Cpp Standard Library 简明教程

Returns an iterator to the first element.

O(1)

Returns an iterator to the theoretical element after the last element.

O(1)

Returns the number of elements present.

O(1)

Returns true if the vector is empty, false otherwise.

O(1)

at()

Return the element at a particular position.

O(1)

assign()

Assign a new value to the vector elements.

O(n)

push_back()

Adds an element to the back of the vector.

O(1)

pop_back()

Removes an element from the end.

O(1)

Insert an element at the specified position.

O(n)

10.

Delete the elements at a specified position or range.

O(n)

11.

clear()

Removes all elements.

O(n)

此处，TC 表示 vector 模板的不同成员函数的时间复杂性。有关时间复杂性的更多信息，请访问此文章 − Time complexity 。

Here, TC indicates time complexity of different member functions of the vector template. For more information on time complexity, visit this article − Time complexity.

// C++ program to illustrate the vector container
#include <iostream>
#include <vector>
using namespace std;

int main(){
   int n=2;
   vector<int> vec1 = { 1, 2, 3, 4, 5 };
   vector<int> vec2(n,0);

   vector<vector<int>> vec3(n,vector<int>(2*n,1));

   vec1.push_back(6);

   cout << "vec1: ";
   for (int i = 0; i < vec1.size(); i++) {
      cout << vec1[i] << " ";
   }
   cout << endl<<"vec2: ";
   for (int i = 0; i < vec2.size(); i++) {
      cout << vec2[i] << " ";
   }
   cout << endl;

   vec1.erase(vec1.begin() + 4);

   cout << "vec1 after erasing: ";
   for (auto i = vec1.begin(); i != vec1.end(); i++) {
      cout << *i << " ";
   }
   cout << endl;

   cout << "vec3:-" << endl;
   for (auto i : vec3) {
      for (auto j : i) {
         cout << j << " ";
      }
      cout << endl;
   }
   cout << endl;

   vector<pair<int,int>> vec4;
   vec4.push_back({2,3});
   vec4.push_back({4,3});

   cout<<"vector of pairs, vec4 : "<<endl;
   for(auto i: vec4){
      cout<<i.first<<" "<<i.second<<endl;
   }
   return 0;
}

vec1: 1 2 3 4 5 6
vec2: 0 0
vec1 after erasing: 1 2 3 4 6
vec3:-
1 1 1 1
1 1 1 1

vector of pairs, vec4 :
2 3
4 3

List in STL

list 容器初始化为 doubly linked list ，而对于实现 singly linked list ，我们使用 forward_list 。可在 C++ <list> 头文件找到它。

The list container is initialized as a doubly linked list, whereas for implementing a singly linked list, we use a forward_list. It can be found in the C++ <list> header file.

list<data_type> list1;

list template 中有不同的函数。这些函数在下面的表中得到简要解释 −

There are different functions in the list template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Return the iterator to the first element.

O(1)

Returns an iterator to the theoretical element after the last element.

O(1)

Returns the number of elements in the list.

O(1)

push_back()

Adds one element at the end of the list.

O(1)

pop_back()

Removes a single element from the end.

O(1)

push_front()

Adds a single element to the front of the list.

O(1)

pop_front()

Removes a single element from the front.

O(1)

Inserts an element at the specified position.

O(n)

Deletes the element at the given position.

O(n)

10.

remove()

Removes all the copies of the given elements from the list.

O(n)

#include <iostream>
#include <list>
#include <vector>
using namespace std;

int main(){
   list<int> list1 = { 1, 5, 9, 1, 4, 6 };

   cout << "List1 first and last element: " << list1.front() <<" "<<list1.back()<<endl;

   // adding element
   list1.insert(list1.begin(), 5);

   // deleting element
   list1.erase(list1.begin());

   // traversing list1
   cout << "list1: ";
   for (auto i = list1.begin(); i != list1.end(); i++) {
      cout << *i << " ";
   }
   cout << endl;

   return 0;
}

List1 first and last element: 1 6
list1: 1 5 9 1 4 6

Deque in STL

deque 容器被初始化为 doubly ended queue ，元素可以从队列的两端进行压入和弹出。它可以在 C++ <deque> 头文件中找到。

The deque container is initialized as a doubly ended queue, where elements can be pushed and popped from both ends of the queue. It can be found in the C++ <deque> header file.

deque<data_type> dq1;

deque template 中有不同的函数。这些函数在下面的表格中进行了简要说明 −

There are different functions in the deque template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Returns iterator to the first element.

O(1)

Returns an iterator to the theoretical element after the last element.

O(1)

