Catalog

Preface

One 、stack Introduction and implementation of

1、 Container adapter

 2、stack Introduction to

 3、stack Simulation Implementation of

Two 、queue Introduction and implementation of

1、queue Introduction to

 2、quueue Simulation Implementation of

  3、 ... and 、priopity_queue Introduction and implementation of

1、priopity_queue Introduction to

2、 functor （ Function object ） Introduction to

2.1 Why introduce the function of amplification

2.2 Introduction of function object

3、 Simulation Implementation of priority queue

  Four 、deque A brief introduction

1、deque Introduction to the principle of

2、deque The advantages and disadvantages of

summary

Preface

Hello, everyone , Today we will continue our study STL The container of . This chapter focuses on STL Knowledge about stacks and queues , Guys, get your notebooks , Let's start together .

One 、stack Introduction and implementation of

1、 Container adapter

Introducing stack Before , We must first learn a concept —— Container adapter .

Concept ： An adapter is a design pattern ( Design patterns are a set of things that are used repeatedly 、 Most people know that 、 Catalogued 、 Summary of code design experience ), This pattern is to convert the interface of one class into another interface that the customer wants .

 2、stack Introduction to

（1） stack Is a container adapter , Specifically used in context with LIFO operations , The deletion can only be performed by inserting and extracting elements from one end of the container .

（2）stack Is implemented as a container adapter , A container adapter is a container that encapsulates a specific class as its underlying container , And provide a specific set of member functions to access its elements .

（3）stack The underlying container can be any standard container class template or some other specific container class , These container classes should support the following operations ：

• empty： Empty operation
• back： Get tail element operation
• push_back： Tail insert element operation
• pop_back： Tail delete element operation

（4） Standard containers vector、deque、list All meet these needs , By default , If not for stack Specify a specific underlying container , By default deque.

 3、stack Simulation Implementation of

	template<class T, class Contioner = std::deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
        void pop()
		{
			_con.pop_back();
		}
        T top()
		{
			return _con.top;
		}
        bool empty()
		{
			return _con.empty();
		}
        size_t size()
		{
			return _con.size();
		}
	private:
		Contioner _con;
	};

Two 、queue Introduction and implementation of

1、queue Introduction to

（1） A queue is a container adapter , Where the element is inserted from one end of the container , Extract the element at the other end .

（2） Queues are implemented as container adapters , The container adapter encapsulates a specific container class as its underlying container class ,queue Provide a specific set of member functions to access its elements . Elements are queued from the end of the queue , Get out of the queue from the head of the queue .

（3） The underlying container can be one of the standard container class templates , It can also be other specially designed container classes . The bottom container shall support at least the following operations :

• empty： Check if the queue is empty
• size： Returns the number of valid elements in the queue
• front： Returns a reference to the queue header 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： Get out of the queue at the head of the queue

（4） Standard container class deque and list Meet these requirements . By default , If not for queue Instantiate the specified container class , Use standard containers deque.

 2、quueue Simulation Implementation of

template<class T, class Contioner = 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();
		}

		bool empty()
		{
			return _con.empty();
		}

		size_t size()
		{
			return _con.size();
		}
	private:
		Contioner _con;
	};

  3、 ... and 、priopity_queue Introduction and implementation of

1、priopity_queue Introduction to

（1）priopity_queue It is called priority queue , Different from ordinary queues, priority queues should always ensure that the first element in the queue is the largest or smallest , It can be understood that the underlying structure is the heap in the binary tree .

（2） Standard container class vector and deque Meet these needs . By default , If not for a specific priority_queue Class instantiation specifies the container class , Then use vector.

（3） Need to support random access iterators , So that the heap structure is always maintained internally . The container adapter automatically calls algorithm functions when needed make_heap、push_heap and pop_heap To automatically complete this operation .

By default , Priority queues are built in a lot , If you want to build a small pile , You need to pass in greater class .greate What kind of thing is a class ？ I will introduce . 

void TestPriorityQueue()
{
//  By default , Created a lot of , The bottom layer is compared according to the less than sign 
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
//  If you want to create a small heap , Replace the third template parameter with greater Comparison mode 
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}

2、 functor （ Function object ） Introduction to

2.1 Why introduce the function of amplification

