Understanding C++ STL: The Functionality of Container Adapters
Written on
Chapter 1: Introduction to C++ STL Container Adapters
In this chapter, we will explore the C++ Standard Template Library (STL), focusing specifically on container adapters such as stack, queue, and priority_queue. We will analyze their source code and discuss why they are not classified as containers in the traditional sense.
Section 1.1: Why Aren't Stack and Queue Considered Containers?
This section will investigate the reasons behind the classification of stack and queue as container adapters rather than traditional containers. We will analyze the underlying source code with this question in mind.
Section 1.2: The Stack Implementation
When examining the stack implementation, we note two primary aspects:
- The default underlying sequence used is deque.
- The internal functions are designed to invoke the corresponding functions of the _Sequence container.
template <typename _Sequence>
class stack {
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
_Sequence c;
public:
reference top() {
__glibcxx_requires_nonempty();
return c.back();
}
void push(const value_type& __x) {
c.push_back(__x);}
};
Testing the Stack Implementation
For the stack, the underlying container can be either vector, deque, or list, but not map or set. The compiler does not rigorously check compatibility, which can lead to compilation failures if non-compatible functions are called.
int test_stack() {
cout << "============test_stack=============" << endl;
stack<int> c;
for (long i = 0; i < 100000; i++)
c.push(i + 1);
cout << "stack.size()= " << c.size() << endl;
cout << "stack.top()= " << c.top() << endl;
c.pop();
cout << "stack.size()= " << c.size() << endl;
cout << "stack.top()= " << c.top() << endl;
}
Section 1.3: The Queue Implementation
Similar to the stack, the queue's source code highlights two main points:
- The default _Sequence is deque.
- The implementation of internal functions also calls the corresponding functions of the _Sequence container.
template <typename _Sequence>
class queue {
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
_Sequence c;
public:
void push(const value_type& __x) {
c.push_back(__x);}
void pop() {
__glibcxx_requires_nonempty();
c.pop_front();
}
};
In this video titled "C++ STL Container Adapters," we will explore how these container adapters function and their roles within the STL.
Section 1.4: The Priority Queue Implementation
The priority queue also utilizes vector as its default underlying container:
template <typename _Sequence, typename _Compare = less>
class priority_queue {
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
_Sequence c;
_Compare comp;
public:
reference top() {
__glibcxx_requires_nonempty();
return c.front();
}
void push(const value_type& __x) {
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
};
Testing the Performance of Queue and Priority Queue
For the queue, the underlying containers can be deque or list, while the priority queue supports vector and deque, but not list, map, or set.
The second video titled "C++ STL std::priority_queue (a container adaptor) | Modern Cpp Series Ep. 133" provides insights into implementing and testing the priority_queue in C++.
Section 1.5: Conclusion
In conclusion, the container adapters stack, queue, and priority_queue are not classified as traditional containers due to their specific functionalities and underlying implementations.