vector

常用构造函数

  1. // 构造容量为 100 的 vector，每个值都赋值为 256
  2. // 如果不提供初始值，会填充对应元素类型的 默认值
  3. std::vector<int> vec(100, 256);
  5. // 范围构造：以 vec 容器中的前 50 个元素来构造一个 vector
  6. // 任何 STL 容器都可以，数组也可以，如下面的例子
  7. std::vector<int> vec2(vec.begin(), vec.begin() + 50);
  9. // 以数组的值来构造 vec
  10. int arr[] = {128, 123, 21, 12, 23, 321};
  11. std::vector<int> vec2(arr, arr +  sizeof(arr) / sizeof(int));
  13. // 赋值构造函数
  14. std::vector<int> vec2(vec);

添加元素

  1. // 在 vector 的末尾添加元素 value
  2. // 当添加的元素个数超过 vector 的容量时，会自动扩容，这可能会导致指向之前内容的指针无效
  3. void push_back(const value_type& value)
  5. // 和 push_back 功能一样，都是在 vector 的末尾位置添加元素
  6. // 但是 emplace_back 没有复制开销
  7. // 它会以 args 为参数原地调用 value_type 的构造函数来构造要添加的值
  8. void emplace_back(Args&& ... args);
  11. // 指定的位置 pos 处插入元素 val
  12. // 返回新插入的元素的位置
  13. iterator insert(const_iterator pos, const value_type& val);
  15. // 指定的位置 pos 处插入范围 [first, last) 中的所有元素
  16. // 返回新插入的第一个元素的位置
  17. iterator insert(const_iterator pos, iterator first, iterator last);
  19. // 在指定的位置 pos 处，以 args 为参数原理构造的方式添加一个元素
  20. // 并返回新添加元素的位置
  21. iterator emplace(const_iterator pos, Args&& ... args);
  25. // assign 系列函数的作用是，使用新的元素替换容器中原有的元素，并相应的修改容器的大小。
  27. // 用区间 [first, last) 中的元素替换容器中的元素
  28. void assign(iterator first, iterator last);
  30. // 用 n 个值为 val 的元素替换容器中原有的元素
  31. void assign(size_t n, const value_type& val);
  33. // 用初始化列表中的元素替换容器中的元素
  34. void assign(intialiazer_list<value_type> li);
  37. //-------------------------- 以下函数不常用 ------------------------------//
  39. // 指定的位置 pos 处插入初始化元素列表中的所有元素
  40. // 返回新插入的第一个元素的位置
  41. iterator insert(const_iterator pos, intialiazer_list<value_type> li);
  43. // 指定的位置 pos 处插入 n 个元素 val
  44. // 返回新插入的第一个元素的位置
  45. iterator insert(const_iterator pos, size_t n, const value_type& val);

需要注意的是，上面所有的添加元素的函数，都有可能发生自动扩容的情况，这可能导致你之前的指向 vector 某个元素的指针无效，从而应发程序崩溃等。
另外，因为 vector 底层的存储使用的是数组，所以最好是在 vector 的末尾添加元素，在中间位置或开头位置添加元素都会引发元素发生挪动，这是比较耗时的操作。

删除元素

  1. // 移除容器中最后位置的元素 (被移除的元素会被析构)
  2. void pop_back();
  4. // 删除指定位置 pos 处的元素
  5. // 返回被删除元素的下一个元素的位置
  6. iterator erase(const_iterator pos);
  8. // 删除指定区间: [first, last) 中的所有元素
  9. // 返回被删除区间的下一个元素的位置
  10. iterator erase(const_iterator first, const_iterator last);
  12. // 移除容器中的所有元素 (调用每个元素的析构函数)，调用该方法后，容器大小为 0.
  13. // clear 不保证原 vector 的内存被重新分配，也不保证该表 vector 的容量大小。
  14. void clear();
  16. // 如果想要保证原 vector 的内存重新分配，可以调用 vector 的 swap 方法
  17. vector<int>().clear(vec);

访问元素

  1. // 返回 vector 容器开头位置的元素的引用
  2. // 注意，若是 vector 为空，调用该函数是 UB 行为
  3. reference front();
  5. // 返回 vector 容器末尾位置的元素的引用
  6. // 注意，若是 vector 为空，调用该函数是 UB 行为
  7. reference back();
  9. // 和 operator[] 功能类似，返回指定位置处的元素，
  10. // 不同的是，at 函数会检查位置参数 n 是否合法，不合法的情况下会抛出 out_of_range 异常
  11. reference at(size_t n);
  13. // 返回内部用于存储 vector 的数组指针
  14. value_type* data();
  16. // 随机访问第 n 个元素的值
  17. reference operator[](size_t n);