At the bottom of the priority queue is the heap , We know that building a heap or reducing a heap mainly depends on the comparison symbols in the up adjustment function and the down adjustment function （ The greater than sign and the less than sign ）. If we want to freely control whether the priority queue is large or small, we need to control the comparison symbol in the adjustment algorithm function . But we can't change the greater than sign to the less than sign , Then what shall I do? ？ Our first thought is to use functions . We can write two functions to replace the greater than sign and the less than sign .

// More than no. 
template<class T>
bool greater(const T& a, const T& b)
{
	if (a > b)
	{
		return true;
	}
	else
	{
		return false;
	}
}
// Less than no. 
template<class T>
bool less(const T& a, const T& b)
{
	if (a < b)
	{
		return true;
	}
	else
	{
		return false;
	}
}

If so , We need to add a function pointer to the parameters in the constructor . But function pointers are very complicated to write ,  To solve this problem ,c++ Introduced the imitative function , Also known as function objects .

2.2 Introduction of function object

Function object means that an object of a class can be used like a function .

template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)// Yes （） Overload 
		{
			return l < r;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};

void test()
{
    int a=1,b=2;
    less<int> com;
    com(a,b);// Turn into com.operator()(a,b);
}

（） It's also an operator , In these two classes , We are respectively right （） It's overloaded . You want to call the object （） When overloading operators , Can be directly in （） Write parameters in , The compiler will convert it . This makes the object name look the same as the function name , So it is called function object , Also known as parafunctions . This avoids the appearance of function pointers , When we create the object of priority queue , Just pass a class to the template , You can control whether to build a large heap or a small heap by controlling the class passed .

3、 Simulation Implementation of priority queue

	// Determine the size of the class 
	template<class T>
	struct less
	{
		bool operator()(const T& l, const T& r)
		{
			return l < r;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& l, const T& r)
		{
			return l > r;
		}
	};
    // Priority queue 
	template<class T,class container=std::vector<int>,class compare=less<T>>
	class priority_queue
	{
	public:
		void adjust_up(size_t child)
		{
			compare com;
			while (child > 0)
			{
				size_t parent = (child - 1) / 2;
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent],_con[child]);
					child=parent;
					parent = (child - 1) / 2;
				}

				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);
		}

		void adjust_down(size_t parent)
		{
			compare com;
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if ((child + 1) < _con.size() && _con[child] < _con[child + 1])
				{
					child += 1;
				}
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}
		T top()
		{
			return _con[0];
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}
	private:
		container _con;
	};

  Four 、deque A brief introduction

We know from the previous article , Queues and stacks are generally used by default deque To achieve . Then let's have a brief look deque Implementation principle and characteristics of .

1、deque Introduction to the principle of

deque Also known as double ended queues , It's a double opening " continuity " Spatial data structure . Double opening means ： The time complexity of inserting or deleting data in the head and tail is O(1). and vector comparison , Inserting and deleting data in the header is more efficient , No need to move data . and list comparison , The space utilization rate is relatively high , And random access to .

  actually deque Not completely continuous , It is made up of small pieces of space . The bottom layer is similar to a dynamic two-dimensional array , Pictured ：

2、deque The advantages and disadvantages of

deque The defects of ：deque Surface set vector and list All in all , It is a container for all-round development . But Han Han once said something “ All round development equals all-round mediocrity ”.deque Although you can do anything , But nothing can be done perfectly .deque Although and vector Random access is also supported , But the efficiency is far less than vector, because deque It is piecewise continuous , It can't directly lock a specific position . meanwhile deque Although and list The same head and tail insertion efficiency is very high , But when inserting data in the middle , But you need to move the data , It's no match for list Come directly . and deque There is a fatal flaw ： Not suitable for traversal . because deque It is piecewise continuous , When traversing, the iterator needs to constantly detect whether it has reached the boundary of a certain space , Resulting in low efficiency . therefore , When linear structure is actually needed , Generally, I still consider vector and list.

Why choose deque As stack and queue The underlying default container for ？

1、stack and queue No traversal required , Because there is no iterator , Only operate at both ends .

2、 stay stack When increasing data , and vector comparison deque More efficient , There is no need to migrate a large amount of data during capacity expansion . because deque It is partially continuous , So and list Higher memory utilization than .

use deque do stack and queue The underlying default container for , Perfect to avoid deque The shortcomings of , And it brings its advantages to the extreme , It can be said to be a perfect match .

summary

That's all for this time , Thanks for reading , I hope my friends can gain something after reading it . The road is the high mountain , The coming days would be long , Look forward to seeing you again .