C + + Standard Template Library

Container class


Take vector as an example

vector <int> a = {1,2,3,4,5};//Put the array {1,2,3,4,5} into the container class instance
vector <int> a = vector <int>(5); //Create a container class instance with 5 elements
vector <vector<int>> a = vector <vector<int>>(5);//Create a container class instance with 5 elements, and each instance is
//Is a container class

Create a container class


Via operator Random access to container classes

vector <int> a = { 1,2,3,4,5 };
for (vector <int>::iterator i = a.begin(); i != a.end(); i++)
	cout << *i << " ";
//1 2 3 4 5

Vector < int >:: iterator is an iterator whose function is similar to that of a pointer
begin() returns an iterator that points to the first element in the container
end() returns an iterator that exceeds the end of the container
push_back(T temp) adds an element to the end of the container class
erase(iterator a,iterator b) deletes all elements in the interval pointed to by iterator A and iterator b-1. [a,b)

vector <int> old_v = { 1,6,7,8,9,10, };
vector <int> new_v = {5,2,3,4,5 };
old_v.insert(old_v.begin() + 1, new_v.begin() + 1, new_v.end());
for (vector <int>::iterator i = old_v.begin(); i != old_v.end(); i++)
	cout << *i << " ";
//1 2 3 4 5 6 7 8 9 10

insert(iterator a,iterator b,iterator c) inserts the elements of the [b,c) interval at a


list <int> a ={1,2,3,4,5};
list <int>b = { 6,7,8,9,10 };
for(int i:a)
	cout<<i<<" ";

remove(const int & _val); Delete all values as_ Element of Val
remove_if(Pr1 _pred); Delete the element whose unary predicate is true
splice(iterator where, list b); Cut list B into a, and the elements in B will no longer exist.

list <int>a = {1,2,2,3,4,5 };

unique() can only compress adjacent duplicate values into one value. You can call sorting first and then compress to delete duplicate elements
sort() will sort the list
Supplement: for sort(),unique(),merge() can also accept a function parameter, which is called predicate (returned as bool value)

list <int> a = { 2,5,4,3,2,1, };
list <int>::iterator last = remove(a.begin(), a.end(), 2);
a.erase(last, a.end());
for (int i : a)
	cout << i << " ";

remove() puts the undeleted element at the head of the queue and returns an iterator that splits the new element and the deleted element
erase() deletes the first and second parameter intervals


valarray <int> a = { 2,5,4,3,2,1, };
cout << a.sum() << " ";
cout << a.min() << " ";
cout << a.max() << " ";
cout << a.size() << " ";
//17 1 5 6

The sum() min() max() size() function is as shown in the function name
Instead of expanding the memory size, resize() resets the size and the values in the array.
There are no iterators such as begin () and end () in valarray

valarray <int> a = { 2,5,4,3,2,1, };
for (int*  i = begin(a); i != end(a); i++)
	cout << *i << " ";

To enable valarray to also use the STL function, use the begin() and end() functions to return an iterator (pointer)
Operator > (), which will return a valarray array

alarray <int> b = a[slice(0, 3, 1)];

slice() is the slice class, #1 specifies the starting position, #2 specifies the number, and #3 specifies the step size


It implements a single linked list. It only needs a forward iterator. It is simpler and more compact, but it has few functions.


Queue, do not allow random access to queue elements, or even traversal of the queue

queue<int>a(deque<int> {1, 2, 3, 4, 5});
int top;
while (!a.empty())
	top = a.front();
	cout << top << " ";

empty() returns true if it is empty, otherwise false
size() returns the number of elements in the queue
front() returns a reference to the first element of the queue
back() returns a reference to the end of the queue element
Push (const T & x) inserts x at the end of the queue
pop() deletes the team leader element


Different from the queue, the largest element is always placed at the head of the queue, and an optional function parameter is provided to select the comparison method.


Stack, no more
empty() returns true if it is empty, otherwise false
size() returns the number of elements in the stack
top() returns a reference to the top element of the stack
Push (const T & x) inserts x at the top of the stack
pop() deletes the stack top element


It is not an STL container and its length is fixed, so it does not have some length related operations, such as adding an element at the end of the array and inserting an element at a certain position. However, many standard STL algorithms can be used for array objects, such as copy(),for_each()

