1 容器

1.1 容器的概念

模板类的集合，容器中封装了组织数据的方法

1.2 容器内对象的拷贝

容器内元素的改变、扩充或删除总是伴随着拷贝。如果将一个对象插入容器中，实际上是将这个对象拷贝进这个容器。拷贝是基于此对象对应class的拷贝构造函数和拷贝赋值操作符。
如果对于某个class来说，他的拷贝非常昂贵，那么拷贝和可能成为容器的瓶颈。此外，拷贝还有可能带来分割的问题，若以基类建立容器，而插入派生类，那么派生部分会被切割。

1.3 补充

1 用empty来代替检查size()是否为0

2 当你想给容器一组全新的值时，你可以使用assign，而 operator=则不能满足你的要求。

3 使用区间成员函数操作替代单元素函数

比如区间只要insert一次，单元素要n次才能插入完一个区间，推荐使用如下的区间成员函数：

//区间构造
container::container(InputIterator begin, // 区间的起点
InputIterator end); // 区间的终点
 
//区间插入
void container::insert(iterator position, // 区间插入的位置（对于关联容器，无需position参数）
InputIterator begin, // 插入区间的起点
InputIterator end); // 插入区间的终点
 
//区间删除
iterator container::erase(iterator begin, iterator end);//序列容器返回iterator，关联容器返回void
 
//区间赋值
void container::assign(InputIterator begin, InputIterator end);

4 容器包含new的指针时，在容器对象被析构之前要delete掉

如：for循环删除容器中的所有指针，缺点是非异常安全，析构过程中抛出异常之前，会发生内存泄漏

void doSomething()
{
  vector<Widget*> vwp;
  for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
    vwp.push_back(new Widget);
  ...
  for (vector<Widget*>::iterator i = vwp.begin(); i != vwp.end(); ++i) {
    delete *i;
  }
}

解决办法：使用智能指针

void doSomething()
{
  typedef boost::shared_ ptr<Widget> SPW; 
  vector<SPW> vwp;
  for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
    vwp.push_back(SPW(new Widget)); // 从一个Widget建立SPW, 然后进行一次push_back
... // 使用vwp
} 

5 永不建立auto_ptr的容器

6 慎重选择删除元素的方法

● 去除一个容器中有特定值的所有对象：
如果容器是vector、string或deque，使用erase-remove惯用法。
如果容器是list，使用list::remove。
如果容器是标准关联容器，使用它的erase成员函数。
● 去除一个容器中满足一个特定判定式的所有对象：
如果容器是vector、string或deque，使用erase-remove_if惯用法。
如果容器是list，使用list::remove_if。
如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。
● 在循环内做某些事情（除了删除对象之外）：
如果容器是标准序列容器，写一个循环来遍历容器元素，每当调用erase时记得都用它的返回值更新你的迭代器。（内存连续的容器的迭代器在insert和erase时会失效）

for (SeqContainer<int>::iterator i = c.begin(); i != c.end();){
  if (badValue(*i)){
    logFile << "Erasing " << *i << '\n';
    i = c.erase(i); 
  } 
  else
    ++i;
}

如果容器是标准关联容器，写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。

AssocContainer<int> c;
...
for (AssocContainer<int>::iterator i = c.begin(); i != c.end(); /*nothing*/ ){ 
  if (badValue(*i)) c.erase(i++); 
    else ++i;
} 

7 切勿对STL容器的线程安全性有不切实际的依赖

解决办法：建立指针的容器，尤其是智能指针的容器。

2 序列式容器

序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序

2.1 vector

• 优点
  动态数组，实现动态扩容
• 缺点
  扩容过程是重新申请一片空间，将原空间的所有数据复制到该空间，再释放掉旧空间，因此非常耗时。解决办法是使用shrink_to_fit()或者 reserve() 成员方法预留足够大的空间，存完之后再通过swap() 成员方法去除 vector 容器多余的容量。

2.2 使用建议

在不同容器类型间，用户可以根据自己的需求做出权衡和取舍，例如：
默认使用顺序容器时vector，序列中存在频繁插入和删除时list，频繁使用序列首尾时deque等。
对如何选择容器，我们有如下建议：

(1)如果想在任意位置插入新数据，请选择顺序容器。

(2)如果不在意容器中元素的顺序，请使用哈希表。

(3)如果需要满足C++标准，请排除hash, slist和rope。

(4)如果想要实现随机访问，请使用vector，deque，string和rope。

(5)如果想要避免插入或删除元素时其他元素的拷贝构造移动，请远离连续内存容器。

(6)如果容器中的数据需要与C的布局兼容，请使用vector。

(7)如果关注容器查找速度，请考虑哈希表，排序vector和标准关联容器。

(8)如果希望容器不使用引用计数，请避免string和rope。

(9)如果希望插入与删除实现事务语义，即要求可靠回滚，请考虑节点容器，如list。

(10)如果希望最小化无效迭代器、指针和引用的影响，请使用节点容器。

(11)如果希望随机访问的顺序容器只有在序列尾部插入和删除时，迭代器、指针和引用才会无效，而其他情况均不会使其无效化，请使用deque。

