2 容器的结构与分类

容器分类¶

容器可分为三种

Sequence Containers：序列容器
Associative Containers：关联式的容器
Unordered Containers：不定序的容器（在这一刻可能是这个顺序，在一些操作之后，顺序可能又变了）

容器又可分为两种：序列容器、关联式容器

不定序容器其实就是一种关联式容器，所以这个分类可能不是很好
更恰当的分类是序列容器与关联式容器两类。

可以把关联式容器当成小型的关联数据库，它的查找是非常快的。

红色框是C++11之后新增的
queue是队列，deque是双向队列
list其实是一个双向环状链表，环状只是为了实现上的遍历，在实际使用和功能上，当成双向链表即可
set、map内部是用红黑树实现的，红黑树是一个高度平衡二叉树。平衡：会保持左右是平衡的，保证查找的效率
set、map表示内部元素不能重复。而multiset、multimap表示key可以重复

array¶

#define ASIZE 1000000000

int compareLongs(const void* a, const void* b) {
    return ( *(long*)a - *(long*)b );
}

array<long, ASIZE> c;

for(long i=0; i<value; ++i) {
    try {
        snprintf(buf, 10, "%d", rand());
        c.push_back(string(buf));
    } catch (exception& e) { //push_back可能会出错，没有那么多内存了
        cout << e.what();
        abort(;
    }
}

c.size();
c.front();
c.back();
c.data();

//排序
qsort(c.data(), ASIZE, sizeof(long), compareLongs);
//二分法查找（二分查找法的前提：元素有序）
long* pItem = (long*)bsearch(&target, c.data(), ASIZE, sizeof(long), compareLongs);

vector¶

vector只能向后增长，扩容之后的大小是原先的两倍。

int compareStrings(const void*a, const void* b) {
    if( *(string*)a > *(string*)b ) return 1;
    else if( *(string*)a < *(string*)b ) return -1;
    else return 0;
}

vetor<string> c;

c.push_back("23123");
c.size();   //真正元素的个数
c.front();
c.back();
c.data();   
c.capacity();   //容量

auto pItem = ::find(c.begin(), c.end(), target);

sort(c.being(), c.end()); //排序
string* pItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareStrings); //二分查找

list¶

list<string> c;

c.push_back("1234");

c.size();       //目前的大小
c.max_size();   //list可放的容量
c.front();
c.back();

forward_list¶

【slist】gnu编译器中的单向链表，方法和stl规定的很像

#include<ext\slist>

_gnu_cxx::slit<string> c;

//其他都

deque¶

deque两头都可以添加，那它是怎么做到的呢？

一个deque分成好几段存储，一段称之为buffer
一个buffer可以放很多元素

stack¶

stack和queue没有提供迭代器，如果有迭代器，可能会与本身的定义有冲突。比如，你拿到迭代器之后，要修改，或前面插入等，这样是不行的，因为stack和queue本身是有限制的容器

queue¶

multi（可重复）¶

multiset¶

set、multiset中，只存有一个元素。与map相比，set的key和value相同。multi允许元素相同

基于红黑树，元素的位置根据算法动态生成
::find()全局函数的find肯定会比容器自己的find更慢，因为容器定制的find，速度肯定会快些

multimap¶

基于红黑树，元素有两个部分，key和value，找的时候用key来找。multimap中key可以重复。

unordered_multiset¶

multiset、multimap是基于红黑树实现的，红黑树是非常严谨的，效率很高。而unordered_multiset是基于哈希表。

bucket篮子。篮子一定比元素多，这是设计的考量
每个篮子出去的链表不能太长
那怎么算太长呢？经验法则：如果元素的个数≥篮子的个数，那么篮子的个数就要扩充（大约两倍这么多），原来的元素从新打散，放在不同的篮子上。
load_factor载重因子

查找：容器.find()比std::find()快

unordered_multimap¶

用哈希表

无multi（不可重复）¶

key不可重复，即根据key会去重。

set¶

kye就是value，value就是key

map¶

key不能重复，放入重复的会失败
multimap不能用[]操作符，而map可以，[]中就是key

总结¶

容器的结构与分类¶

不同容器之间的关联性¶

注释一：图中，以缩进的形式表示基层和衍生层的关系。所谓衍生是指复合关系。如

rb_tree是指红黑树（高度平衡的二叉树）；而set、map、multiset、multimap在rb_tree下面缩进了一个空格。代表的是，set、map、multiset、multimap是衍生层，rb_tree是基层。复合的意思就是：衍生层has-a基层。set里有一个rb_tree在帮它管理各个元素
heap has-a vector
priority_queue has-a heap
stack has-a deque
queue has-a deque

注释二：非标准，代表该容器是非标准的容器

当初slist是非标准。但在C++11新标准下，slist命名为forward_list，被纳为新标准的容器
hash_set、hash_map、hash_multiset、hash_multimap当初是非标准容器。但在C++新标准下，它们也被容纳进来，但名字改为unordered_set、unordered_map、unordered_multiset、unordered_multimap

注释三：蓝色的部分，代表将这些容器做出一个object，这个object所占的大小。即vector<int> arr; sizeof(arr)的值

这里sizeof的大小是指容器的大小
而容器元素的大小并不在容器中控制，而是通过指针控制，它不会影响容器本身的大小