STL容器概述

STL容器

1、容器概述

1.1、容器分类

1.1.1、顺序容器：提供对元素序列的访问，顺序容器为元素连续分配内存或将元素组织为链表，元素的类型是容器成员value_type。

vector<T, A>空间连续分配的T类型元素序列；默认选择容器list<T, A>T类型元素双向链表；当需要插入/删除元素但不移动已有元素是选择它。forward_list<T, A>T类型元素单向链表；很短的或空序列的理想选择deque<T, A>T类型元素双向队列；向量和链表的混合；对于大多数应用，都比向量和链表其中之一要慢。

模板参数A是一个分配器，容器用它来分配和释放内存, 默认值 std::allocator。

1.1.2、有序关联容器：提供基于关键字的关联查询。

map<K, V, C, A>从K到V的有序映射；一个（K, V）对序列multimap<K, V, C, A>从K到V的有序映射；允许重复关键字set<K, C, A>K的有序集合multiset<K, C, A>K的有序集合；允许重复关键字

C是比较类型，默认值 std::less(K)； A是分配器类型，默认值 std::allocator<std::pair<const K, T>>。这些容器通常采用平衡二叉树（通常红黑树）实现。

1.1.3、无序关联容器：

unordered_map<K, V, H, E, A>从K到V的无序映射；unordered_multimap<K, V, H, E, A>从K到V的无序映射；允许重复关键字unordered_set<K, H, E, A>K的无序集合unordered_multiset<K, H, E, A>K的无序集合；允许重复关键字

H是关键字类型K的哈希函数类型，默认值 std::hash。E是关键字类型K的相等性测试函数类型，默认值 std::equal_to, 用来判断哈希值相同的两个对象是否相等。A是分配器类型。这些容器都是采用溢出链表法的哈希表实现。

关联容器都是链接结构（树），节点类型为其成员value_type。

1.1.4、容器适配器：提供对底层容器的特殊访问。

priority_queue<T, C, Cmp>T的优先队列；Cmp是优先级函数类型queue<T, C>T的队列，支持push() 和 pop()操作stack<T, C>T的栈，支持push() 和 pop()操作

一个priority_queue的默认优先级函数Cmp为std::less。queue的默认容器类型C为std::deque，stack和priority_queue的默认容器类型C为std::vector。

1.2、容器对元素的要求

1.2.1、比较操作

注意 C 风格字符串(即const char*)上的 < 比较的是指针值，因此如果用 C 风格字符串作为关键字，关联容器将不能正常工作，为了让这样的关联容器正常工作，就必须使用基于字典序的比较操作。

struct Cstring_less
{
    bool opreator()(const char *p, const char *q) const
    {
        return strcmp(p, q) < 0;
    }
};

map<char*, int, Cstring_less> m; //map使用strcmp()比较const

2、操作

2.1、标准库容器操作复杂性

标准容器操作复杂性 [] 列表头部尾部迭代器 vector 常量 O(n)+ 常量+ 随机 list 常量常量常量双向 forward_list 常量常量前向 deque 常量 O(n) 常量常量随机 stack 常量 queue 常量常量 priority_queue O(log(n)) O(log(n)) map O(log(n)) O(log(n))+ 双向 multimap O(log(n))+ 双向 set O(log(n))+ 双向 multimap O(long(n))+ 双向 unordered_map 常量+ 常量+ 前向 unordered_multimap 常量+ 前向 unordered_set 常量+ 前向 unordered_multiset 常量+ 前向 string 常量 O(n)+ O(n)+ 常量+ 随机 array 常量随机内置数组常量随机 valarray 常量随机 bitset 常量随机

头部操作：表示在第一个元素之前的插入和删除操作。

尾部操作：表示在最后一个元素之后的插入和删除操作。
列表操作：表示在任意位置的插入和删除操作。

迭代器：“随机”表示随机访问迭代器，“向前”表示前向迭代器，“双向”表示双向迭代器。

时间复杂度：

常量又表示为O(1)，表示时间复杂度是个常量，通常代表时间复杂度低。
O(n)表示操作花费非时间与元素数目成正比，元素增加n倍，操作时间也增加n倍。通常代表时间复杂度较高。
O(n*n)表示元素增加n倍，操作时间就增加n^2倍。通常代表时间复杂度很高，n很大时，对资源消耗来说是灾难。
O(logn)表示元素增加n倍，操作时间增加logn倍（以2为底的对数）。通常代表时间复杂度较低。
O(nlogn)表示元素增加n倍，操作时间增加nlogn倍。时间复杂度高于O(n)低于O(n*n)。

时间复杂度后加 “+” 表示时间复杂度可能会更高，如vector增加元素时，可能需要重新分配资源。

值得注意的是，操作效率还取决于计算机的内存和处理器构架的细节，比如通过链接获取下一个元素（list情形）的代价会远高于在一个vector中获取下一个元素的代价（元素是连续存储）。因此对操作效率的评估不能完全简单的依赖于对复杂性的评估，而是要进行实际的测试。