STL (Standard Template Library)组件

  1. 容器 Containers
    1. Vector
    2. List
    3. Queue
    4. Dequeue
    5. Priority Queue
    6. Stack
    7. Set
    8. Multiset
    9. Map & unordered map
    10. Multimap
  2. 算法 Algorithms
  3. 迭代器 Iterators
  4. 函数对象 Function Objects
  5. 适配器 Adapters

算法

  1. 排序
  2. 搜索
  3. 常用数组算法

Vector

原文 https://www.geeksforgeeks.org/vector-in-cpp-stl/

迭代器Iterators

  1. begin() – 返回迭代器指向的第一个元素
  2. end() – 返回迭代器指向的最后一个元素
  3. rbegin() – 返回迭代器倒序指向的元素，指针从最后一个向第一个移动
  4. rend() – 返回指向vector中第一个元素之前的理论元素的反向迭代器（被视为反向结束）
  5. cbegin() – 返回指向vector中第一个元素的常量迭代器
  6. cend() – 返回指向vector中最后一个元素之后的理论元素的常量迭代器。
  7. crbegin() – 返回指向vector中最后一个元素（反向开始）的常量反向迭代器。从最后一个元素移动到第一个元素
  8. crend() – 返回一个常量反向迭代器，指向vector中第一个元素之前的理论元素（被视为反向结束）

记住是begin和end，其他的看前缀，r: reverse反向，c: constant常量，cr: constant+reverse

容器Capacity

  1. size() – 返回元素数量
  2. max_size() – 返回vector可以存放的最大元素数
  3. capacity() – 返回当前分配给vector的存储空间的大小，以元素数表示。
  4. resize(n) – 调整容器的大小，使其装下n个元素。
  5. empty() – 返回容器是否为空
  6. shrink_to_fit() – 减少vector的容量以适应其大小并销毁超出容量的所有元素。理解为减去没有存储的空容量
  7. reserve()– 要求vector容量至少足以包含 n 个元素。

元素访问 Element access

  1. reference operator [g] – 返回g索引位置的元素
  2. at(g) – 返回g索引位置的元素
  3. front() – 返回vector的第一个元素
  4. back() – 返回vector的最后一个元素
  5. data() – 返回指向vector内部使用的内存数组的直接指针，用于存储其拥有的元素。

Modifiers

  1. assign()–通过替换旧元素来为vector元素分配新值
  2. push_back() – 从vector的末尾将元素推入vector中
  3. pop_back() – 从vector的末尾弹出或删除元素。
  4. insert() – 在指定位置的元素之前插入新元素
  5. erase() –从vector的指定位置或范围删除元素。
  6. swap() – 将一个向量的内容与另一个相同类型的向量交换。大小可以不同。
  7. clear() – 删除vector的所有元素
  8. emplace() – 通过在指定位置插入新元素来扩展容器。
  9. emplace_back() – 将新元素插入到向量容器中，新元素添加到向量的末尾

Map

返回指向末尾的迭代器：end(); 用迭代器访问元素的键值 it->first 用迭代器访问元素的键值对应的元素值 it->second

C++中的std::map是一个关联容器，它将键和值以键-值对的形式存储在容器中，并按键的顺序进行排序。以下是std::map提供的一些主要函数及其简介：

  1. begin():
    • 返回指向容器中第一个键-值对的迭代器。
  2. end():
    • 返回指向容器中最后一个键-值对之后位置的迭代器。
  3. rbegin():
    • 返回指向容器中最后一个键-值对的逆序迭代器。
  4. rend():
    • 返回指向容器中第一个键-值对之前位置的逆序迭代器。
  5. clear():
    • 清空容器，移除所有键-值对。
  6. count(const KeyType& key):
    • 返回具有给定键的键-值对的数量（通常为0或1，因为map不允许重复键）。
  7. empty():
    • 如果容器为空，则返回true；否则返回false。
  8. erase(iterator position):
    • 移除指定迭代器位置的键-值对。
  9. erase(const KeyType& key):
    • 移除具有给定键的键-值对。
  10. find(const KeyType& key):
    • 返回一个指向具有给定键的键-值对的迭代器，如果键不存在，则返回end()。
  11. insert(const std::pair<KeyType, ValueType>& kv):
    • 在容器中插入一个键-值对。如果该键已存在，则更新对应的值。
  12. size():
    • 返回容器中键-值对的数量。
  13. lower_bound(const KeyType& key):
    • 返回指向第一个不小于给定键的键-值对的迭代器。
  14. upper_bound(const KeyType& key):
    • 返回指向第一个大于给定键的键-值对的迭代器。
  15. equal_range(const KeyType& key):
    • 返回一对迭代器，分别指向容器中所有具有给定键的键-值对的范围。
  16. swap(std::map& other):
    • 交换两个map容器的内容。