其他函数

  1. // vector 的容量至少要为 n
  2. // 如果当前容量小于 n，则重新分配至少可以容纳 n 个元素的空间；否则，函数无影响。
  3. void reserve(size_t n);
  5. // 重新调整 vector 容器的大小（注意不是容量）
  6. // 如果 n 小于当前容器大小，则只保留前 n 个元素，其余被析构清除
  7. // 如果 n 大于当前容器大小，则扩展容器元素大小到 n 个元素，默认值为元素的默认值
  8. void resize(size_t n);
  10. // 和上面的功能一致，只是扩展的情况下会填充指定的值 val
  11. void resize(sizet_n, const value_type& val);
  13. // 调整容器容量大小到容器 size 的大小，一般不用，除非特别在意空间
  14. void shrink_to_fit();
  17. // 下面是对 vector 迭代访问的一些函数
  18. iterator begin();
  19. iterator end();
  21. const_iterator cbegin();
  22. const_iterator cend();
  24. iterator rbgin();
  25. iterator rend();
  27. const_iterator crbegin();
  28. const_iterator crend();

queue

常用构造函数

  1. // 构造一个空队列
  2. std::queue<int> que;
  4. // 以 cnt 的内容来构造队列 queue
  5. // 底层默认是使用 std::deque 来保存队列元素，可以指定其他容器
  6. explicit queue<T, container_type=deque<T>>(const container_type& ctn);
  8. // 赋值构造函数
  9. explicit queue(const queue& x);
  12. std::deque<int> deq(3, 12);
  13. // 构造一个队列，队列中的值是 deq 中的值
  14. std::queue<int> que(deq);
  16. std::vector<int> vec(5,256);
  17. // 构造一个队列，队列中的值是 vec 中的值
  18. std::queue<int,std::vecteor<int>> que(vec);

队列的增删查改

  1. // 往队列尾部添加一个元素 val
  2. void push(const value_type& val);
  4. // 和push功能一样，都是往队列尾部添加一个元素 val
  5. // 不同的是，emplace 会以原地构造的方式添加
  6. void emplace(Args&& ... args);
  8. // 删除队列的队头元素
  9. void pop();
  11. // 访问队列的队头元素
  12. // 注意，这里返回的是引用，方便你直接修改队头元素
  13. value_type& front();
  15. // 队头元素乘 2
  16. que.front() *= 2;
  18. // 队列为空，返回true，否则返回false
  19. bool empty() const;
  21. // 返回队列的大小
  22. size_t size() const;
  24. // 交换两个队列
  25. // 注意：交换的两个队列的底层容器必须一致，否则它们是两个不同的类型，无法调用该函数
  26. void swap(queue& x) noexcept;

可以看到，队列的操作比较简单，没有其他的复杂操作，因为队列本身可以理解成是增删查改都受到一定限制的数组，所以，它的 push，pop ，emplace 等也都不需要带上 _back 等表示插入或删除位置的后缀。

stack

常用构造函数

  2. // 以容器 cntr 的元素构造一个 stack 容器
  3. // 默认的容器适配器类型时 std::deque
  4. explicit stack(const container_type& ctnr=empty_container);
  7. std::deque<int> mydeque(3,100);
  8. // 以deque元素构造一个 stack
  9. std::stack<int> first(mydeque);
  11. // 以vector作为容器适配器构造一个 stack
  12. std::stack<int,std::vector<int>> second(std::vector<int>{1,2,3});
  14. std::stack<int> third; // 构造一个空的 stack

栈的增删查改

  2. // 在栈顶位置添加一个元素
  3. void push(const value_type& val);
  5. // 以原地构造的方式在栈顶位置添加一个元素
  6. void emplace(Args&&...args);
  8. // 访问栈顶位置的元素，可以方便快速修改栈顶元素
  9. reference top();
  11. // 删除栈顶位置的元素
  12. void pop();
  14. // 返回栈的大小
  15. size_t size();
  17. // 交换两个栈的元素内容
  18. void swap(stack& x);

