1. 非关联容器
在我们看到的众多数据结构书籍中，最开始介绍过时间复杂度和空间复杂度后，接下来由简入难，分别是数组，链表和树。很多程序语言都提供了自己的标准实现，这里我们以C++为例。在C++标准库(STL)中，有两个基于堆分配的容器，分别对应数组和双向链表，std::vector和std::list。在后续的说明中，所有的实验都是基于这两个容器，但是其适用于任何基于节点的数据结构，不只是C++标准库中的。开始之前，都知道这两种数据结构在内存的中的存储形式是不同的，数组在内存中地址是连续的，链表的内存地址是非连续的（如下图）。
插入元素比较
在数组中插入一个元素，需要将插入位置后面的元素向后移动，时间复杂度是O(N)；但是向双向链表中插入一个元素需要分配一个节点，并设置4个指针，时间复杂度是O(1)。自然，对于很大的常数N，在链表中插入要快速的多。
读取元素比较
对于这两种容器，按顺序读取所有元素的时间复杂度是O(N)。但是，数组的读取速度仍旧比链表快。缓存(cache)和预取(prefetch)机制对数组读取是有利的，但是对链表的读取没有任何帮助。
从理论上来说，以上的说法是正确的，但在现代计算机上，真正的性能是如何的？我们可以通过实验来验证，通过不停地修改N的值，该程序可以得到在数组和双向链表的中间值右边插入数值0所消耗的时间。所用机器配置如下图:
#include<iostream> #include<vector> #include<list> #include<algorithm> #include<random> #include<ctime> usingnamespace std; constsize_t N = 50000; int main() { doublestart_t, end_t; std::vector<size_t> vec(N); std::list<size_t> lst(N); //The vector and list has same N elements for(size_t i = 0; i < vec.size(); ++i) { vec[i] = i + 1; lst.push_back(i + 1); } //insert 100 right before the the first occurence of 3 start_t= clock(); vec.insert(std::find(vec.begin(), vec.end(), 3), 100); //Tv end_t= clock(); std::cout << "vector cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; start_t= clock(); lst.insert(std::find(lst.begin(), lst.end(), 3), 100); // Tl end_t= clock(); std::cout << "list cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; return0; }
很明显，这样的线性搜索对于两种容器来说都是O(N),正如我们已经看到的，向vector插入一个元素是一个O(N)操作，向list插入一个元素是O(1)操作。向数组插入元素时，把少量的元素向右移动代价是很小的，毫无疑问应该期待Tv < Tl；但是当N是多少时，移动元素的代价会使Tl < Tv? 应该存在这样的一个临界值N。下面的表格是插入元素的实验结果：
| Size | std::vector | std::list | list/vector |
| 10000 | 0ns | 0ns | null |
| 50000 | 0ns | 1e+06ns | null |
| 100000 | 0ns | 2e+06ns | null |
| 1000000 | 6e+06ns | 2.1e+07ns | 3.5 |
| 10000000 | 5.5e+07ns | 2.03e+08ns | 3.69 |
| 100000000 | 5.79e+08ns | 2.169e+09ns | 3.746 |
| 500000000 | 3.6342e+10ns | 2.7049e+11ns | 5.638 |
我们发现，没有这样的一个临界值N，使得在双向链表中插入元素比数组快。线性内存访问模式会使用CPU的pre-fetcher，其作为一个无限大小的LN+1缓存。但是指针节点的数据结构没有这点好处，所以总是更慢一点。所以，如果你的关心迭代速度，就不要使用基于节点的容器，大多数情况下，程序更关注迭代速度。实际上，不管是插入或者删除操作，当你试图去寻找正确的位置，这时程序就需要迭代。所以，一般不要使用链表。
但是，在写程序时，总是会有适合链表的时刻（虽然很少）：
1.用分离链表法去解决hash冲突的时候，对于相同的hash key值，使用链表来存储，将新的节点插入链表的头部；2.如果需要引用稳定性，则可能需要一个链表，因为节点不会移动。如果指向一个节点，并对除了所指向的节点之外的任何内容执行插入或擦除操作，该指针将保持有效。3.实现一个软件LRU或MRU缓存，通常使用链表，并有指针指向缓存的所有元素。当使用其中一个时，将其从链表中拉出，并将其放在开头或结尾。
别的一般情况下，相比std::list，更倾向于选择std::array和std::vector。
2. 关联容器
“关联容器”是一个来自c++标准的术语。关联容器通常称为映射或字典。它们将一组键一对一地关联到一组值上。换句话说，您可以将一个键及其关联值插入到容器中，然后通过传递该键请求该值。在C++ STL中，包括std::map和std::set。这两个容器都以红黑树的方式实现，因此可以按照键排序的顺序遍历元素。
std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.
从c++ 11开始，还有散列关联容器std::unordered_map和std::unordered_set。顾名思义，这些元素没有按顺序排列。
这里，我们讨论有序的，其底层结构是红黑树的容器，内存存储结构如下图：
在有序数组和树中，查找一个特定值的时间复杂度是O(log(N))，并且由于在任何二叉搜索中都要在内存中跳跃，所以数组的速度并没有加快。
将一个元素插入到已排序的数组中需要先进行搜索，然后再进行插入(包括将后面的所有元素后移)，时间消耗为O(log(N) + N)或者说O(N)。插入到树中需要搜索、分配，可能还需要重新平衡树，时间复杂度是O (log (N))。对于较大的N，在树中插入自然要快得多。
需要注意的是，由于插入时间的xx性，填充一个排序数组是O(N * N)，填充红黑树是O(N * log(N))。对于两个容器，按顺序读取所有元素的时间是O(N)。同样，读取数组中的值要快得多。事实上，树中的迭代速度甚至比链表中的还要慢。下面的测试代码是基于vector_vs_map稍作改动。
#include<iostream> #include<map> #include<vector> #include<algorithm> #include<ctime> constsize_t N = 1000000; volatilesize_t acc = 0; typedef std::vector<std::pair<size_t, size_t>> vecss; typedef std::map<size_t, size_t> mapss; struct firstPairComp { booloperator()(const vecss::value_type& lhs, const vecss::value_type& rhs) { return lhs.first < rhs.first; } }; void insert_in_vec(const std::vector<size_t>& orderVec) { vecss vals; vals.reserve(N); doublestart_t, end_t; start_t= clock(); for(size_t i = 0; i < N; ++i) { vecss::value_type val(orderVec[i], rand()); std::pair<vecss::iterator, vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); vals.insert(res.second, val); } end_t= clock(); std::cout << "vector insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } void find_in_vec(const std::vector<size_t>& orderVec) { vecss vals; vals.reserve(N); for(size_t i = 0; i < N; ++i) { vecss::value_type val(orderVec[i], rand()); std::pair<vecss::iterator, vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); vals.insert(res.second, val); } doublestart_t, end_t; start_t= clock(); for(size_t i = 0; i < N; ++i) { vecss::value_type val(orderVec[i], 0); std::pair<vecss::iterator, vecss::iterator> res = std::equal_range(vals.begin(), vals.end(), val, firstPairComp()); acc += res.first->second; } end_t= clock(); std::cout << "vector find cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } void insert_in_map(const std::vector<size_t>& orderVec) { mapss vals; doublestart_t, end_t; start_t= clock(); for(size_t i = 0; i < N; ++i) { mapss::value_type val(orderVec[i], rand()); vals.insert(val); } end_t= clock(); std::cout << "map insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } void find_in_map(const std::vector<size_t>& orderVec) { mapss vals; for(size_t i = 0; i < N; ++i) { mapss::value_type val(orderVec[i], rand()); vals.insert(val); } doublestart_t, end_t; start_t= clock(); for(size_t i = 0; i < N; ++i) { mapss::iterator it = vals.find(orderVec[i]); acc += it->second; } end_t= clock(); std::cout << "map insert cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } void iter_vec() { vecss vals; vals.reserve(N); for(size_t i = 0; i < N; ++i) vals.push_back(vecss::value_type(i, rand())); vecss::value_type *begin= &vals[0]; doublestart_t, end_t; start_t= clock(); for(size_t i = 0; i < N; ++i) acc += begin[i].second; end_t= clock(); std::cout << "vector iterator cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } void iter_map() { mapss vals; for(size_t i = 0; i < N; ++i) vals.insert(mapss::value_type(i, rand())); doublestart_t, end_t; start_t= clock(); mapss::const_iterator end= vals.end(); for(mapss::const_iterator it = vals.begin(); it != end; ++it) acc += it->second; end_t= clock(); std::cout << "map iterator cost time: "<< ((end_t- start_t) * 1000000) << " ns"<< std::endl; } int main() { std::vector<size_t> orderVec(N); for(size_t i = 0; i < N; i++) { orderVec[i] = i + 1; } insert_in_vec(orderVec); insert_in_map(orderVec); find_in_vec(orderVec); find_in_map(orderVec); iter_vec(); iter_map(); system("pause"); return0; }
测试结果在下面的表格(注意：这里的vector是有序的),单位是纳秒(ns)：
| Size | Insert Comparison | Find Comparison | Iterator Comparison | ||||||
| Vector | Map | Map/Vector | Vector | Map | Map/Vector | Vector | Map | Map/Vector | |
| 10000 | 1e+06 | 2e+06 | 2 | 1e+06 | 1e+06 | 1 | 0 | 0 | null |
| 50000 | 4e+06 | 7e+06 | 1.75 | 3e+06 | 3e+06 | 1 | 0 | 1e+06 | null |
| 100000 | 8e+06 | 1.5e+07 | 1.875 | 7e+06 | 7e+06 | 1 | 0 | 2e+06 | null |
| 1000000 | 9.6e+07 | 1.74e+08 | 1.813 | 7.2e+07 | 7.2e+07 | 1 | 2e+06 | 2.1e+07 | 10.5 |
| 10000000 | 1.097e+09 | 1.908e+09 | 1.74 | 8.23e+08 | 7.9e+08 | 0.96 | 1.5e+07 | 2.2e+08 | 14.67 |
| 100000000 | 1.3488e+10 | 2.3679e+10 | 1.76 | 7.83e+09 | 8.888e+09 | 1.13 | 1.84e+08 | 2.117e+09 | 11.51 |
从上面可以看出，对于迭代，没有比线性内存访问更好的方法了，并且插入操作，map也没有比有序数组更好。如果只关心快速插入、删除和查找怎么办?使用散列表，如std::unordered_map或std::unordered_set。这些操作平摊了O(1)的运行时间，比O(log(N))要好。当你决定使用树的时候，记住:
•对于关联数据结构的插入、擦除和查找操作，哈希几乎总是优于树。•对于相当小的工作集，排序数组具有无与伦比的迭代速度，但代价昂贵的插入和擦除。
因此，如果您关心迭代速度或插入、删除和查找的性能，就不要使用基于树的数据结构。同样，可能会发现少数场景下需要考虑稳定性。
3. 总结
避免使用链表，除非:
•你需要参考稳定性；•你正在实现一个软件MRU/LRU缓存。
使用数组来代替。std::vector生成一个良好的堆分配数组，而std::array生成一个适合堆栈的固定大小的良好数组。
避免使用树结构,除非:
•需要参考稳定性；•操作的成本并不依赖于树中的元素数量(如trie)。
对于小的N值，使用排序数组(boost::container::flat_map构造了一个良好排序的数组，就像一个有序的std::vector一样）。
flat_map is similar to std::map but it's implemented by as an ordered sequence container. The underlying sequence container is by default vector but it can also work user-provided vector-like SequenceContainers (like static_vector or small_vector).
对于大的N值，使用哈希表(std::unordered_map和std::unordered_set)。
本文作者：focuscode，16年控制工程毕业，不慎误入C/C++怀抱，希望有一天可以给简历的精通C++加上双引号~。
声明：本文为 脚本之家专栏作者 投稿，未经允许请勿转载。
