C++ STL容器

vector（向量）

连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。
vector首先分配一个非常大的内存空间预备进行存储，即capacity()函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储（视编译器决定还是2倍还是1.5倍），所以这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。
扩充空间的过程为：

1. 配置一块新的空间
2. 将旧元素一一搬入新地址
3. 把原来的空间释放还给系统

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

int main() {
    std::vector<int> vector_test;
    vector_test.push_back(1);
    std::cout << "size: " << vector_test.size() << ", cap: " << vector_test.capacity() << std::endl;
    // size: 1, cap: 1
    vector_test.reserve(10);
    std::cout << "size: " << vector_test.size() << ", cap: " << vector_test.capacity() << std::endl;
    // size: 1, cap: 10
    vector_test.push_back(2);
    std::cout << "size: " << vector_test.size() << ", cap: " << vector_test.capacity() << std::endl;
    // size: 2, cap: 10

    // sort头文件<algorithm>
    // functional头文件<functional>, less升序，greater降序，默认为非降序排序
    std::sort(vector_test.begin(), vector_test.end(), std::greater<int>());
    std::sort(vector_test.begin(), vector_test.end(), std::less<int>());

    // cbegin(),cend(),crbegin(),crend()分别是的begin(),end(),rbegin(),rend()的const版本
    // r:reverse,反向
    for (auto iter = vector_test.cbegin(); iter != vector_test.cend(); ++iter) { 
        std::cout << "key: " << *iter << std::endl;
    }
    for (auto iter = vector_test.crbegin(); iter != vector_test.crend(); ++iter) {
        std::cout << "key: " << *iter << std::endl;
    }
    for (auto iter : vector_test) {
        std::cout << "key: " << iter <<  std::endl;
    }
    for (int index = 0; index < vector_test.size(); ++index) {
        std::cout << "key: " << vector_test.at(index) << std::endl;
        // std::cout << "key: " << vector_test[index] << std::endl;
        // 直接用[]访问，vector退化为数组，不会进行越界的判断。此时推荐使用at()，会先进行越界检查。
    }
    return 0;
}

list（列表）

非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。

#include <iostream>
#include <list>

int main() {
    std::list<int> list_test;
    list_test.push_back(1);
    list_test.push_front(2);
    list_test.push_front(2);

    list_test.unique(); // 去重

    for (auto iter : list_test) {
        std::cout << "key: " << iter << std::endl;
    }

    return 0;
}

deque（双端队列 double-end queue）

连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构，采用一块所谓的 map 作为主控。这里的 map 是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是 deque 的存储空间主体。（ 底层数据结构为一个中央控制器和多个缓冲区）SGI STL 允许我们指定缓冲区大小，默认值 0 表示将使用 512 bytes 缓冲区。这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。
参考：https://blog.csdn.net/u010710458/article/details/79540505

#include <iostream>
#include <deque>

int main() {
    std::deque<int> deque_test;
    deque_test.push_back(1);
    deque_test.push_front(2);

    for (int index = 0; index < deque_test.size(); ++index) {
        std::cout << "key: " << deque_test.at(index) << std::endl;
        // std::cout << "key: " << deque_test[index] << std::endl;
    }
}

vector、list、deque的选择

1. 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2. 如果你需要大量的插入和删除，而不关心随机存取，则应使用list
3. 如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

map（映射）

非连续存储结构，底层数据结构是红黑树。key不可以重复，自动按照key从小到大排序

#include <iostream>
#include <map>

int main() {
    std::map<int, int> map_test;
    map_test.insert( std::make_pair(1, 1) );
    map_test.insert( std::make_pair(2, 2) );
    // map的key不能重复，所以这里的insert实则没有生效
    if (false == map_test.insert(std::make_pair(2, 3)).second) {
        std::cout << "insert faild!" << std::endl;
    }
    // insert_or_assign 若key已存在，替换value；如果key不存在，插入
    map_test.insert_or_assign(2, 4);
    map_test.insert_or_assign(3, 5);

    auto iter = map_test.find(2);
    if (iter != map_test.end()) {
        std::cout << "key[2]: " << iter->second << std::endl;
    }
    auto count = map_test.count(6);
    if (count == 0) {
        std::cout << "key[6] is not exist" << std::endl;
    }

    for (auto iter : map_test) {
        std::cout << "key: " << iter.first << ", value: " << iter.second << std::endl;
    }

    return 0;
}

multimap（多重映射）

非连续存储结构，底层数据结构是红黑树。key可以重复，自动按照key从小到大排序

#include <iostream>
#include <map>

int main() {
    std::multimap<int, int> multimap_test;
    multimap_test.insert(std::make_pair(1, 1));
    multimap_test.insert(std::make_pair(1, 2));

    // 如果find的key对应多个value，返回第一个
    auto iter = multimap_test.find(1);
    if (iter != multimap_test.end()) {
        std::cout << "key[1]: " << iter->second << std::endl;
    }

    for (auto iter : multimap_test) {
        std::cout << "key: " << iter.first << ", value: " << iter.second << std::endl;
    }

    return 0;
}

unordermap（不排序映射）

非连续存储结构，底层数据结构是hash表。key不可以重复，不排序

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> unordered_map_test;
    unordered_map_test.insert(std::make_pair(1, 1));
    unordered_map_test.insert(std::make_pair(2, 2));

    for (auto iter : unordered_map_test) {
        std::cout << "key: " << iter.first << ", value: " << iter.second << std::endl;
    }

    return 0;
}

map、unordered_map比对（转化为红黑数和hash表的比对）

1. 插入/删除/查找时间复杂度
   map:插入和删除时间复杂度都是：log(n)+再平衡时间，查找时间复杂度是：log(n)
   unordered_map:插入/删除/查找时间复杂度：理想状况下（没有hash冲突）为O(1)，最坏情况下的时间复杂度为O(n)
2. 占用内存
   map:每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间
   unordered_map:Hash事先就应该分配足够的内存存储散列表（即使有些槽可能遭弃用）。
   因此map占用的空间更小
   总结：
3. 如果需要排序，一定使用map
4. 对于根据key查询value的问题，unordered_map的效率更高

set（集合）

非连续存储结构，底层数据结构是红黑树。value不可以重复，自动按照value从小到大排序

#include <iostream>
#include <set>

int main() {
    std::set<int> set_test;
    set_test.insert(1);
    set_test.insert(2);

    for (auto iter : set_test) {
        std::cout << iter << std::endl;
    }

    return 0;
}

multiset（多重集合）

非连续存储结构，底层数据结构是红黑树。value可以重复，自动按照value从小到大排序

#include <iostream>
#include <set>

int main() {
    std::multiset<int> multiset_test;
    multiset_test.insert(1);
    multiset_test.insert(1);
    multiset_test.insert(2);

    for (auto iter : multiset_test) {
        std::cout << iter << std::endl;
    }

    return 0;
}