Open rainit2006 opened 5 years ago
■ Sequence Container No find function.
vector: 单向 deque:双向 list: 双向指针。 list的splice函数非常快O(1),无论多么大的list分割成子list仅需要O(1), 很多人仅仅是为了splice函数而是用list。
forward list: just have a forward pointer.
■Associative Container: binary tree always sorted, No push_back, No push_front,
Set : no duplicates(不能有重复的元素) 在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树:红黑树,也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树,所以被STL选择作为了关联容器的内部结构。
set<int> myset;
myset.insert(1); //O(log(n))
set<int>::interator it;
it = myset.find(7); //O(log(n))
it = myset.begin();
myset.insert(it, 9); //O(log(n))->O(log(1)), very fast.
multiset: allows duplicate items.
set/multiset: The value of elements cannot be modified. read-only.
mat/ multimap : key-value. multimap allows duplicated key.
map<char, int> mymap;
mymap.insert(pair<char, int>('a', 100));
mymap.insert(make_pair('z', 20));
STL曾经存在的问题: https://www.zhihu.com/question/38225973 以前STL对自定义memory allocator支持不好,而我司(曾经)极度依赖自定义memory allocator。如果在几个STL容器里使用了几种不同的自定义allocator,同时再使用template就会出问题。因此我司写了自己的容器类,接口和实现几乎完全照搬STL,但是改写了memory allocator部分。
作者:Steven Wang 链接:https://www.zhihu.com/question/38225973/answer/75481218 来源:知乎 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
■Unsorted Container: Hash table
ーーー