directory

  1. Introduction of six parts of STL
  2. The container classification
  3. Introduction to sequential containers (vector, List, deque)
  4. Associative container
  5. data
  6. harvest

1. Six parts of STL

STL: CPP Standard Library CPP standard library

STL’s six components compounts:

  1. Containers
  2. Allocators
  3. Algorithms
  4. Iteratros
  5. Adapters (Adapters)
  6. Functors

The more important or commonly used components are: containers, algorithms, iterators, and functors. Iterators are Bridges between containers and algorithms, and functors are operator overloads of “()”. Next we will focus on practical containers and algorithms. This article focuses on the features of various containers.

Ii. Container classification

Containers can be divided into sequential containers, associative containers and unordered containers according to whether memory allocation is continuous or not.

Sequential containers: Emphasize the ordering of values, with each element having a fixed position

Contains the following container types:

  1. Array (Array fixed size)
  2. Vector (the Vector expands automatically),
  3. Deque (two-way queue, both front and back expandable)
  4. -Penny: A List.
  5. Forward-list :(single necklace list)

Associative container: binary tree structure, there is no strict physical order between the elements. Usage scenario: Mass search

Contains the following containers:

  1. Set/Multiset
  2. Map/Multimap: key – Value

Set and Map elements cannot be repeated, but Multiset and Map elements can be repeated

Inside is a highly balanced tree or red-black tree structure

Unordered container HashTable Separate Chaining

Vector, List, deque

3.1 the vector

The difference between a Vector and a normal array is that an array is a static space and a Vector is a dynamic extension. The dynamic scaling here is not about adding new space after the original space, but about finding more memory space and copying the original data in a way that is twice as long.

The way data is obtained

[]
at
front
back
Copy the code

Capacity () resize the vector: resize()

3.2 the list list

A linked list is made up of nodes that contain data fields and pointer fields.

Advantages: Data can be added and deleted quickly at any position, only need to change the point of the node pointer field, without moving the subsequent position; The size is flexible, and you don’t have to worry about doubling the size of a vector: no contiguous array blocks in traversal speed; Pointer fields take up more space than arrays.

The linked list in Stl is a bidirectional cyclic linked list. List iterators can only move forward or backward, not jump

Operator++ () returns self and operator++ (int) returns selfCopy the code

3.3 a deque container

A double-ended array, which can be inserted and deleted at the end of the deque, is segmented contiguous

The sequential container adaptor stack inside the deque is implemented first and then out

The sequential container adapter queue, fifO, is also internally implemented as a DEQUE

The common methods are as follows:

The assignment operation

=
assign(begin,end)
assign(n,num)
Copy the code

The size of the

Empty () deque.size() deque.resize(num) deque.resize(num,elem) Void void printDeuqe(const deque<int &d>) { for(deque<int>::const_iterator it =d.begin(); it ! =d.end(); it++) { cout << *it << ""; } cout <<endl; }Copy the code

Insert the delete

Push_back (elem); Push_front (elem); // Remove the last data from the container pop_back(); // Delete the container's first data pop_front(); Insert (pos,elem); insert(pos,elem); Insert (pos,beg,end); clear(); erase(pos); erase(beg,end); erase(pos,beg,end);Copy the code

Data access

// return the data to which pos refers at(int pos); opeartor[]; // Return the first data element in the container front(); // Return the last data element of the container back();Copy the code

The sorting

Sort (iterator beg, iterator end) sort(iterator beg, iterator end)Copy the code

4. Associative containers

You can think of it as a small relational database

4.1 the set/multiset container

All elements in set are sorted automatically when inserted. Set does not allow duplicate values. Multiset can be repeated.

Assign to insert data using insert

Assignment constructs copy constructs

Search and statistics

// Find if the key exists, if so, return the iterator of the element of the key; Set.end () find(key); // Count the number of key elements. For set, return 0 or 1.Copy the code

The sorting

Bool opeartor () (int x, int y) const; bool opeartor () (int x, int y) const; class Mycompare { public: bool operator()(int v1,int v2) { return v1 >v2; }} For custom collation of data types, use the parafter function to specify collation rules. set<Object,MyCompare>Copy the code

4.2 map/multimap container

All elements in a map are pairs. The first element of a pair is a key, which acts as an index, and the second element is a value. All elements are sorted automatically based on the key of the element.

In addition, the iterator of the container adopts interval programming with left closed and right open

This article is to understand the six components of STL, the classification of containers, as well as the characteristics of various containers, common methods and some usage scenarios. We’ll start learning practical algorithms in the next article.

Five, the data

  1. Tinking in C++
  2. “The c + + Primer”
  3. [Hou Jie c + + STL architecture and kernel analysis] : www.bilibili.com/video/BV1db… The images above are from this source.

Six, harvest

  1. Understand the six components of STL
  2. Understand the classification of sequential containers and associative containers
  3. Understand the characteristics, common methods, and advantages and disadvantages of various containers.

Thank you for reading

In the next chapter, we will start the learning practice of algorithms. Here we also set a flag, update one type of algorithm every day (traversal, search, sort, copy, replace, etc.), these basic knowledge is very important, let’s learn together.

Welcome to pay attention to the public account “audio and video development journey”, learn and grow together.

Welcome to communicate