C++STL常用容器

C++ STL

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

C++ 标准模板库的核心包括以下三个组件：

• 容器（Containers）: 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。

• 算法（Algorithms）: 算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。

• 迭代器（iterators）: 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。

C++ STL常用容器

• vector：向量

• stack：栈

• set：集合

• queue：队列

• list：双向链表

• map：地图

• string：字符串

• deque：双端队列

• priority_queue：优先队列

对于容器，主要的操作有：

• 容器的建立

• 插入元素

• 删除元素

• 查询

• 遍历

• 计算元素个数

• 检查元素是否为空

• 输出容器包含的内容

vector

vector包含着一系列连续存储的元素,其行为和数组类似。访问Vector中的任意元素或从末尾添加元素都可以在常量级时间复杂度内完成，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度。

构造函数:

• vector(); 无参数 - 构造一个空的vector

• vector(size_type num); 数量(num) - 构造一个大小为num，值为Type默认值的Vector

• vector(size_type num, const TYPE &val); 数量(num)和值(val) - 构造一个初始放入num个值为val的元素的Vector

• vector(const vector &from); vector(from) - 构造一个与vector from 相同的vector

• vector(input_iterator start, input_iterator end); 迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).

• vector(initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

  C++11新提供的方法，类似如下方式：

  • std::vector<int>a{1, 2, 3, 4, 5};

  • std::vector<int>a = {1, 2, 3, 4, 5};

常用API：

• Operators : 对vector进行赋值或比较

  • v1 == v2
  • v1 != v2
  • v1 <= v2
  • v1 >= v2
  • v1 < v2
  • v1 > v2
  • v[]

• assign()对Vector中的元素赋值

• at() : 返回指定位置的元素

• back() : 返回最末一个元素

• begin() : 返回第一个元素的迭代器

• capacity() : 返回vector所能容纳的元素数量(在不重新分配内存的情况下）

• clear() : 清空所有元素

• empty() : 判断Vector是否为空（返回true时为空）

• end() : 返回最末元素的迭代器(译注:实指向最末元素的下一个位置)

• erase() : 删除指定元素

• front() : 返回第一个元素

• get_allocator() : 返回vector的内存分配器

• insert() : 插入元素到Vector中

• max_size() : 返回Vector所能容纳元素的最大数量（上限）

• pop_back() : 移除最后一个元素

• push_back() : 在Vector最后添加一个元素

• rbegin() : 返回Vector尾部的逆迭代器

• rend() : 返回Vector起始的逆迭代器

• reserve() : 设置Vector最小的元素容纳数量

• resize() : 改变Vector元素数量的大小

• size() : 返回Vector元素数量的大小

• swap() : 交换两个Vector

stack

C++ stack（堆栈）实现了一个先进后出（FILO）的数据结构。

构造函数：

• stack<T> stkT; : 采用模板类实现，stack对象的默认构造形式

• stack(const stack &stk); : 拷贝构造函数

常用方法：

• size(): 返回栈中的元素数

• top(): 返回栈顶的元素

• pop(): 从栈中取出并删除元素

• push(x): 向栈中添加元素x

• empty(): 在栈为空时返回true

set

Sets are containers that store unique elements following a specific order.

集合中以一种特定的顺序保存唯一的元素。

构造函数:

• set(); 无参数 - 构造一个空的set

• set(InputIterator first, InputIterator last) : 迭代器的方式构造set

• set(const set &from); : copyd的方式构造一个与set from 相同的set

• set(input_iterator start, input_iterator end); 迭代器(start)和迭代器(end) - 构造一个初始值为[start,end)区间元素的Vector(注:半开区间).

• set (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

  C++11新提供的方法，类似如下方式：

  • std::set<int>a{1, 2, 3, 4, 5};

// constructing sets
#include <iostream>
#include <set>

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

struct classcomp {
  bool operator() (const int& lhs, const int& rhs) const
  {return lhs<rhs;}
};

int main ()
{
  std::set<int> first;                           // empty set of ints

  int myints[]= {10,20,30,40,50};
  std::set<int> second (myints,myints+5);        // range

  std::set<int> third (second);                  // a copy of second

  std::set<int> fourth (second.begin(), second.end());  // iterator ctor.

  std::set<int,classcomp> fifth;                 // class as Compare

  bool(*fn_pt)(int,int) = fncomp;
  std::set<int,bool(*)(int,int)> sixth (fn_pt);  // function pointer as Compare

  return 0;
}

常用API：

• begin() : 返回指向第一个元素的迭代器

• clear() : 清除所有元素

• count() : 返回某个值元素的个数

• empty() : 如果集合为空，返回true

• end() : 返回指向最后一个元素的迭代器

• equal_range() : 返回集合中与给定值相等的上下限的两个迭代器

• erase() : 删除集合中的元素

• find() : 返回一个指向被查找到元素的迭代器

• get_allocator() : 返回集合的分配器

• insert() : 在集合中插入元素

• lower_bound() : 返回指向大于（或等于）某值的第一个元素的迭代器

• key_comp() : 返回一个用于元素间值比较的函数

• max_size() : 返回集合能容纳的元素的最大限值

• rbegin() : 返回指向集合中最后一个元素的反向迭代器

• rend() : 返回指向集合中第一个元素的反向迭代器

• size() : 集合中元素的数目

• swap() : 交换两个集合变量

• upper_bound() : 返回大于某个值元素的迭代器

• value_comp() : 返回一个用于比较元素间的值的函数

queue

C++队列是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。

构造函数：

• explicit queue (const container_type& ctnr);

• explicit queue (container_type&& ctnr = container_type());

• template <class Alloc> explicit queue (const Alloc& alloc);

• template <class Alloc> queue (const container_type& ctnr, const Alloc& alloc);

• template <class Alloc> queue (container_type&& ctnr, const Alloc& alloc);

• template <class Alloc> queue (const queue& x, const Alloc& alloc);

• template <class Alloc> queue (queue&& x, const Alloc& alloc);

// constructing queues
#include <iostream>       // std::cout
#include <deque>          // std::deque
#include <list>           // std::list
#include <queue>          // std::queue

int main ()
{
  std::deque<int> mydeck (3,100);        // deque with 3 elements
  std::list<int> mylist (2,200);         // list with 2 elements

  std::queue<int> first;                 // empty queue
  std::queue<int> second (mydeck);       // queue initialized to copy of deque

  std::queue<int,std::list<int>> third; // empty queue with list as underlying container
  std::queue<int,std::list<int>> fourth (mylist);

  std::cout << "size of first: " << first.size() << '\n';
  std::cout << "size of second: " << second.size() << '\n';
  std::cout << "size of third: " << third.size() << '\n';
  std::cout << "size of fourth: " << fourth.size() << '\n';

  return 0;
}

size of first: 0
size of second: 3
size of third: 0
size of fourth: 2

常用API：

• back() : 返回最后一个元素

• empty() : 如果队列空则返回真

• front() : 返回第一个元素

• pop() : 删除第一个元素

• push() : 在末尾加入一个元素

• size() : 返回队列中元素的个数

list

Lists将元素按顺序储存在链表中. 与 向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢.

构造函数：

• list (const allocator_type& alloc = allocator_type());

• list (size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type());

• template <class InputIterator> list (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());

• list (const list& x);

常用API：

• assign() : 给list赋值

• back() : 返回最后一个元素

• begin() : 返回指向第一个元素的迭代器

• clear() : 删除所有元素

• empty() : 如果list是空的则返回true

• end() : 返回末尾的迭代器

• erase() : 删除一个元素

• front() : 返回第一个元素

• get_allocator() : 返回list的配置器

• insert() : 插入一个元素到list中

• max_size() : 返回list能容纳的最大元素数量

• merge() : 合并两个list

• pop_back() : 删除最后一个元素

• pop_front() : 删除第一个元素

• push_back() : 在list的末尾添加一个元素

• push_front() : 在list的头部添加一个元素

• rbegin() : 返回指向第一个元素的逆向迭代器

• remove() : 从list删除元素

• remove_if() : 按指定条件删除元素

• rend() : 指向list末尾的逆向迭代器

• resize() : 改变list的大小

• reverse() : 把list的元素倒转

• size() : 返回list中的元素个数

• sort() : 给list排序

• splice() : 合并两个list

• swap() : 交换两个list

• unique() : 删除list中重复的元素

map

C++ Maps是一种关联式容器，包含“关键字/值”对

构造函数：

• map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

• template <class InputIterator> map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& = allocator_type());

• map (const map& x);

• map (const map& x, const allocator_type& alloc);

• map (map&& x);

• map (map&& x, const allocator_type& alloc);

• map (initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());

// constructing maps
#include <iostream>
#include <map>

bool fncomp (char lhs, char rhs) {return lhs<rhs;}

struct classcomp {
  bool operator() (const char& lhs, const char& rhs) const
  {return lhs<rhs;}
};

int main ()
{
  std::map<char,int> first;

  first['a']=10;
  first['b']=30;
  first['c']=50;
  first['d']=70;

  std::map<char,int> second (first.begin(),first.end());

  std::map<char,int> third (second);

  std::map<char,int,classcomp> fourth;                 // class as Compare

  bool(*fn_pt)(char,char) = fncomp;
  std::map<char,int,bool(*)(char,char)> fifth (fn_pt); // function pointer as Compare

  return 0;
}

常用API：

• begin() : 返回指向map头部的迭代器

• clear() : 删除所有元素

• count() : 返回指定元素出现的次数

• empty() : 如果map为空则返回true

• end() : 返回指向map末尾的迭代器

• equal_range() : 返回特殊条目的迭代器对

• erase() : 删除一个元素

• find() : 查找一个元素

• get_allocator() : 返回map的配置器

• insert() : 插入元素–

• key_comp() : 返回比较元素key的函数

• lower_bound() : 返回键值>=给定元素的第一个位置

• max_size() : 返回可以容纳的最大元素个数

• rbegin() : 返回一个指向map尾部的逆向迭代器

• rend() : 返回一个指向map头部的逆向迭代器

• size() : 返回map中元素的个数

• swap() : 交换两个map

• upper_bound() : 返回键值>给定元素的第一个位置

• value_comp() : 返回比较元素value的函数

string

string构造函数

• string();//创建一个空的字符串

• string(const string& str);//使用一个string对象初始化另一个string对象

• string(const char* s);//使用字符串s初始化

• string(int n,char c);//使用n个字符c初始化

string基本赋值操作

• string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串

• string& operator=(const string &s);//把字符串s赋值给当前的字符串

• string& operator=(char c);//字符赋值给当前的字符串

• string& assign(const char* s);//把字符串s赋值给当前的字符串

• string& assign(const char* s,int n);//把字符串s的前n个字符赋值给当前的字符串

• string& assign(const string &s);//把字符串s赋值给当前的字符串

• string& assign(int n,char c);//用n个字符c赋值给当前字符串

• string& assign(const string &s,int start,int n);//将s从start开始n个字符赋值给字符串

string存取字符操作

• char& operator[](int n);//通过[]方式取字符

• char& at(int n);//通过at方法获取字符

string拼接操作

• string& operator+=(const string& str);//重载+=运算符

• string& operator+=(const char* str);//重载+=运算符

• string& operator+=(const char c);//重载+=运算符

• string& append(const char *s);//把字符串s连接到当前字符串结尾

• string& append(const char *s,int n);//把字符串s的前n个字符连接到当前字符串结尾

• string& append(const string &s);//同operator+=（）

• string& append(const string &s,int pos,int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾

• string& append(int n,char c);//在当前字符串结尾添加n个字符c

string查找和替换

• int find(const string& str,int pos = 0)const;//查找str第一次出现的位置，从pos开始查找

• int find(const char* s,int pos = 0)const;//查找s第一次出现位置，从pos开始查找

• int find(const char *s,int pos,int n)const;//从pos位置查找s的前n个字符第一次位置

• int find(const char c,int pos = 0)const;//查找字符c第一次出现位置

• int rfind(const string& str, int pos = npos)const;//查找str最后一次出现位置，从pos开始查找

• int rfind(const char* s,int pos = npos)const;//查找s最后一次出现位置，从pos开始查找

• int rfind(const char* s,int pos,int n )const;//从pos查找s的前n个字符最后一次位置

• int rfind(const char c,int pos = 0)const;//查找字符c最后一次出现位置

• string& replace(int pos,int n,const string& str);//替换从pos开始的n个字符为字符串str

• string& replace(int pos,int n,const char* s);//替换从pos开始的n个字符为字符串s

string 比较操作

• int compare(const string &s)const;//与字符串s比较

• int compare(const char*s)const;//与字符串s比较

• compare函数在>时返回1，<时返回-1，相等时返回0，比较区分大小写，逐个字符比较

string子串

• string substr(int pos = 0,int n = npos)const;//返回由pos开始的n个字符组成的字符串

string插入和删除操作

• string& insert(int pos,const char* s);//插入字符串

• string& insert(int pos,const string &str);//插入字符串

• string& insert(int pos,int n,char c);//在指定位置插入n个字符c

• string& erase(int pos,int n = npos);//删除从pos开始的n个字符

deque

deque是Double-Ended Queues(双向队列)的缩写。

双向队列和向量很相似，但是它允许在容器头部快速插入和删除（就像在尾部一样）。

deque构造函数

• deque<T> queT;//queue采用模板类实现，queue对象的默认构造形式

• deque<T> queT(size);//构造大小为size的deque，其中值为T类型的默认值

• deque<T> queT(size, val);//构造大小为size的deque，其中值为val

• deque(const deque &que);//拷贝构造函数

• deque(input_iterator start, input_iterator end);//迭代器构造函数

// constructing deques
#include <iostream>
#include <deque>

int main ()
{
  unsigned int i;

  // constructors used in the same order as described above:
  std::deque<int> first;                                // empty deque of ints
  std::deque<int> second (4,100);                       // four ints with value 100
  std::deque<int> third (second.begin(),second.end());  // iterating through second
  std::deque<int> fourth (third);                       // a copy of third

  // the iterator constructor can be used to copy arrays:
  int myints[] = {16,2,77,29};
  std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  std::cout << "The contents of fifth are:";
  for (std::deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

The contents of fifth are: 16 2 77 29 

deque存取、插入和删除操作

• back();//返回最后一个元素

• front();//返回第一个元素

• insert();//

• pop_back();//删除尾部的元素

• pop_front();//删除头部的元素

• push_back();//在尾部加入一个元素

• push_front();//在头部加入一个元素

• at();//访问指定位置元素

注：queue只有push和pop方法，在尾部加入和删除元素。

deque赋值操作

• operator[] (size_type n);//重载[]操作符

deque大小操作

• empty();//判断队列是否为空

• size();//返回队列的大小

priority_queue

优先队列类似队列， 但是在这个数据结构中的元素按照一定的规则排列有序。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高优先级先出 （first in, largest out）的行为特征。

首先要包含头文件#include, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

优先队列具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。

构造函数： priority_queue<Type, Container, Functional>

• Type 就是数据类型，

• Container 就是容器类型（Container必须是具备随机存取能力的容器，支持如下方法：empty(), size(), front(), push_back(),pop_back()。比如vector,deque等等，但不能用list。STL里面默认用的是vector）。可选

• Functional 就是比较的方式。可选

当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆(Functional是less)。

// constructing priority queues
#include <iostream>       // std::cout
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

class mycomparison
{
  bool reverse;
public:
  mycomparison(const bool& revparam=false)
    {reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
    if (reverse) return (lhs>rhs);
    else return (lhs<rhs);
  }
};

int main ()
{
  int myints[]= {10,60,50,20};

  std::priority_queue<int> first;
  std::priority_queue<int> second (myints,myints+4);
  std::priority_queue<int, std::vector<int>, std::greater<int> >
                            third (myints,myints+4);
  // using mycomparison:
  typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type;

  mypq_type fourth;                       // less-than comparison
  mypq_type fifth (mycomparison(true));   // greater-than comparison

  return 0;
}

The example does not produce any output, but it constructs different priority_queue objects: - First is empty. - Second contains the four ints defined for myints, with 60 (the highest) at its top. - Third has the same four ints, but because it uses greater instead of the default (which is less), it has 10 as its top element. - Fourth and fifth are very similar to first: they are both empty, except that these use mycomparison for comparisons, which is a special stateful comparison function that behaves differently depending on a flag set on construction.

api和队列基本操作相同:

• top 访问队头元素

• empty 队列是否为空

• size 返回队列内元素个数

• push 插入元素到队尾 (并排序)

• emplace 原地构造一个元素并插入队列

• pop 弹出队头元素

• swap 交换内容

时间复杂度对比

容器	访问	push_back()	push_front()	insert()	pop_back()	pop_front()	erase()	find()
list	O(n)	O(1)	O(1)	O(1)	O(1)	O(1)	O(1)	O(n)
vector	O(1)	O(1)	\	O(n)	O(1)	\	O(n)	O(n)
deque	O(1)	O(1)	O(1)	O(n)	O(1)	O(1)	O(n)	O(n)
map	O(log n)	\	\	O(log n)	\	\	O(log n)	O(log n)
multimap	O(log n)	\	\	O(log n)	\	\	O(log n)	O(log n)
set	O(log n)	\	\	O(log n)	\	\	O(log n)	O(log n)
multiset	O(log n)	\	\	O(log n)	\	\	O(log n)	O(log n)

容器底层实现和特点

1. vector（向量）

   

   • 底层实现：动态数组，元素连续存储。

   • 扩容方式：通常以倍数增加容量，旧数据复制到新内存块，释放旧内存。

   • 特点：

     • 随机访问时间复杂度为 O(1)。
     • 在末尾添加或删除元素较快，但在中间或头部插入/删除操作时间复杂度为 O(n)。
     • 对于频繁进行随机访问和末尾操作的场景非常高效。

2. list（双向链表）

   

   • 底层实现：双向链表，每个节点包含指向前后节点的指针。

   • 特点：

     • 插入和删除操作时间复杂度为 O(1)，不需要移动其他元素。
     • 随机访问时间复杂度为 O(n)。
     • 适用于需要频繁插入和删除元素而不要求高效随机访问的场景。

3. deque（双端队列）

   

   • 底层实现：多个连续内存块（缓冲区）及其索引。

   • 特点：

     • 支持双端快速插入和删除操作。
     • 随机访问时间复杂度为 O(1)。
     • 适用于需要在两端频繁操作，同时希望进行随机访问的场景。

4. map（映射）

   • 底层实现：红黑树（平衡二叉搜索树）。
   • 特点：
     • 元素以键值对形式存储，键唯一且自动排序。
     • 查找、插入、删除操作时间复杂度为 O(log n)。
     • 适用于需要根据键值对进行查找和存储的场景。

5. set（集合）

   • 底层实现：红黑树（平衡二叉搜索树）。
   • 特点：
     • 元素唯一且自动排序。
     • 查找、插入、删除操作时间复杂度为 O(log n)。
     • 适用于需要存储唯一元素并进行排序的场景。

6. multimap（多重映射）

   • 底层实现：红黑树（平衡二叉搜索树），与 map 相似，但允许键重复。
   • 特点：
     • 允许多个键值对具有相同的键。
     • 查找、插入、删除操作时间复杂度为 O(log n)。
     • 适用于需要存储多个键相同的值的场景。

7. multiset（多重集合）

   • 底层实现：红黑树（平衡二叉搜索树），与 set 相似，但允许元素重复。
   • 特点：
     • 允许存储多个相同的元素。
     • 查找、插入、删除操作时间复杂度为 O(log n)。
     • 适用于需要存储重复元素并进行排序的场景。

其他容器

• stack（栈）、queue（队列） 和 priority_queue（优先队列） 是容器适配器，基于底层容器（如 deque、vector）实现，提供特定的操作和访问模式。它们不直接支持复杂的操作（如插入中间元素）：

  • stack：后进先出（LIFO），底层通常使用 deque。
  • queue：先进先出（FIFO），底层通常使用 deque。
  • priority_queue：优先队列，通常使用堆（如二叉堆）实现，提供高效的优先级访问。

总结

1. 高效随机访问：使用 vector

2. 高效插入和删除操作：使用 list

3. 双端高效操作和随机访问：使用 deque

4. 键值对映射和查找：使用 map 或 multimap

5. 唯一元素存储和排序：使用 set 或 multiset

Reference

[1] C++ STL常用容器API总结:https://vernlium.github.io/2019/12/29/C-STL%E5%B8%B8%E7%94%A8%E5%AE%B9%E5%99%A8API%E6%80%BB%E7%BB%93/

[2] C++ STL中各种数据结构操作的时间复杂度比较:https://blog.csdn.net/dieju8330/article/details/108551007