可以看到，栈的操作比队列还要简单，那是因为栈的限制比队列还要打，因为栈的添加删除修改都只能在一端进行。

priority_queue

常用构造函数

  2. // 构造一个优先级队列，内部比较算法是 comp，内容保存元素的容器是 cntr
  3. // comp 默认是 std::less
  4. // cntr 默认是 std::vector
  5. priority_queue(const Compare& comp, const Container& cntr);
  7. // 区间构造，和上一个一样，但是会插入 [first, last) 区间内的元素到优先级队列中
  8. priority_queue(Iterator first, Iterator last, const Compare& comp, const Container& cntr);
  11. // 构造一个空的优先级队列
  12. // 默认比较函数是 less, 也就是大顶堆
  13. // 默认使用的容器是 vector
  14. std::priority_queue<int> que;

优先级队列的增删查改

  1. // 往优先级队列中添加一个元素 val
  2. void push(const value_type& val);
  4. // 和push功能一样，都是往优先级队列中添加一个元素 val
  5. // 不同的是，emplace 会以原地构造的方式添加
  6. void emplace(Args&& ... args);
  8. // 删除优先级队列的顶部元素，
  9. void pop();
  11. // 访问优先级队列的顶部元素
  12. // 注意，这里返回的是常引用，不可修改
  13. const value_type& top();
  15. // 队列为空，返回true，否则返回false
  16. bool empty() const;
  18. // 返回队列的大小
  19. size_t size() const;
  21. // 交换两个队列
  22. // 注意：交换的两个队列的底层容器必须一致，否则它们是两个不同的类型，无法调用该函数
  23. void swap(queue& x) noexcept;

可以看到，priority_queue 的函数和 queue 几乎一样，只是队列的 front() 函数换成了 top() 函数，之所以会有这个差别，是因为所谓优先级队列其实和队列没有什么关系，它本质上是一个大/小顶堆。而叫它优先级队列也是因为它的性质和队列是一样的，不同的是，队列是以入队的顺序来出队的，而它是以元素的大小来出队的。

priority_queue 的内部实现其实就是调用的 std::make_heap, std::push_heap, std::pop_heap 这几个函数来实现的。

deque

deque 表示 double-ended-queue 的意思，也就是双端队列。它提供的功能其实和 vector 基本一致，但 vector 只支持在末尾进行高效的插入和删除操作；而 deque 同时支持在开头和末尾的位置进行高效的插入和删除操作。
deque 也支持对单个元素进行快速的随机访问，但是它不保证内部所有元素在内存中是连续存储的，所以通过偏移 deque 中某个元素的指针来访问另一个指针是属于 UB 行为。

常用构造函数

  1. std::deque<int> deq;
  3. // 构造一个有 n 个元素的 deque。
  4. explicit deque(size_t n);
  6. // 构造一个有 n 个元素，每个元素的值为 val 的 deque。
  7. deque(size_t n, const value_type& val);
  9. // 以区间 [first, last) 中的元素构造一个 deque。
  10. deque(iteartor first, iterator last);
  12. // 赋值构造
  13. deque(const deque& x);
  15. // 以初始化序列中的值构造 deque
  16. deque(intializer_list<valye_type> li);

