Cpp Standard Library 简明教程

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素的理论元素后的迭代器。

O(1)

返回存在的元素数量。

O(1)

如果 vector 为空则返回 true，否则返回 false。

O(1)

at()

返回特定位置的元素。

O(1)

assign()

为 vector 元素分配一个新值。

O(n)

push_back()

在 vector 的末尾添加一个元素。

O(1)

pop_back()

从末尾删除一个元素。

O(1)

在指定位置插入一个元素。

O(n)

10.

删除特定位置或范围内的元素。

O(n)

11.

clear()

Removes all elements.

O(n)

此处，TC 表示 vector 模板的不同成员函数的时间复杂性。有关时间复杂性的更多信息，请访问此文章 − 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> 头文件找到它。

list<data_type> list1;

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

S.No.

Function

Function Explanation

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素的理论元素后的迭代器。

O(1)

返回列表中的元素数量。

O(1)

push_back()

在列表末尾添加一个元素。

O(1)

pop_back()

从尾部移除一个元素。

O(1)

push_front()

在列表的前面添加一个元素。

O(1)

pop_front()

从头部移除一个元素。

O(1)

在指定位置插入一个元素。

O(n)

删除指定位置的元素。

O(n)

10.

remove()

从列表中移除所有给定元素的副本。

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> 头文件中找到。

deque<data_type> dq1;

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

S.No.

Function

Function Explanation

返回到第一个元素的迭代器。

O(1)

返回指向最后一个元素的理论元素后的迭代器。

O(1)

at()

Access specified element.

O(1)

[ ]

访问给定索引处的元素。

O(1)

front()

Returns the first element.

O(1)

back()

Returns the last element.

O(1)

返回元素数量。

O(1)

push_back()

在末尾添加元素。

O(1)

pop_back()

从末尾移除元素。

O(1)

10.

push_front()

在前面添加元素。

O(1)

11.

pop_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> 头文件中找到。

stack<data_type> s1;

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

S.No.

Function

Function Explanation

如果栈为空，则返回 true，否则返回 false。

O(1)

返回栈中的元素数量。

O(1)

top()

Returns the top element.

O(1)

push(x)

在堆栈中推送一个元素。

O(1)

pop()

从堆栈中移除一个元素。

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> 头文件中找到。

queue<data_type> q1;

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

S.No.

Function

Function Explanation

如果队列为空，则返回 true，否则返回 false。

O(1)

返回队列中的项目数。

O(1)

front()

Returns the front element.

O(1)

back()

返回末尾的元素。

O(1)

push()

向队列添加一个项目。

O(1)

pop()

从队列中移除一个项目。

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> 头文件中找到。

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 中有不同的函数。它们在下面的表中进行简要解释 −

S.No.

Function

Function Explanation

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素的迭代器。

O(1)

返回元素数量。

O(1)

检查容器是否为空。

O(1)

Inserts a single element.

O(logn)

Removes the given element.

O(logn)

clear()

Removes all elements.

O(n)

find()

如果存在，则返回指向给定元素的指针，否则返回指向末尾的指针。

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> 头文件中。

map<key_type,value_type> map;

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

S.No.

Function

Function Explanation

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素之后的理论元素的迭代器

O(1)

返回映射中的元素数

O(1)

向映射中添加一个新元素。

O(logn)

erase(iterator)

删除迭代器所指向位置的元素。

O(logn)

erase(key)

删除键及其值从映射。

O(logn)

clear()

删除地图中的所有元素。

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> 头文件实现。

unordered_set<data_type> set;

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

S. No.

Functions

Description

Time Complexity

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素之后的理论元素的迭代器

O(1)

返回元素数量。

O(1)

如果无序集为空，则返回 true，否则返回 false。

O(1)

在容器中插入一项。

O(1)

从容器中移除一个元素。

O(1)

find()

如果存在，则返回指向给定元素的指针，否则返回指向末尾的指针。

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> 标头文件中。

unordered_map<key_type, value_type> map;

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

S. No.

Function

Description

Time Complexity

返回指向第一个元素的迭代器。

O(1)

返回指向最后一个元素之后的理论元素的迭代器

O(1)

返回元素数量。

O(1)

如果无序映射为空，则返回 true，否则返回 false。

O(1)

find()

如果存在，则返回指向给定元素的指针，否则返回指向末尾的指针。

O(1)

bucket()

返回数据存储的存储桶编号。

O(1)

在容器中插入一项。

O(1)