Original link: https://yousazoe.top/archives/558bb9a.html
introduction
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.
Iterator
 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
 Randomaccess 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 Randomaccess 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().
interface
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
stack
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
queue
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
practise
if ( stack2.empty ()) { 
vector
 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
 Randomaccess iterator
 Random access: operator [], at(x), front(), back()
 insert(iter, x), push_back(x)
 erase(iter), pop_back()
How to implement a vector?
shrink
performance analysis
list
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
insert
Node* insert (Node* pos, int value) { 
Node* insert (Node *pos, int value) { 
delete
void erase (Node *pos) { 
void erase2 (Node *pos) { 
traverse
 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
std::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 – cppreference.com
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: https://yousazoe.top/archives/558bb9a.html
This site is for inclusion only, and the copyright belongs to the original author.