at()

Access specified element.

O(1)

[ ]

Access element at the given index.

O(1)

front()

Returns the first element.

O(1)

back()

Returns the last element.

O(1)

Returns the number of elements.

O(1)

push_back()

Add the elements at the end.

O(1)

pop_back()

Removes the elements from the end.

O(1)

10.

push_front()

Add the elements at the front.

O(1)

11.

pop_front()

Removes the element from the front.

O(1)

#include <deque>
#include <iostream>
using namespace std;

int main(){

   deque<int> dq = { 1, 2, 3, 4, 5 ,6, 8 };
   cout<<"Initial Deque: "<<endl;
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;
   dq.push_front(dq.back());
   dq.pop_back();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.push_front(dq.back());
   dq.pop_back();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.pop_back();
   dq.pop_front();
   for (auto i : dq) {
      cout << i << " ";
   }
   cout<<endl;

   dq.push_front(11);
   dq.push_back(99);

   for (auto i : dq) {
      cout << i << " ";
   }

   return 0;
}

Initial Deque:
1 2 3 4 5 6 8
8 1 2 3 4 5 6
6 8 1 2 3 4 5
8 1 2 3 4
11 8 1 2 3 4 99

Stack in STL

栈容器被初始化为 LIFO container ，元素可以压入顶部，并从顶部弹出。因此，最后一个进入栈的元素是第一个从容器中退出的元素。它可以在 C++ <stack> 头文件中找到。

The stack container is initialized as a LIFO container, where elements can be pushed to the top, and popped from the top. Hence, the last element to enter is the first one to exit from the container. It can be found in the C++ <stack> header file.

stack<data_type> s1;

stack template 中有不同的函数。这些函数在下面的表格中进行了简要说明 −

There are different functions in the stack template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Returns true if the stack is empty, false otherwise.

O(1)

Returns the number of elements in the stack.

O(1)

top()

Returns the top element.

O(1)

push(x)

Push one element in the stack.

O(1)

pop()

Removes one element from the stack.

O(1)

// C++ Program to illustrate the stack
#include <bits/stdc++.h>
using namespace std;

int main(){
   stack<int> s;

   s.push(2);
   s.push(9);
   s.push(3);
   s.push(1);
   s.push(6);

   cout << "Top is: " << s.top() << endl;

   while (!s.empty()) {
      cout<<"size is: "<<s.size()<<" ";
      cout << "element is: "<<s.top() << endl;
      s.pop();
   }
   return 0;
}

Top is: 6
size is: 5 element is: 6
size is: 4 element is: 1
size is: 3 element is: 3
size is: 2 element is: 9
size is: 1 element is: 2

Queue in STL

队列容器初始化为 FIFO container ，其中可以将元素推送到前面，并从前面弹出。因此，第一个进入的元素是第一个从容器中退出的元素。它可以在 C++ <queue> 头文件中找到。

The queue container is initialized as a FIFO container, where elements can be pushed to the front, and popped from the front. Hence, the first element to enter is the first one to exit from the container. It can be found in the C++ <queue> header file.

queue<data_type> q1;

queue template 中有不同的函数。它们在下面的表中进行简要解释 −

There are different functions in the queue template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Returns true if the queue is empty, otherwise false.

O(1)

Returns the number of items in the queue.

O(1)

front()

Returns the front element.

O(1)

back()

Returns the element at the end.

O(1)

push()

Add an item to the queue.

O(1)

pop()

Removes an item from the queue.

O(1)

#include <iostream>
#include <queue>
using namespace std;

int main(){
   queue<int> q;
   q.push(1);
   q.push(1);
   q.push(6);
   q.push(1);

   cout << "Front element: " << q.front() << endl;
   cout << "Back element: " << q.back() << endl;

   cout << "q: ";
   int size = q.size();

   for (int i = 0; i < size; i++) {
      cout << q.front() << " ";
      q.pop();
   }

   return 0;
}

Front element: 1
Back element: 1
q: 1 1 6 1

Hash-Set/Set in STL

集合容器被初始化为唯一元素存储数据结构，它还实现了排序顺序，既可以升序也可以降序。它通常实现 red-black tree 作为底层数据结构。它可以在 C++ <set> 头文件中找到。

The set container is initialized as unique element storage data structure, which also implements a sorted order, both ascending and descending. It generally implements a red-black tree as an underlying data structure. It can be found in the C++ <set> header file.

set<data_type> set;
set<data_type, greater<data_type>> set2; //this is a set in descending order
set<data_type, comparator/lambda_function> set3; //this is a set in custom order

