STL & Basic Data Structure

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
  • 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().

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 ()) {
 while (! stack1.empty ())
 stack2.push ( stack1.top ()), stack1.pop (); }
 return stack2.top (); 

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
  • 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?

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* 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;
 } 

delete

 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;
 } 

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.