Associated container

Its value is bound with the key, which is similar to the data structure designed in the database.
You can use the key to find the value.
Like an ordinary container, an associated container can also insert new elements, but it cannot specify the insertion location, because it has its own algorithm to determine the data location, so that it can quickly find data. The association container is generally realized by the data structure of tree, and its search speed is faster than that of linked list.


It is an associative set, reversible, sortable, and the key is unique. It cannot store multiple identical values

constexpr int N = 7;
string a[N] = { "tdd","tea","apple","banana","clock","dog","tdd"};
set<string> b(a, a + N);
ostream_iterator <string, char> out(cout, " ");
copy(b.begin(), b.end(), out);
//apple banana clock dog tdd tea

Set takes an iterator interval as a parameter to construct a set
Supplement: STL algorithm provides some mathematically set functions, such as union, intersection and difference set (Union intersection). These functions can naturally be used for set objects.
set_union() Union
set_ Intersection
set_difference() difference set

string strs1[7] = { "tdd","tea","apple","banana","clock","dog","tdd"};
string strs2[3] = { "tdd" ,"apple","banana" };
set<string> set1(strs1, strs1 + 7);
set<string> set2(strs2, strs2 + 3);
ostream_iterator <string, char> out(cout, " ");
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
//apple banana tdd

set_ The first two pairs of parameters of intersection are the ranges of two sets, and the last is the iterator output to. This output iterator can be an iterator that outputs to the screen. But cannot be set Begin(), because it is a constant iterator, and if the collection is not large enough, it will cause the program to crash, so you can use insert_ The iterator (C, c.begin()) converts replication to insertion

string strs1[7] = { "tdd","tea","apple","banana","clock","dog","tdd"};
set<string> set1(strs1, strs1 + 7);
cout << *set1.lower_bound("c") << endl;
cout << *set1.upper_bound("c");

lower_bund(key) returns the first value less than key
upper_bound(key) returns the first value greater than the key


Similar to set, it is also an inverted and sorted Association container, but the types of keys and values are different. One key can be associated with multiple values

multimap <int, string> codes;

Create a new multimap

pair<const int, string> item1(123, "BeiJing");

Create a pair object that can be added directly to the multimap


Add item1 to codes

pair<const int, string> item2(123, "HeFei");	

Let's add another one

cout << codes.count(123) << endl;

count(key) will return the number of values corresponding to the key. For example, 2 will be returned;
lower_bund(key) returns the first value less than key
upper_bound(key) returns the first value greater than the key
It is the same as set, but the iterator returned here is dereferenced as a pair object, so it is slightly different
equal_range(key): a pair object is returned here. There are two iterator objects in the object, which contain space equal to the key.

No associated container

For the well of the container, the unassociated container also associates the value with the key, but the difference between the underlying container and the associated container is that it is based on the data structure hash table, which is to improve the speed of adding and deleting elements.

Function object

Also known as function symbol, function symbol is any object that can be used in combination with () in a functional way, including function name, pointer to function and class object that overloads () operator.
That is, the current function also takes it as an object

template <class _Pr>
bool g(_Pr _Pred,const int & a)
	return  _Pred(a);

It can be compiled like this_ Pred is an object of class, which overloads the () operator. When g() is called, the function name can be passed as a parameter, that is, the function is also regarded as an object overloaded with the () operator.
What's more, using classes instead of function names can also pass parameters to different functions and functions with different limited numbers, such as book 708


It defines multiple template class function objects to solve the problem that operators cannot be passed into functions as function objects,

plus<double> add;
cout << add(1.3, 1.4);

Operator and corresponding function character p711

plus<double> add;
binder1st <plus<double>> g(add, 5);
cout << g(6);

It transforms the instance of the binary function add() into a unary function g(), where 5 is the first default parameter of the binary function, and it can be realized only if and only if add is an adaptive function -- although I don't know what it means.
It exists to simplify the code. Its function is the same as above, except that it directly returns a unary function instance.



void show(const int & a)
	cout << a << " ";
int main()
	vector <int> old_v = { 1,6,7,8,9,10,};
	for_each(old_v.begin(), old_v.end(), show);
	return 0;

