This section is relatively simple. The task is relatively easy.
Start with Stack and Queue.
Let's talk about their usage first, and then simulate the implementation.
catalogue
Simulation Implementation of Stack and Queue
Function template specialization
class template specializations
Template separation compilation
Usage of Stack and Queue
First of all, we have discussed the underlying logic of Stack and Queue Data structures - stacks and queues That's what I said. Therefore, we will not go into too much detail here.
Stack:
Among them, the empty here is actually an insert. They are similar in effect, but the specific implementation principles are different.
There are so many interfaces in total.
Let's take an example.
void test_stack()
{
std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
int main()
{
test_stack();
return 0;
}For such a piece of code, first put it on the stack, put it on the stack five times, then take the top element of the stack at one time, print it, and then get out of the stack.
Let it be implemented, and we get such a result:
Let's talk about Queue again
Similarly, it is still very simple.
Queue:
Then let's give an example and it's over. Because these interfaces are relatively easy to understand.
void test_queue()
{
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
while (!q.empty())
{
cout << q.front() << " ";//Tail in, head out
q.pop();
}
cout << endl;
}//No iterators
int main()
{
test_queue();
return 0;
}Operation screenshot:
OK, that's all for stack and queue usage.
Simulation Implementation of Stack and Queue
If we follow our conventional thinking, we should write as follows:
template <class T>
class stack
{
private:
T* _a;
size_t _size;
size_t _top;
}; //Conventional thinkingSo, what are our other ideas?
The answer is: use existing containers.
We have implemented vector, list and so on before. Now, I can take it and use it. In other words, taking the previously implemented container for repair and modification is a new container. And here we use it, which is called an adapter.
I wonder if you noticed that in the library files, the templates of Stack and Queue have the second parameter:
The Container behind this is called adapter.
If we use the adapter to complete the simulation implementation of stack and queue, it will be too simple.
Specifically, for stack and queue:
Stack:
1. stack is a container adapter, which is specially used in the context of last in first out operation. Its deletion can only be carried out from one end of the container
Insert and extract elements.
2. stack is implemented as a container adapter. The container adapter encapsulates a specific class as its underlying container, and provides a set of specific member functions to access its elements. With a specific class as its underlying element, the tail of the specific container (i.e. the top of the stack) is pressed in and popped out.
3. The underlying container of stack can be any standard container class template or some other specific container classes. These container classes should support the following operations:
- Empty: empty judgment
- back: get tail element operation
- push_back: tail insert element operation
- pop_back: delete element at the end
4. The standard containers vector, deque and list meet these requirements. By default, if no specific underlying container is specified for stack, deque is used by default.
Queue:
1. Queue is a container adapter, which is specially used to operate in FIFO context (first in first out), in which elements are inserted from one end of the container and extracted from the other end.
2. Queue is implemented as a container adapter, which encapsulates a specific container class as its underlying container class, and queue provides a set of specific member functions to access its elements. Elements enter the queue from the end of the queue and exit the queue from the head of the queue.
3. The bottom container can be one of the standard container templates or other specially designed container classes. The bottom container shall at least support the following operations:
- Empty: check whether the queue is empty
- size: returns the number of valid elements in the queue
- front: returns the reference of the queue head element
- back: returns a reference to the end of the queue element
- push_back: enter the queue at the end of the queue
- pop_front: exit the queue at the head of the queue
4. Standard container classes deque and list meet these requirements. By default, if no container class is specified for queue instantiation, the standard container deque is used
Let's look at its simulation implementation:
namespace jxwd{ //Using container adapters
template <class T,class Container = std::vector<T>>
class stack
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop(const T& x)
{
_con.pop_back(x);
}
T top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
bool empty()
{
return size() == 0;
}
private:
Container _con;
};
template<class T, class Container = std::deque<T>>
class queue
{
public:
void push(const T& x)
{
_con.push_back(x);
}
void pop()
{
_con.pop_front();
}
T front()
{
return _con.front();
}
T back()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}It can be seen that in the above code, we use vector and deque as adapters to complete the implementation of stack and queue.
The advantage of this is that after we create a member variable, we can directly call the member function of the adapter to realize the function we want to achieve. Therefore, in terms of the length of the code, it is more than a little simple.
So what is deque we mentioned above?
Let's say a little:
deque: (bidirectional queue)
In other words, it can support random access like vector, or insert and delete like list.
So, if it is really so powerful, can it replace vector and list?
The answer is definitely not.
in other words,
Compared with vector, deque has the following advantages:
When inserting and deleting headers, there is no need to move elements, which is particularly efficient. Moreover, there is no need to move a large number of elements during capacity expansion, so its efficiency must be vector high.
Compared with list,
Its bottom layer is continuous space, which has high space utilization and does not need to store additional fields.
However, deque has one fatal flaw:
Not suitable for traversal.
When traversing, the iterator of deque needs to frequently detect whether it moves to the boundary of a small space, resulting in low efficiency. In sequential scenes, it may need to be traversed frequently. Therefore, in practice, when linear structure is required, vector and list are given priority in most cases. Deque is not widely used, and one application that can be seen at present is, STL uses it as the underlying data structure of stack and queue
The reason for this is actually related to the underlying structure of deque.
In general, the underlying structure of deque is as follows:
Let's explain:
The bottom layer of the double ended queue is an imaginary continuous space, which is actually piecewise continuous. In order to maintain its "overall continuity" and the illusion of random access, it falls on the iterator of deque, so the design of the iterator of deque is more complex.
The following picture should be clear:
- In other words, it first has a one-dimensional array;
- Then the address of the first element of each array is stored in a pointer array.
- Then, each node has four iterators, and each iterator points to the position in the map (that is, the pointer array) and the position of the current element; The position of the first element and the next position of the last element of the current one-dimensional array.
functor
Imitation function -- it is essentially a function object, but the object of this class can be used like a function
for instance:
That is, I overloaded the () operator so that an object of the class can be used like a function.
What are we talking about? Because we need it when we implement the priority queue below.
Why come up with an imitation function? In essence, it is because function pointers are too complex to use. So in C + +, we use imitation function to replace it.
Priority queue (heap)
The so-called priority queue is essentially a heap implementation process.
1. Priority queue is a container adapter. According to the strict weak sorting standard, its first element is always the largest of the elements it contains.
2. This context is similar to the heap. Elements can be inserted in the heap at any time, and only the largest heap element (the element at the top of the priority queue) can be retrieved.
3. The priority queue is implemented as a container adapter, which encapsulates a specific container class as its underlying container class, and queue provides a set of specific member functions to access its elements. The element pops from the "tail" of a particular container, which is called the top of the priority queue.
4. The bottom container can be any standard container class template or other specially designed container classes. The container should be accessible through a random access iterator and support the following operations:
- empty(): check whether the container is empty
- size(): returns the number of valid elements in the container
- front(): returns the reference of the first element in the container
- push_back(): insert elements at the end of the container
- pop_back(): delete the element at the end of the container
5. The standard container classes vector and deque meet these requirements. By default, if there is no specific priority_ If the queue class instantiates the specified container class, vector is used.
6. You need to support random access iterators to always maintain the heap structure internally. The container adapter automatically calls the algorithm function make when needed_ heap,push_heap and pop_heap to automate this operation
Let's first look at its simulation implementation:
template<class T, class Container = std::vector<T> ,class Compare = Less<T>>//The third template parameter here is the imitation function
class priority_queue
{
public:
Compare cmp; //Define a functor object
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if( cmp(_con[child] , _con[parent])) //Compare with an imitation function (similar to a function pointer)
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() &&cmp( _con[child] , _con[child + 1]))
{
child++;
}
if (cmp(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
T top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
}
private:
Container _con;
};
template<class T>
struct Less
{
bool operator()(const T& l, const T& r)
{
return l < r;
}
};
template<class T>
struct great
{
bool operator()(const T& l, const T& r)
{
return l > r;
}
};Advanced template
Non type template parameters
Template parameter classification type shape participates in non type parameter.
Type parameter: the parameter type name that appears in the template parameter list, followed by class or typename.
Non type parameter: a constant is used as a parameter of the class (function) template, which can be used as a constant in the class (function) template
Kind of like #define
be careful:
1. Floating point numbers, class objects and strings are not allowed as non type template parameters.
2. The results of non type template parameters must be confirmed at compile time.
Specialization of template
In general, using templates can implement some type independent code, but for some special types, you may get some wrong results
Like this:
template<class T>
bool IsEqual(T& left, T& right)
{
return left == right;
}
void Test()
{
char* p1 = "hello";
char* p2 = "world";
if(IsEqual(p1, p2))
cout<<p1<<endl;
else
cout<<p2<<endl;
}At this time, it's best to specialize the template. That is, the implementation method of specialization for special types based on the original template class.
Template specialization is divided into function template specialization and class template specialization.
Function template specialization
Specialization steps of function template:
1. There must be a basic function template first
2. The keyword template is followed by a pair of empty angle brackets < >
3. The function name is followed by a pair of angle brackets, which specify the type to be specialized
4. Function parameter table: it must be exactly the same as the basic parameter type of the template function. If it is different, the compiler may report some strange errors
Like this:
template<>
bool IsEqual<char*>(char*& left, char*& right)
{
if(strcmp(left, right) > 0)
return true;
return false;
}Note: in general, if the function template encounters a type that cannot be processed or processed incorrectly, the function is usually given directly in order to simplify the implementation.
That is to say, directly:
bool IsEqual(char* left, char* right)
{
if(strcmp(left, right) > 0)
return true;
return false;
}class template specializations
Full specialization
Full specialization is to determine all parameters in the template parameter list (as follows:)
template<class T1, class T2>
class Data
{
public:
Data() {cout<<"Data<T1, T2>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
template<>
class Data<int, char>
{
public:
Data() {cout<<"Data<int, char>" <<endl;}
private:
T1 _d1;
T2 _d2;
};
void TestVector()
{
Data<int, int> d1;
Data<int, char> d2;
}Partial specialization
Partial specialization: any specialized version of further conditional design for template parameters
Partial specialization can be expressed in the following two ways:
partial specialization
Specialize some parameters in the template parameter class table.
// Specialize the second parameter to int
template <class T1>
class Data<T1, int>
{
public:
Data() {cout<<"Data<T1, int>" <<endl;}
private:
T1 _d1;
int _d2;
};Further restrictions on parameters
Partial specialization does not only refer to the specialization of some parameters, but a specialized version designed for the further conditional constraints of template parameters.
//The two parameters are partial specialization to pointer type
template <typename T1, typename T2>
class Data <T1*, T2*>
{
public:
Data() {cout<<"Data<T1*, T2*>" <<endl;}
private:
T1 _d1;
T2 _d2;
};Template separation compilation
Let's simply mention this: the author thinks this part itself is very simple and has nothing to say.
A thousand words: templates cannot be compiled separately.
// a.h
template<class T>
T Add(const T& left, const T& right);
// a.cpp
template<class T>
T Add(const T& left, const T& right)
{
return left + right;
}
// main.cpp
#include"a.h"
int main()
{
Add(1, 2);
Add(1.0, 2.0);
return 0;
}Like this.
reason:
Solution:
1. Put the declaration and definition in a file "xxx.hpp" or XXX H actually, it's OK. This is recommended.
2. Explicitly instantiate the position defined by the template.
Template summary
[advantages]
1. Templates reuse code, save resources, and develop iteratively faster. As a result, the standard template library (STL) of C + + is generated
2. Enhanced code flexibility
[defects]
1. Templates can cause code bloat and lead to longer compilation time
2. When a template compilation error occurs, the error information is very messy and it is not easy to locate the error