set template 中有不同的函数。它们在下面的表中进行简要解释 −

There are different functions in the set template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Returns an iterator to the first element.

O(1)

Return an iterator to the last element.

O(1)

Returns the number of elements.

O(1)

Checks if the container is empty.

O(1)

Inserts a single element.

O(logn)

Removes the given element.

O(logn)

clear()

Removes all elements.

O(n)

find()

Returns the pointer to the given element if present, otherwise, a pointer to the end.

O(logn)

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main(){
   set<int> set;
   set.insert(9);
   set.insert(11);
   set.insert(9);
   set.insert(11);

   bool flag=set.find(9)!=set.end();

   cout<<"Is there a 9 in the set? "<<flag<<endl;

   set.insert(21);

   for (auto i : set) {
      cout << i << " ";
   }
   cout << endl;
   return 0;
}

Is there a 9 in the set? 1
9 11 21

Hash-Map/Map in STL

映射是一个容器，它以密钥的排序顺序以键值对的形式存储数据，其中每个密钥都是唯一的。它使用红黑树数据结构实现。它包含在 <map> 头文件中。

The map is a container which stores data in form of key-value pairs in a sorted order of keys, where each key is unique. It is implemented using the red-black tree data structure. It is included in the <map> header file.

map<key_type,value_type> map;

map template 中有不同的函数。它们在下面的表中进行简要解释 −

There are different functions in the map template. These are explained briefly in the table below −

S.No.

Function

Function Explanation

Returns an iterator to the first element.

O(1)

Returns an iterator to the theoretical element that follows the last element

O(1)

Returns the number of elements in the map

O(1)

Adds a new element to the map.

O(logn)

erase(iterator)

Removes the element at the position pointed by the iterator.

O(logn)

erase(key)

Removes the key and its value from the map.

O(logn)

clear()

Removes all the elements from the map.

O(n)

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
   map<char,int> map;
   string s="abbacdbbac";
   for(char c: s){
      map[c]++;
   }

   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   cout<<"after erasing element 'c' : "<<endl;
   map.erase('c');
   for(auto it:map){
      cout<<it.first<<" : "<<it.second<<endl;
   }
   return 0;
}

a : 3
b : 4
c : 2
d : 1
after erasing element 'c' :
a : 3
b : 4
d : 1

Unordered Set in STL

无序集容器存储唯一的数值，但与 set 的唯一区别是数据不会以任何顺序存储。它使用 <unordered_set> 头文件实现。

The unordered_set container stores unique data values in it, but the only difference from set is that the data is not stored in any order. It is implemented using the <unordered_set> header file.

unordered_set<data_type> set;

unordered_set template 中有不同的函数。下表对其作了简要说明：

There are different functions in the unordered_set template. These are explained briefly in the table below −

S. No.

Functions

Description

Time Complexity

Returns an iterator to the first element.

O(1)

Returns an iterator to the theoretical element that follows the last element

O(1)

Returns the number of elements.

O(1)

Returns true if the unordered_set is empty, otherwise false.

O(1)

Insert an item in the container.

O(1)

Removes an element from the container.

O(1)

find()

Returns the pointer to the given element if present, otherwise, a pointer to the end.

O(1)

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int main(){
   unordered_set<int> set;
   set.insert(19);
   set.insert(10);
   set.insert(13);
   set.insert(21);

   bool flag=set.find(9)!=set.end();

   cout<<"Is there a 9 in the set? "<<flag<<endl;

   set.insert(21);

   for (auto i : set) {
      cout << i << " ";
   }
   cout << endl;
   return 0;
}

Is there a 9 in the set? 0
21 13 10 19

Unordered Map in STL

在无序映射容器中，数据的存储类似于映射容器，但存储数据的顺序是随机的，因此不遵循升序或降序。它包含在 <unordered_map> 标头文件中。

In the unordered_map container, the data is stored similar to the map container, but the order of the data stored is random, hence, ascending or descending order is not followed. It is included in the <unordered_map> header file.

unordered_map<key_type, value_type> map;

unordered_map template 中有不同的函数。下表对其作了简要说明：

There are different functions in the unordered_map template. These are explained briefly in the table below −

S. No.

Function

Description

Time Complexity

Returns an iterator to the first element.

O(1)

Returns an iterator to the theoretical element that follows the last element

O(1)

Returns the number of elements.

O(1)

Returns true if the unordered_map is empty, otherwise false.

O(1)

find()

Returns the pointer to the given element if present, otherwise, a pointer to the end.

O(1)

bucket()

Returns the bucket number where the data is stored.

O(1)

Insert an item in the container.

O(1)