for_each(iterator a,iterator b,f) calls the function f(*i) for the iterator interval [a,b);
Note for_ The each () function cannot modify the contents of the iteration, while the range for loop can be modified.


vector <int> old_v = {5,2,3,4,5 };
sort(old_v.begin(), old_v.end());
for_each(old_v.begin(), old_v.end(), show);
  • sort(iterator a,iterator b) sort the iterator interval [a,b) about < and note that the types in the container class should have functions that can handle operator < ().
  • sort(iterator a,iterator b,_pr _Pred)Pred is a comparison function that accepts the dereference of two iterator variables and returns a bool value


constexpr int N = 5;
vector <double> a = { 1,4,9,16,24 };
ostream_iterator <double, char> out(cout, " ");
transform<vector<double>::iterator, ostream_iterator<double,char>,double (*)(double)>(a.begin(), a.end(),out, sqrt);
//1 2 3 4 4.89898
  • transform() takes four parameters. The first and second specify the range, the third specifies the output stream, and the fourth specifies the unary (processing) function
  • transform() accepts five parameters, #1 and #2 specify interval 1, #3 is the starting position of interval 2, #4 is the output stream, #5 is a binary function


vector<int> vector1 = { 3,2,3,4,5,3,7 };
replace(vector1.begin(), vector1.end(), 3, 0);
for (vector<int>::iterator i = vector1.begin(); i != vector1.end(); i++)
	cout << *i <<  " ";
  • replace() accepts four parameters. The first and second specify the range, the third specifies the value to be replaced, and the fourth specifies the value to be replaced
    This is a local algorithm
  • replace_copy() is the copy version, but its third parameter specifies the starting iterator of the copy
  • replace_if() is the if version. Different from the original version, it has the last function parameter, which is used as the predicate function


string a = "abc";
sort(a.begin(), a.end());
cout << a << endl;
while (next_permutation(a.begin(), a.end()))
	cout << a << endl;

next_permutation() arranges intervals


  • Non modifying sequence operations: such as find(), for_ each()
  • Modified sequence operation: such as transform() rand_shuffle() copy()
  • Sorting and related operations: such as sort(), set_ Collection operations such as intersection()
  • General digital operation: content accumulation and internal product calculation
    The first three groups are located in the < alorithm > file and the last in the < numeric > file



list <int> a = { 2,5,4,3,2,1, };
cout<<count(a.begin(), a.end(), 2);

count() searches in the specified interval_ Number of val


For finding a specific element in an array / linked list, we can generalize the data type through generics, but our algorithm still depends on the specific class. Now we hope to completely separate our algorithm from not only the data type but also the stored data structure through a design, which gives birth to the iterator, which is like a generalization interface, Whether in the form of ordinary array storage or linked list storage, it is generalized into an iterator to traverse the data.
As an iterator, it meets at least the following conditions:

  • Dereference to iterator * p
  • Assign an iterator to another iterator p=q
  • Can compare, such as p==q, P= q
  • It can traverse all elements in the container, which can be realized by + + p,p + +
iterator operator++ ();//++p prefix version
iterator operator++ (int);//In the p + + suffix version, the parameter int here will never be used

As a programming style, it is best to avoid using iterators directly and use STL functions (for_each()) to handle details as much as possible,
You can also use the C++11 range based for loop

  • Input iterator: it can access all values in the container. It is a one-way iterator, which can be incremented but not reversed (single pass, read-only algorithm)
  • Output iterator: single pass, write only algorithm
  • Forward iterator: it always traverses a series of values in the same order. After the iterator is incremented, it can still dereference the previous iterator
  • Bidirectional iterators: have two orders
  • Random access iterator: can jump directly to any element in the container

Pointers are also an implementation of iterators, so

int a[] = { 5,4,3,2,1 };
sort(&a[0], &a[5]);
for (int i = 0; i < 5; i++)
	cout << a[i] << " ";
//1 2 3 4 5

copy(iterator a,iterator b,iterator c) copies the interval [a,b) to c, starting with c

int a[] = { 5,4,3,2,1 };
vector <int> b(10);
ostream_iterator <int, char> out_iter(cout, " ");
copy(&a[0], &a[5], b.begin());
copy(b.begin(), b.end(), out_iter);
//5 4 3 2 1 0 0 0 0 0