2.3 另一个角度分类容器

(1)连续内存容器：它在一块或多块内存中存储元素，每块内存中存储多个元素。当一个元素被插入或删除时，同一个内存块中的其他元素要整体拷贝移动，这会影响程序的性能和异常安全性。常见的标准容器为vector,string和deque，非标准的rope也属于此类。
(2)结点类型容器：它在一块内存中只存取一个元素。插入和删除操作仅仅影响指向该节点的指针，而不会改变节点中的内容。常见的标准容器有list和slist，非标准的hash表也属于此类。

2.4 vector和string

8 vector和string优先于动态分配的数组

为减轻程序员的负担，推荐使用vector或者string。在多线程环境下使用string，由于string大多使用引用计数来优化内存分配和效率，但是在多线程环境下，同步操作可能带来更来的效率损耗。这时候可以用vector<char>来代替string。

9 使用reserve预留空间，避免内存的重新分配和拷贝

size()：返回该容器中有多少个元素
capacity()：返回该容器利用已分配的内存可以容纳多少个元素，可以用“capacity()-size()”得知容器在不重新分配内存的情况下还能插入多少个元素。
resize(container::size_type n)：强迫改变容器改变到包含n个元素的状态。如果n小于当前size，则容器尾部元素被析构；如果n大于当前size，则通过默认构造函数将新元素添加到容器的尾部；；如果n大于当前capacity，则先重新分配内存。
reserve(container::size_type n)：强制容器吧他的容量变成至少是n，前提是n不小于当前的大小。如果n小于当前容量，vector什么都不做；而string可能把自己的容量见效为size()和n中的最大值。
为了避免内存的重新分配和元素拷贝，可以使用reserve成员函数。
第一种方式是，若能确切知道大致预计容器中最终有多少元素，可以在容器声明后，立即使用reserve()，预留出适当大小的空间。
第二种方式是，先预留足够大的空间，当把所有元素都加入容器后，去除多余的容器。（使用resize()或参考条款17）

10 注意string实现的多样性

string的值可能会被引用计数，也可能不会。很多情况下会默认使用引用计数，但一般都会提供关闭默认选择的方法。

string对象大小的范围是一个char*指针大小的1倍到7倍。

创建一个新的字符串可能需要0次、1次或者2次动态分配内存。

string对象可能共享，也可能不共享其大小和容量信息。

string可能支持，也可能不支持针对单个对象的分配子。

不同的实现对字符内存的最小分配单位有不同的策略。

11 了解如何把vector和string数据传给旧的API

12 使用“swap技巧”除去多余的容量

13 避免使用vector<bool>

3 关联容器

关联容器与序列容器不同点在于关联容器都是键值对的形式。

3.1 set和map的总结

set：键值相同，键不能相同

• set以RBTree作为底层容器
• 所得元素的只有key没有value，value就是key
• 不允许出现键值重复
• 所有的元素都会被自动排序
• 不能通过迭代器来改变set的值，因为set的值就是键

map：键值是区分的，键不能相同，值可以相同

• map以RBTree作为底层容器
• 所有元素都是键+值存在
• 不允许键重复
• 所有元素是通过键进行自动排序的
• map的键是不能修改的，但是其键对应的值是可以修改的

3.2 补充

14 理解相等(equality)和等价(equivalence)的区别

标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数(默认为less)来决定保持怎样的顺序。等价的定义正是通过该比较函数而确定的，因此，标准关联容器的使用者要为所使用的每个容器指定一个比较函数(用来决定如何排序)。

15 为包含指针的关联容器指定比较类型

默认就是指针地址的排序，大部分情况下是需要自己重定义的

struct DereferenceLess {
	template<typename PtrType>
	bool operator()(PtrType pT1, PtrType pT2) const
	{
		return *pT1 < *pT2;
	}
};
 
int main()
{
	//std::set<std::string*> ssp; // std::set<std::string*> <==> std::set<std::string*, std::less<std::string*>>, 得不到预期的结果
	//std::set<std::string*, StringPtrLess> ssp;
	std::set<std::string*, DereferenceLess> ssp; // 与std::set<std::string*, StringPtrLess> ssp;的行为相同
	ssp.insert(new std::string("Anteater"));
	ssp.insert(new std::string("Wombat"));
	ssp.insert(new std::string("Lemur"));
	ssp.insert(new std::string("Penguin"));
 
	for (set<std::string*, DereferenceLess>::iterator it = ssp.begin(); it != ssp.end(); ++it) {
		fprintf(stdout, "%s\n", (**it).c_str());
	}
 
	return 0;
}

16 总是让比较函数在等值情况下返回false

比较函数的返回值表明的是按照该函数定义的排列顺序，一个值是否在另一个之前。相等的值从来不会有前后顺序关系，所以，对于相等的值，比较函数应当始终返回false。对set和map确实是这样，因为这些容器不能包含重复的值。对multiset和multimap也是这样。从技术上来说，用于对关联容器排序的比较函数必须为它们所比较的对象定义一个”严格的弱序化”(strict weak ordering)。(对于传递给像sort这类算法的比较函数也有同样的限制。)任何一个定义了”严格的弱序化”的函数必须对相同值的两个拷贝返回false。

