Simulation implementation of STL-queue and priority_queue

Review

For STL, we already know vector and list, and they are containers called one of the six major components in STL. We also learned to simulate the implementation of stack, and stack is called an adapter of one of the six major components in STL , Today, let’s learn about the analog implementation of queue and the analog implementation of priority_queue, and they are also adapters.

For the adapter, we refer to the experience of stack simulation implementation. The interface of the adapter is only implemented by calling the interface of the container. Therefore, to implement an adapter, as long as you understand its data structure, the implementation is very simple.

queue (queue)

What is a queue? In daily life, if we want to go to the supermarket to buy things, if there are many people at the cash register, we need to line up from the end of the line until the people in front of us have collected the money. This is a queue, and the people who line up first Go first, people in the back row go later. Queues follow the first-in-first-out principle.

Looking back at the stack, the stack follows the principle of first in, last out, which is the opposite of the queue we are going to learn today.

So, the overall queue is still easy to understand, so if we want to realize it, what kind of data structure should we use?

We can use vector as a container for stack, so what about queue? Can it also be done using vector as a container?

Here we need to consider our time complexity to measure, because of the queue’s first-in-last-out principle, if we want to delete, we can only delete from the data at the head of the queue, but if we start from the head of the queue To delete data, vector is used as a continuous array space, so it is necessary to move data every time you delete, and every time you delete data, it will be an O(N) time complexity, so it is not efficient, so you cannot use vector as a queue container. So, have you already thought of a more suitable container to implement our queue more efficiently? —–list and deque are very good, they are not expensive for head deletion, and the time is very efficient!

STL uses deque as the default container of queue.

Simulate queue

template<typename T , class Container = deque<T>>
class queue
{
public:
void push(const T & amp; data)
{
_data.push_back(data);
}

size_t size() const
{
return _data. size();
}

void pop()
{
_data. pop_front();
}

bool empty() const
{
return _data. empty();
}
\t\t
T & front()
{
return _data. front();
}
const T & front() const
{
return _data. front();
}

T & back()
{
return _data.back();
}

const T & back() const
{
return _data.back();
}
private:
Container_data;
};

The implementation of the template is very simple, and the interface to implement it is only to call the interface of the container. There is also a reason why vector cannot be used as a container, because vector does not have the pop_front interface at all, so it cannot be used as our container .

priority_queue (priority queue)

The difference between priority_queue and queue is quite big. The data structure of priority_queue is actually a heap. For the data structure of heap, its container can be vector, but queue is not.

For the content of the heap, if you don’t understand it well, you can find the content of the heap first. The heap is a data structure based on a binary tree.

The addition and deletion of the queue is like this (take a large pile as an example)

For deleting data, it will first exchange the top element (the largest element) with the last element, then delete the largest element (tail deletion), and then perform heap sorting, and the top element (originally the tail element) will be sorted Adjust downward, this series of operations completes the delete operation

For inserting data, it inserts data at the end first, and then performs heap sort

Because it uses the storage method of the heap, we must implement two functions of the heap—up adjustment and down adjustment

Both upsizing and downsizing are heap sorting algorithms used to maintain the heap structure

Adjust Up

When inserting data, perform heap sorting and maintain the characteristics of the heap

void adjust_up(size_t pos) //up adjustment
{
Compare com;
size_t child = pos;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_data[parent] < _data[child])
if (com(_data[parent],_data[child])) // functor, we will talk later
{
std::swap(_data[parent], _data[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

Adjust Down

void adjust_down(size_t pos) //Adjust down
{
Compare com;
size_t parent = pos;
size_t child = parent * 2 + 1;
while (child < _data. size())
{
if (child + 1 < size() & amp; & amp; com(_data[child], _data[child + 1]))
{
child = child + 1;
}
if (com(_data[parent], _data[child])) // functor
{
std::swap(_data[parent], _data[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

The if judgment statement for judging whether to adjust upward (downward) here uses the knowledge of the functor, which will not be discussed here for the time being, and will be discussed later. You only need to know that this is used to judge whether adjustment is required.

push

void push(const T & amp; data)
{
_data.push_back(data);
adjust_up(size() - 1);
}

When the data is inserted, the newly inserted elements are adjusted upwards so that the heap structure is maintained.

pop

void pop() //Delete the head
{
assert(!empty());
std::swap(_data. front(), _data. back());
_data. pop_back();
adjust_down(0);
}

Why is the method of exchanging first and then deleting at the end? Because if you want to do heap sort, the time complexity of using upward adjustment is O(N*logN), and if using downscaling its complexity is O(N).

Other functions

bool empty() const
{
return _data. empty();
}


size_t size() const
{
return _data. size();
}


const T & top() const
{
assert(!empty());
return _data. front();
}

Functor

template<typename T , class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
private:
Container_data;
};

template<typename T>
struct greater
{
public:
bool operator()(const T & amp; t1, const T & amp; t2) const
{
return t1 > t2;
}
};

In implementing priority_queue, its template function is like this

template<typename T , class Container = vector<T>, class Compare = less<T> >

The first two are not difficult to understand. As an adapter, it needs to be passed into the container, so what is the third one?

In the implementation of the priority_queue just now, since it is implemented in the form of a heap, sometimes we may need a large or small heap. At this time, we can use a functor to achieve it, but why is it called a functor?

A functor is also a class, but when we use it, is it like a function call?

void adjust_up(size_t pos) //up adjustment
{
Compare com;
size_t child = pos;
size_t parent = (child - 1) / 2;
while (child > 0)
{
//if (_data[parent] < _data[child])
if (com(_data[parent],_data[child])) // functor
{
std::swap(_data[parent], _data[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

And how is it implemented in the class? -> This effect is achieved by overloading ().

template<typename T>
struct greater
{
public:
bool operator()(const T & amp; t1, const T & amp; t2) const
{
return t1 > t2;
}
};

This is the functor class greater

If you want to implement the functor class less, just write

template<typename T>
struct less
{
public:
bool operator()(const T & amp; t1, const T & amp; t2) const
{
return t1 < t2;
}
};