第一章.容器

---

• 条款1.慎重选择容器类型

标准STL序列容器：vector、string、deque和list
标准STL关联容器：set、map、multiset和multimap
非标准的关联容器：hash_set、hash_multiset、hash_map和hash_multimap
标准的非STL容器：数组、bitset、valarray、stack、queue和priority_queue

另一种分类：
连续内存容器(元素存放在一块或多块内存中，每块内存中存有多个元素)：vector、string和deque
基于节点的容器(每块内存存放一个元素)：list和所有标准的关联容器

---

• 条款2.不要试图编写独立于容器类型的代码

序列容器与关联容器数据结构不同 ，所提供的操作也不同。
序列容器支持push_front或push_back，但关联容器不支持。
关联容器提供对数时间复杂度的lower_bound、upper_bound和equal_range成员函数，但序列容器却没有。
写既要和序列容器又要和关联容器一起工作的代码并没有什么意义。很多成员函数(包括运算符重载)只存在于其中一类容器中。

---

• 条款3.确保容器中的对象拷贝正确且高效

当你向容器中添加一个对象（比如通过insert或push_back等），进入容器的是你指定的对象的拷贝，
如果你从vector、string或deque中插入或删除了什么或使用了任何排序算法，现有的容器元素会移动（拷贝）。
因此把一个派生类对象插入基类对象的容器会导致派生部分被删除，而且容器中如果放的对象拷贝过程很昂贵，元素的移动会成为性能瓶颈，
所以使拷贝更高效、正确而且对分割问题免疫的简单的方式是建立指针的容器而不是对象的容器。但是指针容器也有自己的问题，详见条款7和条款33。

---

• 条款4.调用empty()而不是检查size()是否为0

empty的典型实现是一个返回size()==0结果的内联函数。
对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费线性时间。
list中有一个变量用于记录元素个数。特殊的是，list::splice()用于拼接两个list，为了达到splice的高效率，在splice时可能不更新size，而在调用size时遍历list计算size，
这就会导致size()花费线性时间而不是常数时间。
但书中没有说empty()为什么一定是常数时间。
所以我看了下我所用的QT中list::empty()的实现方式，发现list是由循化链表实现的，empty()的实现是判断头节点的下个节点是否还是头结点，因此为常数时间。
所以我的理解是：由于STL的实现方式不同，empty()的效率比0 == size()更加稳定(如循环链表实现的List)。

---

• 条款5.区间成员函数优先于与之对应的单元素成员函数

本文以insert的单元素版本和区间版本说明，区间成员函数优点有三：

1. 省去了没有必要的函数调用，调用1次与调用n次，即使将单元素版本声明为内联，也有可能不会成为内联。
2. 每次insert单元素，要将插入位置后的所有元素进行移动，进行拷贝，区间insert则先算好一共要插入的总数，然后将插入位置后的元素只整体挪动一次
3. 看原因3前需要先看Part2.条款14中，了解序列容器插入元素时内存的重新分配机制。多次插入单元素可能导致内存多次重新分配，而区间插入则一次性分配足够的空间，然后进行插入。

常用区间成员函数整理：
区间构造：

container::container(InputIterator begin, InputIterator end); 

begin和end为旧容器中，被拷贝区间的起始

区间插入：

序列容器：void container::insert(iterator position,InputIterator begin, InputIterator end); 
关联容器：void container::insert(lnputIterator begin, InputIterator end);//关联容器使用自己的比较函数决定插入元素放在哪

begin和end为旧容器中，要插到新容器中的区间起始
position为新容器中，要插入位置的迭代器，新元素插入到该迭代器之前

区间删除：

C++11以上: iterator container::erase(iterator begin, iterator end);
C++11以下: 关联容器erase()返回值void

将容器中[begin, end)前闭后开区间内的元素删除

区间赋值：

void container::assign(InputIterator begin, InputIterator end);

begin和end为旧容器中，被拷贝区间的起始

---

• 条款6.当心C++编译器最烦人的分析机制

按照条款5中所说，尝试使用list的区间构造，以一个文件中的全部内容构造一个list对象data

ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

