STL & Basic Data Structure

Original link:


Briefly introduce the principles of Vector vector, List linked list, Queue queue, Stack stack, Priority_Queue priority queue, and the use of these data structures in C++ STL, as well as some application scenarios for written tests and interviews.

STL container

Introduction to STL Containers

  • Containers are objects that hold a series of objects.

  • For example, std::vector, std::list std::string , std::queue<std::vector>;*

  • Classification:

    • Sequence container
    • Associative container
    • There are also Container adaptor and Almost container
  • You can also design your own container, as long as it meets common standards and

*Note: When compiling with the C++98 standard, you need to add a space between the two >s.


  • Abstraction of pointers.
  • Hence the need to overload the * operator.
  • Pointer operations are based on using a contiguous memory space, which is not the case for some containers.
  • Based on the types of operations that can be performed, iterators can be divided into the following categories:
    • All iterators support the dereference operator (*) and the increment operator (++)
    • On this basis, Input iterator supports ==, !=, single read, ->; Output Iterator only supports single write (after class: check I/O library related content to understand their usage scenarios)
    • Forward iterator supports repeated access and read and write on the basis of Input iterator
    • Bidirectional iterator supports the decrement operator (–) on the basis of Forward iterator
    • Random-access iterator supports [], +, +=, −, −=, <, <=, >, >= operators on the basis of Bidirectional iterator (same function as normal pointer)

In order to ensure commonality, some library functions are also provided in the standard library

  • #include
  • std::advance(iter, n) iterator iter increments n times
  • std::distance(iter1, iter2) returns the distance between iterators iter1 and iter2
  • std::next(iter, n=1), std::prev(iter, n=1) returns the iterator corresponding to “iter + n” or “iter – n” (c++11)
  • Note that without a Random-access iterator, these methods may be linear in complexity, or have undefined behavior, or fail to compile.

The container’s begin() and end() methods can get the start and end iterators

  • for (auto it = c.begin(); it != c.end(); ++it)
  • for (auto & x: c)
  • The iterator is of type ContainerType::iterator

In addition, the cbegin() and cend() methods can return constant iterators at the beginning and end (similar to constant pointers)

  • for (auto it = c.cbegin(); it != c.cend(); ++it)
  • for (const auto &x: c)
  • The iterator is of type ContainerType::const_iterator

After class: Query relevant information about reverse iterators, explain the usage of rbegin(), rend(); crbegin(), crend().


In the design process of the C++ standard, these standard containers are intentionally shared, so as to exert the characteristics of template polymorphism.

For example, common constructors:

  • ContainerType c(num)
  • ContainerType c(num, x)
  • ContainerType c(beg, end)

Capacity related methods:

  • int s = c.size(); bool b = c.empty();
  • c.resize(num); c.resize(num, x);
  • c.clear();

Reference: Bjarne Stroustrup. The C++ Programming Language, 4th edition. §31.3


std::stack<T, Container>

  • It belongs to Container Adapter and needs to be based on a Sequence container
  • Cannot use iterator access
  • push(x)
  • pop()
  • top()
  • After class: understand initializer_list, understand the use of emplace() method.

How to implement a stack?

  • For convenience, it is assumed that the total amount of data is N and the data type is int.
  • int stack[N], top; The data is stored in the interval [0, top).

Some basic operations:

  • push: stack[top++] = x;
  • pop: int y = stack[–top];
  • size: return top;
  • empty: return top == 0;

Catalan number


How to implement a queue

int queue[N], head, tail; where elements are stored in the [head, tail) interval.

Basic operation

  • push: queue[tail++] = x;
  • pop: int y = queue[head++];
  • size: return tail – head;
  • empty: return head == tail;

circular queue


 if ( stack2.empty ()) {
while (! stack1.empty ())
stack2.push ( ()), stack1.pop (); }
return ();


  • Before we assumed that the amount of data is known, so when our amount of data is unknown?
  • array of indeterminate length
    • #include std::vector
    • Sequence Container
    • Random-access iterator
    • Random access: operator [], at(x), front(), back()
    • insert(iter, x), push_back(x)
    • erase(iter), pop_back()

How to implement a vector?


performance analysis


Lists and Linked Lists

  • Another way to achieve dynamism is to not use an array, but to open up a new space for each additional element
  • But we still need to save some extra information to save the order relationship between them – pointers!
  • This chained data structure is called a linked list.
  • Example: train car
  • #include std::list
    • Sequence container, Bidirectional iterator
    • front(), back()
    • insert(iter, x), push_back(x), push_front(x),
    • erase(iter), pop_back(), pop_front()

linked list structure

Sentinel node

Basic operation

 Node* insert (Node* pos, int value) {
Node* n = new Node (value);
n->next = pos->next;
pos->next = n;
return n;
 Node* insert (Node *pos, int value) {
Node *n = new Node (value);
n->next = pos->next;
n->prev = pos;
pos->next->prev = n;
pos->next = n;
return n;
 void erase (Node *pos) {
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
delete pos;
 void erase2 (Node *pos) {
Node *tmp = pos->next;
pos->next = pos->next->next;
delete tmp;
  • for (Node* x = head->next; x != tail; x = x->next);
  • Comparing begin() and end() of iterators
  • “Subscript” access?
  • Querying the previous element in a singly linked list?
  • size()?
performance analysis

priority queue


  • Container Adaptor, no iterator
  • push(x), pop(), top()
  • std:priority_queue<T, Container=std::vector, Compare=std::less>
    • the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that “come before” are actually output last
    • Need to define less than sign
    • std::greater (need to define greater than sign)

Reference: std::priority_queue –

How to implement a priority queue? (optional)

  • A variety of implementation methods, the simplest one – binary heap
  • Heap: A binary tree that satisfies the parent node priority not less than the child node
  • For convenience, a complete binary tree can be used
  • Up adjustment procedure up, push()
  • Downward adjustment procedure down, pop()

some applications

Monotonic stack Monotonic queue

expression evaluation

  • To simplify things, let’s say we only have operations like + – * / ()
  • Observe: 1+2 3 and 1 2+3. When can we determine the order of computation?
  • The first equation needs to go to the end, and the second equation finds that the previous content can be calculated when it scans to +
  • Undecidable formula priority size increment
  • A monotonic stack similar to a monotonic queue. Also need to maintain uncalculated numbers
  • Parentheses? The parentheses are also included in the scope of the priority comparison, or each time a layer of parentheses is encountered, the priority within the parentheses increases by one step

Huffman coding

  • (Last step of the problem) With a sequence of length n, perform n – 1 operations, each time taking the two elements with the smallest value and putting their sum back into the sequence. Find the two numbers taken out by each step of the operation
  • Compare the definition and interface of the priority queue

This article is reprinted from:
This site is for inclusion only, and the copyright belongs to the original author.