17 切勿直接修改set或multiset中的键

18 考虑用排序的vector替代关联容器

对于许多应用，哈希容器可能提供常数时间的查找能力优于set、multiset、map和multimap的确定的对数时间查找能力。
插入和删除操作对于vector来说是昂贵的，但对于关联容器却是廉价的。这就是为什么只有当你知道”对数据结构的使用方式是：查找操作几乎从不跟插入和删除操作混在一起”时，再考虑使用排序的vector而不是关联容器才是合理的。否则，使用排序的vector而不是标准关联容器几乎肯定是在浪费时间。

19 当效率至关重要时，请在map::operator[]与map::insert之间谨慎做出选择

map的operator[]函数与众不同。它与vector、deque和string的operator[]函数无关，与用于数组的内置operator[]也没有关系。相反，map::operator[]的设计目的是为了提供”添加和更新”(add or update)的功能。map::operator[]返回一个引用。

对效率的考虑使我们得出结论：
当向映射表中添加元素时，要优先选用insert，而不是operator[]；
而从效率和美学的观点考虑，结论是：当更新已经在映射表中的元素的值时，要优先选择operator[]。

20 熟悉非标准的哈希容器

C++11中新增了四种关联容器，使用哈希函数组织的，无序的，即unordered_map、unordered_multimap、unordered_set、unordered_multiset。

3.4 序列容器与关联容器区别

STL是建立在泛型的基础上，但由于不同容器的特性不同（尤其是迭代器、指针和引用的类型与失效规则不同），支持所有容器的相同接口是不存在的。比如：

• 只有序列容器支持： push_front和push_back，
• 只有关联容器支持： logN时间复杂度的lower_bound、upper_bound和equal_range；

insert：当你向序列容器中插入对象时，该对象位于被插入的位置处；而当你向关联容器中插入对象时，容器会按照其排序规则，将该对象移动到适当的位置上。
erase：作用于序列容器时，会返回一个新的迭代器，但当它作用于关联容器时则没有返回值。

4 迭代器

容器都是用来存储数据的，都具有插入、删除、遍历、查找等操作，能不能有一个统一的操作将容器和算法分离开来。
迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

21 iterator优先于const_iterator、reverse_iterator以及const_reverse_iterator

22 使用distance和advance将容器的const_iterator转换成iterator

某些容器仅能支持iterator作为参数，但是现在只有const_iterator。
解决办法，强转类型。
建立一个iterator指向那个容器的起始位置，然后计算出偏移量，使得获得一个新的iterator等价于const_iterator。

23 正确理解由reverse_iterator的base()成员函数所产生的iterator的用法

24 对于逐个字符的输入请考虑使用istreambuf_iterator

5 算法

25 确保目标区间足够大

26 了解各种与排序有关的选择

排序分类：
给定区间的所有元素进行排序：std::sort 采用类似快速排序算法，复杂度为Nlog2(N)
给定区间的所有元素进行稳定排序：std::stable_sort 采用类似归并排序，复杂度为Nlog2(N)
给定区间的部分元素进行排序：std::partial_sort 采用类似堆排序，复杂度为N*log(M)
自定义排序规则：
当容器中的元素是一些标准类型(如int、string)时，可以直接使用函数模板。但其元素是自定义类型或者需要按照其它方式排序时，需要自己来实现，有两种方法：一种是自己写比较函数，另一种是重载类型操作符”<”。std::sort/std::stable_sort/std::partial_sort中最后一个参数可以是函数指针类型或函数对象类型。

27 对包含指针的容器使用remove这一类算法时要特别小心

当容器中存放的是指向动态分配的对象的指针的时候，应该避免使用remove和类似的算法(remove_if和unique)。
如果容器中存放的不是普通指针，而是具有引用计数功能的智能指针，那么就可以直接使用erase-remove的习惯用法。

28 了解哪些算法要求使用排序的区间作为参数

29 通过mismatch或lexicographical_compare实现简单的忽略大小写的字符串比较

30 理解copy_if算法的正确实现

31 使用accumulate或者for_each进行区间统计

6 函数、函数子类及其他

32 遵循按值传递的原则来设计函数子类

33 确保判别式是”纯函数”

34 若一个类是函数子，则应使它可配接

35 理解ptr_fun、men_fun和mem_fun_ref的来由

36 确保less与operator<具有相同的语义

37 算法调用优先于手写的循环

38 容器的成员函数优先于同名的算法

39 正确区分count、find、binary_search、lower_bound、upper_bound和equal_range

40 考虑使用函数对象而不是函数作为STL算法的参数

7 在程序中使用STL

8 学习过程中的一些思考

8.1 vector可以实现stack的功能，为什么还需要stack

1. vector是容器，stack是容器适配器
   扩充：什么是容器适配器？
   容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。stack（类似还有queue、priority_queue）是个容器适配器
2. 使用stack可以限制一些措施，比如使用stack可以禁止使用下标访问等操作，在编译阶段就可以阻止

参考链接：https://blog.csdn.net/fengbingchun/article/details/103223914