上面这段代码乍一看好像没有问题，从文件的begin开始，一直迭代到NULL，即文件末尾，以此区间内的元素构造对象data。
但是编译器会将第二句代码解析为一个函数声明。问题出在构造时使用了一个匿名迭代器。
目前最好的解决方式，是在数据声明中避免使用匿名迭代器对象。

ifstream dataFile("ints.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd;
list<int> data(dataBegin, dataEnd);

---

• 条款7.如果在容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉

可以通过遍历容器释放指针，这样做能行，但不是异常安全的。
如果在向容器中放入和释放指针时有异常抛出，同样会有资源泄露。
所以最安全的做法是用引用计数智能指针（如Boost::shared_ptr）容器代替指针容器。
ps.不要创建auto_ptr的容器，并指望其中的指针被自动删除，详见下一条款

---

• 条款8.切勿创建包含auto_ptr的容器对象

auto_ptr最大的古怪在于它的拷贝构造和赋值操作符，会将被拷贝的指针置为NULL。
STL算法中的sort()采用的快速排序算法，会用临时对象拷贝vector中的值作为基准值。
这将导致vector<auto_ptr>调用sort()时，其中的值被临时对象拷贝，vector中的值被置为NULL，临时对象在作用域结束时释放了该auto_ptr。
ps.C++标准委员会做了很多使vector<auto_ptr>不被编译通过，并最终在C++11中移除了auto_ptr.

---

• 条款9.慎重选择删除元素的方法

9.1.1. 对于连续内存的容器(vector、deuqe和string)，删除元素的最好办法是使用erase-remove

vec.erase( std::remove(vec.begin(), vec.end(), value), vec.end());

erase-remove讲解：先要说一下erase和remove，

std::remove (Itertor first, Itertor last, const T& val);
    是<algorithm>中的算法，通过传入的迭代器确定容器遍历区间，将区间中不等于val的元素依次拷贝到区间中的前端。
    完成遍历之后即确定了一段由first起始，没有val值的新区间，
    最后返回该新区间后一个位置的迭代器

iterator erase (iterator first, iterator last);
    将前开后闭区间[first, last)中的元素删除，返回last

erase-remove:
    先通过remove将容器遍历，将不等于value值的元素放在容器前端新区间
    再将新区间后一个位置的迭代器和容器的end()传入erase，将新区间以外的部分删除

9.1.2. 对于list，erase-remove同样适用，但list::remove()更有效(详见条款44)

list.remove(value);
从list中移除所有值等于value的元素

9.1.3. 对于关联容器(set、multiset、map、multimap)，删除元素正确且高效的方法是调用erase（高效的原因详见条款19），不要对关联容器使用std::remove（详见条款22）

set.erase(value);
从set中删除所有值为value的元素（multiset中也是删除所有）

ps.书中提到，序列容器erase会返回下一个位置的迭代器，而关联容器erase返回void，所以序列容器可以通过iter = vec.erase(iter)获得erase后有效的迭代器，而关联容器则要通过set.erase(iter++)后置++的方式获得。
不过我在QtCreator和VisualStudio2005两个编译器都试了下，关联容器erase的返回值已经是下一个元素的迭代器了，两种容器可以都通过iter = vec.erase(iter)有效迭代，但对于序列容器不要使用vec.erase(iter++),因为序列容器调用erase后，会使被删除元素之后所有的迭代器失效（虽然QtCreator对此有优化，但在visual studio中的确如此，还是不要这么使用的好）。

9.2. 要删除容器中满足特定判别式的所有对象，序列容器使用erase-remove_if，list使用list::remove_if，关联容器使用遍历+erase(没有erase_if)

bool badvalue(int); //特定判别式

vec.erase( std::remove_if( vec.begin(),  vec.end(),  badvalue));
    序列容器，遍历vec，删除使badvalue返回true的对象

list.remove_if(badvalue);
    list::remove_if是删除使badvalue返回true的对象的最好办法

for(auto iter = set.begin(); iter != set.end(); /*for第三个参数什么也不做*/)
{
    if(badvalue(*i))  set.erase(iter++);
    else  ++iter;
}

---

如有错误，欢迎指正