The output iterator first creates an array a, then creates a vector b with a length of 10 and declares an out_ ITER output iterator, which means that cout is used as the output stream, and "" is used as the delimiter after being sent to the output stream each time. Then, the program copies the value of a into b, and then uses out_iter to display the value of b.
ostream_iterator is an output iterator that uses two template parameters. The first is the data type sent to the output stream, and the second is the data type used by the output stream.

int a[5] = { 1,2,3,4,5 };
copy(istream_iterator<int, char>(cin), istream_iterator<int, char>(), a);
for (int i = 0; i < 5; i++)
	cout << a[i] << " ";
//<-1 2 3 4 j
//->1 2 3 4 1

Typical representation of input iterators, istream_ The iterator uses two template parameters, the first is the data type to be read, that is, the data type written into the program (target data type), the second is the data type used by the input stream, the function parameter is cin, that is, the input stream managed by cin, and istream_iterator < int, char > () represents input failure
Other iterators

vector <int>a = { 1,2,3,4,5 };
copy(a.rbegin(), a.rend(), ostream_iterator<int, char>(cout, " "));

rbegin() is a reverse iterator, which actually points to the super tail element
rend() is a reverse iterator that actually points to the first element
The + + operation for the reverse iterator is the - operation of the normal iterator. By using the reverse iterator, you can reuse the + + code containing copy() and complete the reverse printing operation.
insert iterator
back_insert_iterator: insert elements into the end of the container. Only containers for quick insertion are allowed
front_insert_iterator: insert elements into the container header. Only container types that are allowed to be inserted for a fixed time are allowed
insert_iterator: inserts an element into the container at a location that is controlled by insert_ The constructor of the iterator determines

vector <int>a = { 1,2,3,4,5 };
vector <int>b = { 6,7,8,9,10 };
back_insert_iterator<vector<int>> back_iter(a);
copy(b.begin(), b.end(), back_iter);
for (int i : a)
	cout << i << " ";
//->1 2 3 4 5 6 7 8 9 10

back_ insert_ The iterator has a template parameter. Pass in our template and let it select the appropriate container method. At the same time, pass the container as a parameter so that it can use a push like method_ copy() is an independent function. It can't use some adding methods of the container, but it can be used indirectly by inserting an iterator.

vector <int>a = { 1,2,3,4,5 };
vector <int>b = { 6,7,8,9,10 };
insert_iterator<vector<int>>  insert_iter (a, a.begin()+1);
copy(b.begin(), b.end(),insert_iter);
for (int i : a)
	cout << i << " ";

insert_ The iterator accepts a template parameter, a container class, and a pointer to a specific location of the container class

Container type

  1. The object of the container cannot be of any type. To be exact, its type must have replicable construction and assignable.

Other libraries

  1. The difference between vector and valarray
  • vector is a part of the container class and algorithm system. It supports container operations, such as sorting, inserting, rearranging, searching and transferring containers
  • The valarray class template is numerical oriented, but it does not push_back() and insert()
  • Array is to replace the built-in array. It is more secure than the built-in array. It is a fixed length array, so it does not support push_back() and insert(), but it has multiple STL methods, begin(), end(), rbegin(), and render()
vector <int> ved1;
array<double,10> vod1;
valarray<double> vad1;


vector <int> a{1,2,3,4};//<=>vector <int> a({1,2,3,4});

Initializer is added in C++11_ List, which is initialized with an indefinite length array
But {} can also be used for initialization

A a{1,2,3};//<=>A a(1,2,3);

Therefore, C + + stipulates that if the class has an initializer_list syntax, for {} initialization, it is agreed to make {} initialization syntax instead of the substitution of ()

Using initializer in code_ List initialization syntax, you can use the member function begin(),end() to access elements, and size() to return the number of elements.
initializer_list is literal, so initializer cannot be modified_ Values in list

T g(initializer_list<T> il) 
	T sum = 0;
	for (const T* i = il.begin(); i != il.end(); i++)
		sum += *i;
	return sum;

int main()

	cout << g<int>({1, 2, 3, 4, 5});


Keywords: C++ STL

Added by blufish on Mon, 20 Dec 2021 23:34:40 +0200