STL与泛型编程 第三周 博览网

deque

• deque其实是分段连续，即在其内部并不是连续分布的。但抽象为连续的分布。如下图：
  image.png
  image.png
  deque可以前后扩充。其中map可以认为是一个控制中心，它其实是一个vector，当map容量不够时进行扩充，扩充后会进行数据copy，但是它会将数据copy到中间位置。
• deque模拟连续空间由deque iterator完成，
• array、vector、deque均抽象为连续空间可以使用+=、-=、[]运算符。其他容器则不可以。

• stack、queue使用的是deque，只不过取消掉一部分功能。stack、queue其实就是一个adapter，它们都不允许遍历，也不提供iterator。stack、queue都可以选择list或者deque作为底层结构，但是deque为默认底层结构，速度更快一点。stack可以选择vector作为底部支撑，但是queue不可以选择vector作为底层结构。

  
  image.png
  image.png
• stack、queue默认基于deque实现，priority_queue是在vector上实现的。priority_queue还要求随机访问能力，故它只能构造在vector和deque之上，不能基于list构造。
• stack包含在stack头文件中，queue和priority_queue均在queue头文件中。

各容器特殊操作

• array不支持C c(b,e)操作，即构造C，将迭代器b和e指定的范围内的元素拷贝到C
• vector deque array支持迭代器+=操作。其他均不支持。包括list。
• list不支持迭代器的比较运算符（除了== !=）
• forward_list因为无法保证size运算的常数复杂度，所以不支持size()运算.
• 所有容器都支持== !=操作，但只有顺序容器支持< <= > >=操作。比较两个容器其实就是将元素逐对进行比较。
• 只有顺序容器可以（不包括array）的构造函数才能接收容器大小的参数。例如：
  list<string> a(4,"haha");
array<int,4> c;//array在创建时必须指定大小
• 只有vector,array,deque,string提供快速随机访问容器。使用at()成员函数可以检查是否越界，如果下表越界会抛出out_of_range异常。
• 访问容器前必须检查是否未空，否则出现知名错误。
• 除了array外，swap()成员函数不对任何元素进行拷贝、删除和插入操作，它不会移动元素本省，它只是改变容器内部的数据结构，因此可以保证在常数时间内完成，因此swap后指向元素的迭代器、引用和指针仍指向这个元素。
• swap 两个array会真正交换它们的元素。因此指向元素的迭代器、引用和指针指向array的相同位置，但是元素值已经不同了。
• swap有成员函数版本和非成员函数版本，统一使用非成员函数版本是一个好习惯。
• 赋值相关预算会导致指向左边容器内部的迭代器，引用和指针失效。
• 对vector、string、deque插入元素（array不支持此操作）会使指向容器的迭代器、引用和指针失效。导致无法再使用，使用时可以使用insert()返回的值对其重新进行赋值。
• 删除deque中除首尾元素之外的任何元素都会使所有迭代器、引用和指针失效。指向vector或string中删除点后位置的迭代器、引用和指针都会失效。
• 对于vector、deuqe、list的insert(p)会返回指向新添加元素的第一个元素，插入位置为迭代器p指向元素的前面；erase(p)会删除p指向的元素，返回一个被删除元素之后元素的迭代器。
• 对于forward_list由于其特殊性，insert_after(p)为在p之后插入元素，返回一个指向最后一个元素的迭代器;erase_after(p)为删除p指向的位置之后的元素，返回一个被删除元素之后元素的迭代器。
• 由于向迭代器添加元素和删除元素的代码可能会使失效，因此必须保证每次改变容器的操作之后都正确地定位迭代器。这个建议对于vector、string、和deque尤为重要。
• 当我们添加/删除vector或string的元素后，或者在deque中首元素外任何位置添加/删除元素后，原来end返回的尾后迭代器均失效，因此不要轻易保存尾后迭代器进行循环判断，而是在每次循环后都进行更新，end()的运行速度一般很快。

string

• 对于string还有特殊版本的insert和earse汉本，它接收的第一个参数是下表，而不是迭代器。

associative container - rb_tree

• associative container包括map、set、multiset、multimap其底层支持就是一个RB_Tree.
• 红黑树是一种平衡二叉搜索树。这种结构有利于search和insert。我们不应使用RB_Tree的iterator改变元素的值，因为元素在rb_Tree中的序列是严格排列规则的。rb_tree提供两种insertion操作：inser_unique（）和insert_equal（）,地址一种表示节点key在树中独一无二，重复的key无法放入树中，后者表示节点可以重复，重复的key可以被放入树中。
  image.png
• set/multiset提供遍历操作及iterator。无法使用iterator改变key值。
• map/multimap提供遍历操作及iterator。通过iterator无法改变map和multimap的key值，但是可以改变它的data值。
• map的operator[]有特殊的功能，可以通过它来方元素进去。multimap则无此功能。

unorder container - hashtable

• unorder_map/multimap unorder_set/multitset底层结构均为容器hashtable。

• hashtable的工作原理

  
  image.png
  

  如果元素个数超过buckets内的个数时，则buckets进行扩充，变为原来的2倍数字附近的质数的个数。在gun2.9中内置的hashtable中buckets的大小，初始为53，第一次扩大为97，第三次扩大为193，以此类推。每一次buckets的扩充都消耗大量时间，包括vector的增长以及元素的重新分配。

• hashtable类没有为std:: string提供默认的hashfunction，所以要自己写一个hashfunction来处理字符串产生hashcode。但是为C风格的字符串提供了默认的产生的hashcode的hashfunction。
• 我们通常不对关联容器使用泛型算法。关联容器可以使用只读取元素的算法，一般不使用泛型find算法，而使用关联容器专门的find算法。
• 关联容器的关键字类型要嘛自己有定义的<操作符，要嘛在实例化泛型时传入一个函数指针来提供比较运算。

bool compareIsbn(const Book &lhs,const Book &rhs) {...}//Book是一个类
set<Book,decltype(compareIsbn)*> bookstore(compareIsbn);//创建实例时传入一个比较函数
//或者如下
typedef bool (*pf) (const Book &,const Book &);
set<Book,pf> bookstore(compareIsbn)

• 对于set或者map，insert(或emplace)返回一个pair类型，first是一个迭代器，指向给定关键字元素，second为一个bool值，指示是否插入成功。
• 对于允许重复关键字的容器，insert或者emplace只返回一个指向插入元素的迭代器。
• 对于map进行下表运算符操作时，如果元素不在map中，则会添加元素到map中，因此如果只是向知道一个元素是否已在map中，但不存在时不想添加元素时不可以使用下表运算符
• 对于无序关联容器，不需要提供<运算符，只需要提供==运算符即可。
• 默认情况下，无序容器使用关键字类型的==运算符来比较元素，它们还使用一个hash<key_type>类型的对象来生成每个元素的哈希值；标准库为内置类型（包括指针）、string和只能指针类型定义了hash，因此我们可以直接定义关键字是内置以上类型的无序容器；但是我们不能直接定义关键字类型为自定义类类型的无序容器，必须提供自己的hash模板版本。自定义类型版本

unorderde_multiset<Book,decltype(hasher)*,decltype(eqOp)* > bookstore(42,hasher,eqOp);
/*hasher,eqOp为函数名，初始化对象传入的参数分别为同大小、哈希函数指针、相等行判断运算符指针*/
unordered_set <Foo,decltype(FooHash)* >fooSet(10,FooHash)；
/*如果在FOO类中定义了==运算符，则可以只重载哈希函数*/