添加元素

  1. // 在 deque 的末尾添加元素 value
  2. void push_back(const value_type& value)
  4. // 在 deque 的开头添加元素 value
  5. void push_front (const value_type& value);
  7. // 和 push_back 功能一样，都是在 deque 的末尾位置添加元素
  8. // 但是 emplace_back 没有复制开销
  9. // 它会以 args 为参数原地调用 value_type 的构造函数来构造要添加的值
  10. void emplace_back(Args&& ... args);
  12. // 和 push_front 功能一样，都是在 deque 的开头位置添加元素
  13. // 但是 emplace_front 没有复制开销
  14. // 它会以 args 为参数原地调用 value_type 的构造函数来构造要添加的值
  15. void emplace_front (Args&&... args);
  18. // 指定的位置 pos 处插入元素 val
  19. // 返回新插入的元素的位置
  20. iterator insert(const_iterator pos, const value_type& val);
  22. // 指定的位置 pos 处插入范围 [first, last) 中的所有元素
  23. // 返回新插入的第一个元素的位置
  24. iterator insert(const_iterator pos, iterator first, iterator last);
  26. // 在指定的位置 pos 处，以 args 为参数原理构造的方式添加一个元素
  27. // 并返回新添加元素的位置
  28. iterator emplace(const_iterator pos, Args&& ... args);
  31. // assign 系列函数的作用是，使用新的元素替换容器中原有的元素，并相应的修改容器的大小。
  33. // 用区间 [first, last) 中的元素替换容器中的元素
  34. void assign(iterator first, iterator last);
  36. // 用 n 个值为 val 的元素替换容器中原有的元素
  37. void assign(size_t n, const value_type& val);
  39. // 用初始化列表中的元素替换容器中的元素
  40. void assign(intialiazer_list<value_type> li);
  42. //-------------------------- 以下函数不常用 ------------------------------//
  44. // 指定的位置 pos 处插入初始化元素列表中的所有元素
  45. // 返回新插入的第一个元素的位置
  46. iterator insert(const_iterator pos, 
  48. // 指定的位置 pos 处插入 n 个元素 val
  49. // 返回新插入的第一个元素的位置
  50. iterator insert(const_iterator pos, size_t n, const value_type& val);

删除元素

  1. // 移除容器中最后一个位置的元素 (被移除的元素会被析构)
  2. void pop_back();
  4. // 移除容器中第一个位置的元素 (被移除的元素会被析构)
  5. void pop_front();
  7. // 删除指定位置 pos 处的元素
  8. // 返回被删除元素的下一个元素的位置
  9. iterator erase(const_iterator pos);
  11. // 删除指定区间: [first, last) 中的所有元素
  12. // 返回被删除区间的下一个元素的位置
  13. iterator erase(const_iterator first, const_iterator last);
  15. // 移除容器中的所有元素 (调用每个元素的析构函数)，调用该方法后，容器大小为 0.
  16. // clear 不保证原 vector 的内存被重新分配，也不保证该表 vector 的容量大小。
  17. void clear();
  19. // 如果想要保证原 vector 的内存重新分配，可以调用 vector 的 swap 方法
  20. vector<int>().clear(vec);

访问元素

  1. // 返回 vector 容器开头位置的元素的引用
  2. // 注意，若是 vector 为空，调用该函数是 UB 行为
  3. reference front();
  5. // 返回 vector 容器末尾位置的元素的引用
  6. // 注意，若是 vector 为空，调用该函数是 UB 行为
  7. reference back();
  9. // 和 operator[] 功能类似，返回指定位置处的元素，
  10. // 不同的是，at 函数会检查位置参数 n 是否合法，不合法的情况下会抛出 out_of_range 异常
  11. reference at(size_t n);
  13. // 返回内部用于存储 vector 的数组指针
  14. value_type* data();
  16. // 随机访问第 n 个元素的值
  17. reference operator[](size_t n);

其他函数

  2. // 重新调整 vector 容器的大小（注意不是容量）
  3. // 如果 n 小于当前容器大小，则只保留前 n 个元素，其余被析构清除
  4. // 如果 n 大于当前容器大小，则扩展容器元素大小到 n 个元素，默认值为元素的默认值
  5. void resize(size_t n);
  7. // 和上面的功能一致，只是扩展的情况下会填充指定的值 val
  8. void resize(sizet_n, const value_type& val);
  10. // 调整容器容量大小到容器 size 的大小，一般不用，除非特别在意空间
  11. void shrink_to_fit();
  14. // 下面是对 vector 迭代访问的一些函数
  15. iterator begin();
  16. iterator end();
  18. const_iterator cbegin();
  19. const_iterator cend();
  21. iterator rbgin();
  22. iterator rend();
  24. const_iterator crbegin();
  25. const_iterator crend();

map、unordered_map

常用构造函数

  2. // 默认构造函数，构造一个空的 map 容器
  3. explicit map(const key_compare& comp=key_compare(), const alloc=aolloc);
  5. // 区间构造函数，以区间 [first, last) 中的元素构造一个 map 容器
  6. map(interator first, iterator last, const key_compare& comp=key_compare, alloc);
  8. // 初始化列表的方式构造
  9. map(initialize_list<valye_type> li, const key_compare& comp=key_compare, alloc);
  11. // 赋值构造
  12. map(const map& x);

可以看到 map 的每个构造函数基本都有一个对 key 进行比较的函数，你可以自定义 key 的比较规则，之所以需要这个比较函数是因为 map 中的元素是有序存储的。

  2. // 默认构造函数，默认一个 0 大小的 unordered_map 容器
  3. explicit unordered_map(size_t n=0, const hasher&=, const key_equal&=...);
  5. // 区间构造，以区间 [first, last) 中的元素构造 unordered_map 容器
  6. unordered_map(iterator first, iterator last, size_t n=0, const hasher...);
  8. // 赋值构造
  9. unordered_map(const unordered_map& x);
  11. // 列表初始化构造
  12. unordered_map(initializer_list<value_type> li, size_t n=0, const hasher...);

unordered_map 和 map 的功能一样，但是 map 是有序的， unordered_map 是无序的，所以，在访问单个元素的时候，unordered_map 的速度要比 map 更快。

添加元素

  2. // 使用 args 参数原地构造一组 <key,value> 对元素并添加到 map 容器中。
  3. // 如果插入成功，则返回新插入元素的迭代器和 true
  4. // 否则，插入失败，表示对应的 key 已存在，返回对应等效元素的迭代器和 false
  5. pair<iteraotr, bool> emplace(Args&& ... args);
  7. // 插入值 val 到 map 容器中
  8. pair<iterator, bool> insert(const value_type& val);
  10. // 插入区间 [first, last) 中的元素到 map 容器中
  11. void insert(iterator first, iterator last);
  13. // 插入序列化中的元素到 map 容器中
  14. void insert(initialize_list<value_type> li);

注意，map 中的 key 值是唯一的，上面所有的插入函数，当插入的 key 值已存在，是不会进行插入操作的。

删除元素

  2. // 删除指定迭代器位置所在的元素，
  3. // 返回被删除元素的下一个元素的迭代器
  4. iterator erase(iterator pos);
  6. // 删除指定的 key 的元素
  7. // 返回被删除元素的个数
  8. size_type erase(const key_type& k);
  10. // 删除指定区间 [first, last) 中的元素
  11. iterator erase(iterator first, iterator last);

访问元素

  2. // 访问指定 key 值的元素值 value，注意是一个引用，可直接修改
  3. // 当对应的 key 值不存在的时候，会抛异常
  4. mapped_type& at(const key_type& k);
  6. // 功能和 at 函数一样，但是
  7. // 当对应的 key 值不存在的时候，会默认添加对应 key 的元素
  8. mapped_type& operator[](const key_type& k);
  10. // 返回容器中所有 key 值等于 k 的元素的一个范围的边界区间
  11. // 但是因为 map 所有 key 都是唯一，所以这个区间中最大元素不会超过 1 个
  12. pair<iterator,iterator> equal_range(const key_type& k);

其他函数

  2. // 返回 key 值为 k 所对应 value 的个数
  3. // 因为 key 值唯一，所以，该函数改么返回 1，要么返回 0；
  4. // 作用就是用来判断容器中是否包含某个key值
  5. size_t count(const key_type& k);
  7. // 返回指定 key 值得元素所在的迭代器位置
  8. // 如果对应的 key 值不存在，则返回 map::end 位置
  9. iterator find(const key_type& k);
  12. // 交换两个 map 容器的内容
  13. void swap(map& x);
  16. // 下面是对 vector 迭代访问的一些函数
  17. iterator begin();
  18. iterator end();
  20. const_iterator cbegin();
  21. const_iterator cend();
  23. iterator rbgin();
  24. iterator rend();
  26. const_iterator crbegin();
  27. const_iterator crend();
  2. // 返回容器中 key 值第一个大于等于 k （对于 operator < 来说；反之则小于等于）的元素的迭代器
  3. // 其实就是 k 为键值得元素的 下边界；是大于还是小于，得根据是从小到大排还是从大到小排。
  4. iterator lower_bound(const key_type& k);
  6. // 返回容器中 key 值第一个大 k（对于 operator < 来说；反之则小于） 的元素的迭代器
  7. // 其实就是 k 为键值得元素的 上边界；
  8. // 注意，和 lower_bound 相比，它没有等于
  9. iterator upper_bound(const key_type& k);

从上面的描述可以看到，其实 lower_bound, upper_bound, 分别就是返回某个元素的左闭右开的一个区间。

set / unordered_set 其实就是没有 value 这个类型，或者说 value 就是它本身的 key 的一个容器。除此之外，它的内部原理以及提供的 API 函数和对应的 map / unordered_map 没有任何差别，这里不再赘述。