A brief overview of the implementation principles and key points of commonly used STL containers.
vector
vector is one of the most commonly used STL containers, similar in usage to an array. Its internal implementation uses contiguous memory, but unlike a static array, it can dynamically grow. The key point of vector is that when space runs out, it allocates a new buffer twice the current size, copies the old data over, and frees the old space.
struct _Vector_impl: public _Tp_alloc_type {
pointer _M_start; // start of elements
pointer _M_finish; // end of elements
pointer _M_end_of_storage; // end of allocated storage
// ... more code omitted
};Here is the push_back implementation: if there is remaining space, the element is appended directly; otherwise, dynamic expansion is triggered.
void push_back(const value_type& __x) {
if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) {
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
++this->_M_impl._M_finish;
} else
_M_realloc_insert(end(), __x);
}
template<typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, const _Tp& __x) {
const size_type __len = _M_check_len(size_type(1), "vector::_M_realloc_insert"); // 2x current size
const size_type __elems_before = __position - begin();
pointer __new_start(this->_M_allocate(__len));
pointer __new_finish(__new_start);
__try {
// The order of the three operations is dictated by the C++11
// case, where the moves could alter a new element belonging
// to the existing vector. This is an issue only for callers
// taking the element by lvalue ref (see last bullet of C++11
// [res.on.arguments]).
_Alloc_traits::construct(this->_M_impl, __new_start + __elems_before, __x);
__new_finish = pointer();
__new_finish = std::__uninitialized_move_if_noexcept_a(this->_M_impl._M_start, __position.base(), __new_start, _M_get_Tp_allocator();
++__new_finish;
__new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), this->_M_impl._M_finish, __new_finish, _M_get_Tp_allocator());
}__catch(...) {
if (!__new_finish)
_Alloc_traits::destroy(this->_M_impl,
__new_start + __elems_before);
else
std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
_M_deallocate(__new_start, __len);
__throw_exception_again;
}
std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, _M_get_Tp_allocator());
_M_deallocate(this->_M_impl._M_start, this->_M_impl._M_end_of_storage - this->_M_impl._M_start);
this->_M_impl._M_start = __new_start;
this->_M_impl._M_finish = __new_finish;
this->_M_impl._M_end_of_storage = __new_start + __len;
}
// Called by _M_fill_insert, _M_insert_aux etc.
size_type _M_check_len(size_type __n, const char* __s) const {
if (max_size() - size() < __n)
__throw_length_error(__N(__s));
const size_type __len = size() + std::max(size(), __n); // double the length
return (__len < size() || __len > max_size()) ? max_size() : __len;
}
pointer _M_allocate(size_t __n) {
typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
}operator[] is overloaded for array-style access:
reference
operator[](size_type __n) _GLIBCXX_NOEXCEPT {
__glibcxx_requires_subscript(__n);
return *(this->_M_impl._M_start + __n);
}Watch out for iterator invalidation — a common issue across many STL containers.
list
Unlike vector, list elements are not contiguously allocated and do not support random access. The advantage is that insertion and deletion are O(1). STL implements a doubly linked list, with each node containing both previous and next pointers.
/// An actual node in the %list.
template<typename _Tp>
struct _List_node : public __detail::_List_node_base {
_Tp _M_data;
_Tp* _M_valptr() { return std::__addressof(_M_data); }
_Tp const* _M_valptr() const { return std::__addressof(_M_data); }
};
struct _List_node_base {
_List_node_base* _M_next;
_List_node_base* _M_prev;
static void swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;
void _M_transfer(_List_node_base* const __first, _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;
void _M_reverse() _GLIBCXX_USE_NOEXCEPT;
void _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;
void _M_unhook() _GLIBCXX_USE_NOEXCEPT;
};deque
The double-ended queue has a unique implementation distinct from both vector and list. It uses small contiguous segments linked together by a pointer array (the map), where each pointer in the map points to the head of a contiguous segment. This layout enables access to all elements.
deque Source Analysis
Let’s examine key implementation details. The deque iterator (compared to vector and list) requires special handling at segment boundaries due to the segmented layout:
#define _GLIBCXX_DEQUE_BUF_SIZE 512 // default segment size
_GLIBCXX_CONSTEXPR inline size_t __deque_buf_size(size_t __size) {
return (__size < _GLIBCXX_DEQUE_BUF_SIZE ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) :size_t(1));
}
template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator {
typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
typedef _Tp* _Elt_pointer;
typedef _Tp** _Map_pointer;
static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT {
return __deque_buf_size(sizeof(_Tp));
}
typedef std::random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Ptr pointer;
typedef _Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Deque_iterator _Self;
_Elt_pointer _M_cur; // current position
_Elt_pointer _M_first; // start of current segment
_Elt_pointer _M_last; // end of current segment
_Map_pointer _M_node; // pointer array — provides access to all contiguous segments
// constructors
_Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT : _M_cur(__x), _M_first(*__y),
_M_last(*__y + _S_buffer_size()), _M_node(__y) { }
_Deque_iterator() _GLIBCXX_NOEXCEPT: _M_cur(), _M_first(), _M_last(), _M_node() { }
_Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT: _M_cur(__x._M_cur), _M_first(__x._M_first),
_M_last(__x._M_last), _M_node(__x._M_node) { }
iterator _M_const_cast() const _GLIBCXX_NOEXCEPT {
return iterator(_M_cur, _M_node);
}
reference operator*() const _GLIBCXX_NOEXCEPT {
return *_M_cur;
}
pointer operator->() const _GLIBCXX_NOEXCEPT {
return _M_cur;
}
// Overloaded ++: when _M_cur reaches the end of the current segment, advance to the next segment
_Self& operator++() _GLIBCXX_NOEXCEPT {
++_M_cur;
if (_M_cur == _M_last) {
_M_set_node(_M_node + 1); // move to next segment
_M_cur = _M_first; // first element of the next segment
}
return *this;
}
_Self operator++(int) _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
++*this;
return __tmp;
}
_Self& operator--() _GLIBCXX_NOEXCEPT {
if (_M_cur == _M_first) { // similarly, if at the first element, -- moves to the previous segment
_M_set_node(_M_node - 1);
_M_cur = _M_last; // move to the end of the previous segment
}
--_M_cur; // since it's a [start, last) range, decrement _M_cur
return *this;
}
_Self operator--(int) _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
--*this;
return __tmp;
}
_Self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT {
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size())) // if current segment has enough room
_M_cur += __n;
else { // current segment doesn't have enough room — calculate which segment to jump to
const difference_type __node_offset = __offset > 0 ? __offset / difference_type(_S_buffer_size()) : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first + (__offset - __node_offset * difference_type(_S_buffer_size()));
}
return *this;
}
_Self operator+(difference_type __n) const _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
return __tmp += __n;
}
_Self& operator-=(difference_type __n) _GLIBCXX_NOEXCEPT {
return *this += -__n; }
_Self operator-(difference_type __n) const _GLIBCXX_NOEXCEPT {
_Self __tmp = *this;
return __tmp -= __n;
}
reference operator[](difference_type __n) const _GLIBCXX_NOEXCEPT { return *(*this + __n); }
// Prepares to traverse new_node. Sets everything except _M_cur, which should therefore be set by the caller immediately afterwards, based on _M_first and _M_last.
void _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT { // jump to a new segment
_M_node = __new_node;
_M_first = *__new_node;
_M_last = _M_first + difference_type(_S_buffer_size());
}
};The key challenge in the deque iterator is handling the boundaries between contiguous segments. Now let’s look at the deque class itself, focusing on push_front/pop_front and push_back/pop_back. push_back is O(1), similar to vector. But why is push_front also O(1)? If the first segment has spare room before start, the element is inserted directly. If not, a new segment is allocated, its head pointer is placed into the map, and if the map itself lacks space, the map is reallocated — see the source for details:
template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc> {
// ... typedefs omitted ...
public:
void push_front(const value_type& __x) { // if the first segment has room at the front, insert directly
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) {
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_start._M_cur - 1, __x);
--this->_M_impl._M_start._M_cur;
} else // otherwise, allocate at the front
_M_push_front_aux(__x);
}
void push_back(const value_type& __x) {
if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1) {
_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish._M_cur, __x);
++this->_M_impl._M_finish._M_cur;
} else
_M_push_back_aux(__x);
}
void pop_front() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_last - 1) {
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_start._M_cur);
++this->_M_impl._M_start._M_cur;
} else
_M_pop_front_aux();
}
void pop_back() _GLIBCXX_NOEXCEPT {
__glibcxx_requires_nonempty();
if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_first) {
--this->_M_impl._M_finish._M_cur;
_Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish._M_cur);
} else
_M_pop_back_aux();
}
iterator insert(iterator __position, const value_type& __x);
void clear() _GLIBCXX_NOEXCEPT { _M_erase_at_end(begin()); }
protected:
void _M_push_back_aux(const value_type&);
void _M_push_front_aux(const value_type&);
void _M_pop_back_aux();
void _M_pop_front_aux();
};The implementation of deque is significantly more complex than vector and list, primarily because of its unique memory layout. The following code handles the spatial reallocation involved in front/back push/pop operations:
// Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
template<typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_push_back_aux(const value_type& __t) {
_M_reserve_map_at_back();
*(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); // map's new pointer points to the newly allocated segment
__try {
this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node + 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
} __catch(...) {
_M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
__throw_exception_again;
}
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
template<typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_push_front_aux(const value_type& __t) {
_M_reserve_map_at_front();
*(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); // map's designated position points to the newly allocated segment
__try {
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node - 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
} __catch(...) {
++this->_M_impl._M_start;
_M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
__throw_exception_again;
}
}
// Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_pop_back_aux() {
_M_deallocate_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(), this->_M_impl._M_finish._M_cur);
}
// Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_pop_front_aux() {
_Alloc_traits::destroy(_M_get_Tp_allocator(), this->_M_impl._M_start._M_cur);
_M_deallocate_node(this->_M_impl._M_start._M_first);
this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
}The following source code adjusts the map. If the map lacks appropriate space to insert a new segment’s head pointer, it is reallocated. For example, if the back of the map is full but the front has plenty of empty space, the existing map elements are shifted toward the center so that both ends have free room. If the map itself runs out of space, a larger map is allocated (new_size = old_size + max(old_size, nodes_to_add) + 2):
void _M_reserve_map_at_back(size_type __nodes_to_add = 1) {
if (__nodes_to_add + 1 > this->_M_impl._M_map_size - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, false);
}
void _M_reserve_map_at_front(size_type __nodes_to_add = 1) {
if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node - this->_M_impl._M_map))
_M_reallocate_map(__nodes_to_add, true);
}
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) {
const size_type __old_num_nodes = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (this->_M_impl._M_map_size > 2 * __new_num_nodes) {
__new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
if (__new_nstart < this->_M_impl._M_start._M_node)
std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
else
std::copy_backward(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart + __old_num_nodes);
} else {
size_type __new_map_size = this->_M_impl._M_map_size + std::max(this->_M_impl._M_map_size, __nodes_to_add) + 2;
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 + (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node, this->_M_impl._M_finish._M_node + 1, __new_nstart);
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}This covers the core of deque — the key member functions, iterator implementation, and map management.
deque vs. vector vs. list
vector provides random access and dynamic growth, but front insertion is O(n) and expansion requires copying all elements. list offers O(1) insertion and deletion at both ends, but lacks random access (lookup is O(n)), and each node stores prev/next pointers — a significant per-element overhead. deque strikes a balance: O(1) front and back insertion/deletion, O(n) middle insertion (similar to both), plus random access. During expansion, it does not need to copy all elements — it only allocates new segments and, at worst, reallocates the map (which is an array of segment pointers, far smaller than the total element count). So deque generally outperforms vector in common scenarios and uses less extra space than list (though deque has a higher minimum memory overhead due to the map and at least one segment — when the element count is very small, overhead exceeds list, but for larger counts it is more space-efficient than list).
stack
A commonly used data structure with a straightforward implementation built on deque (though vector or list can also serve as the underlying container):
// Stack implementation -*- C++ -*-
template<typename _Tp, typename _Sequence = deque<_Tp> >
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:
stack(): c() { }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() {
__glibcxx_requires_nonempty();
return c.back();
}
void push(const value_type& __x) { c.push_back(__x); }
void pop() {
__glibcxx_requires_nonempty();
c.pop_back();
}
}; queue
Queues include the standard FIFO queue and the priority queue, which emphasizes priority over insertion order.
Standard Queue
Similar to stack, the standard queue is built on deque:
template<typename _Tp, typename _Sequence = deque<_Tp> >
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:
queue(): c() { }
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() {
__glibcxx_requires_nonempty();
return c.front();
}
reference back() {
__glibcxx_requires_nonempty();
return c.back();
}
void push(const value_type& __x) { c.push_back(__x); }
void pop() {
__glibcxx_requires_nonempty();
c.pop_front();
}
};Priority Queue (priority_queue)
The priority queue is implemented as a heap over an array, which is why vector serves as the underlying container (rather than other containers). Heap operations (insert, delete) always involve the tail of the array, and vector’s 2x growth aligns well with the binary tree property (next level = sum of all previous nodes + 1). Other containers like deque could also be used, but are suboptimal. The implementation is straightforward once you understand heaps:
template<typename _Tp, typename _Sequence = vector<_Tp>, typename _Compare = less<typename _Sequence::value_type> >
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;
typedef _Compare value_compare;
protected:
_Sequence c;
_Compare comp; // the priority queue is heap-based, which needs frequent comparisons
public:
explicit priority_queue(const _Compare& __x = _Compare(), const _Sequence& __s = _Sequence()): c(__s), comp(__x) {
std::make_heap(c.begin(), c.end(), comp); // build the heap
}
bool empty() const {
return c.empty();
}
size_type size() const { return c.size(); }
const_reference top() const {
__glibcxx_requires_nonempty();
return c.front();
}
void push(const value_type& __x) { // insert: append to the tail, then sift up to restore heap property
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
void pop() { // pop the top element
__glibcxx_requires_nonempty();
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
};Once you understand heap principles, the priority queue implementation is easy to follow. Further heap-related STL source analysis is beyond the scope of this note.