C++ STL容器

标签：复杂度   eve   reverse   没有   test   pos   size   默认   cond   

vector（向量）

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

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

#include 
#include 
#include 
#include 

int main() {
    std::vector vector_test;
    vector_test.push_back(1);
    std::cout , less升序，greater降序，默认为非降序排序
    std::sort(vector_test.begin(), vector_test.end(), std::greater());
    std::sort(vector_test.begin(), vector_test.end(), std::less());

    // cbegin(),cend(),crbegin(),crend()分别是的begin(),end(),rbegin(),rend()的const版本
    // r:reverse,反向
    for (auto iter = vector_test.cbegin(); iter != vector_test.cend(); ++iter) { 
        std::cout 

list（列表）

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

#include 
#include 

int main() {
    std::list 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 

deque（双端队列 double-end queue）

连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。

#include 
#include 

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

    for (int index = 0; index 

vector、list、deque的选择

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

map（映射）

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

#include 
#include 

multimap（多重映射）

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

#include 
#include 

unordermap（不排序映射）

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

#include 
#include 

int main() {
    std::unordered_map 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 

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 
#include 

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

    for (auto iter : set_test) {
        std::cout 

multiset（多重集合）

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

#include 
#include 

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

    for (auto iter : multiset_test) {
        std::cout 

C++ STL容器

标签：复杂度   eve   reverse   没有   test   pos   size   默认   cond   

原文地址：https://www.cnblogs.com/ghx-kevin/p/12686864.html