这些是std::map提供的一些常用函数。map是一个有序容器，用于存储键值对，它会根据键的值来排序，并且不允许重复的键。这使得它非常适用于需要将数据按键进行有序存储和检索的情况。

Map遍历的几种方法

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

int main() {
    unordered_map<string, int> mp;
    mp["张三"] = 20;
    mp["李四"] = 18;
    mp["王五"] = 30;

    // 方式一、迭代器
    cout << "方式一、迭代器" << endl;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        cout << it -> first << " " << it -> second << endl;
    }

    // 方式二、range for C++ 11版本及以上
    cout << "\n方法二、 range for" << endl;
    for (auto it : mp) {
        cout << it.first << " " << it.second << endl;
    }

    // 方法三、 C++ 17版本及以上
    cout << "\n方法三" << endl;
    for (auto [key, val] : mp) {
        cout << key  << " " << val << endl;
    }
    
    return 0;
}

Stack

在默认情况下，std::stack使用std::deque作为其底层数据结构，因为std::deque允许在两端进行高效的插入和删除操作，这对于栈这种数据结构来说非常合适。而deque（双端队列，即"double-ended queue"的缩写）的底层数据结构通常是由一个动态数组（或一系列固定大小的数组块）组成的，而不是像vector一样使用单个连续的内存块。这使得deque在两端（前端和后端）进行高效的插入和删除操作成为可能。

empty() – 返回栈是否为空 size() – 返回栈的大小 top() – 返回对堆栈最顶部元素的引用 push(g) – 将元素“g”添加到堆栈顶部 pop() – 删除堆栈中最近输入的元素

Set

集合是一种关联容器，其中每个元素都必须是唯一的。其底层实现是红黑树，默认是升序（从小到大）

当在C++代码中使用std::set时，通常会使用命名空间std，所以你可以不必每次都使用完整的std::set::前缀。以下是相同的函数列表，简化为使用命名空间的写法：

  1. begin():
    • 返回指向容器中第一个元素的迭代器。
  2. end():
    • 返回指向容器中最后一个元素之后位置的迭代器。
  3. rbegin():
    • 返回指向容器中最后一个元素的逆序迭代器。
  4. rend():
    • 返回指向容器中第一个元素之前位置的逆序迭代器。
  5. clear():
    • 清空容器，移除所有元素。
  6. count(const KeyType& key):
    • 返回具有给定键值的元素的数量（通常为0或1，因为set不允许重复键）。
  7. empty():
    • 如果容器为空，则返回true；否则返回false。
  8. erase(iterator position):
    • 移除指定迭代器位置的元素。
  9. erase(const KeyType& key):
    • 移除具有给定键值的元素。
  10. find(const KeyType& key):
    • 返回一个指向具有给定键值的元素的迭代器，如果元素不存在，则返回end()。
  11. insert(const ValueType& value):
    • 在容器中插入一个值。如果该值已存在，则不会插入。
  12. size():
    • 返回容器中元素的数量。
  13. lower_bound(const KeyType& key):
    • 返回指向第一个不小于给定键值的元素的迭代器。
  14. upper_bound(const KeyType& key):
    • 返回指向第一个大于给定键值的元素的迭代器.
  15. equal_range(const KeyType& key):
    • 返回一对迭代器，分别指向容器中所有具有给定键值的元素的范围。
  16. swap(std::set& other):
    • 交换两个set容器的内容。