effective STL 读书笔记——第一章：容器

条款1：仔细选择你的容器

常见容器：

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

序列容器的选择：

vector：当需要使用下标索引，不经常插入删除元素时，选择vector——连续内存块
list：当很频繁地对序列中部进行插入和删除时应该用list——基于节点的分散的内存块
deque：当大部分插入和删除发生在序列的头或尾时可以选择deque——连续内存块

其他：

不关心元素顺序、要求查找速度的时候，选择散列容器
如果要求在任意位置插入元素，则不可选择关联容器，可以选择vector、list等
数据内存必须兼容C，则只能使用vector
介意是否使用了引用计数——是，则不可以使用string、rope

条款2：小心对“容器无关代码”的幻想

标准连续容器都提供随机访问迭代器
标准的基于节点的容器（再参见条款1）都提供双向迭代器
序列容器支持push_front或push_back，但关联容器不支持
关联容器提供对数时间复杂度的lower_bound、upper_bound和equal_range成员函数，但序列容器却没有

要限制如果用一个容器类型替换了另一个容器可能需要修改的代码，就需要在类中隐藏那个容器，而且要通过类的接口限制容器特殊信息可见性的数量比如，如果你需要建立一个客户列表，请不要直接用list。取而代之的是，建立一个CustomerList类，把list隐藏在它的private区域。如果以后你发现list对于你是用的场景在性能/功能不满足你的要求，你只需要将CustomerList中的list换成vector或者map等即可，而不需要修改CustomerList调用处的代码。——设计之初，应该保证尽量少的暴露容器相关的信息，以保证后期修改后对其他代码无影响。

条款3：使容器里对象的拷贝操作轻量而正确

向STL里面容器中添加对象时，实际上是对原始对象的拷贝，此时会调用该类的拷贝构造函数——如果存在。如果拷贝构造操作比较昂贵，则会对程序性能造成影响——它会浪费大量的内存以及时钟周期。因此有必要使容器对象的拷贝操作轻量而正确。

由于STL总是拷贝对象，因此如果把一个子类添加到一个基类的容器中，则会造成子类信息丢失。

一个使拷贝更高效、正确而且对分割问题免疫的简单的方式是建立指针的容器而不是对象的容器。同样使用指针也会带来问题——由于存放的是指针，则其指向的对象一般都是堆上的，在将指针从容器中remove掉的时候，如果不显示的删除资源，会造成内存泄露——解决该问题的途径是使用智能指针。

条款4：用empty来代替检查size()是否为0

对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费线性时间。

条款5：尽量使用区间成员函数代替它们的单元素兄弟

如何快速的将一个vector v1的值变为v2的后半部分？最佳答案如下：

v1.assign(v2.begin() + v2.size() / 2, v2.end());

1.assign成员函数对于所有标准序列容器（vector，string，deque和list）都有效 
2.区间成员函数是一个像STL算法的成员函数，使用两个迭代器参数来指定元素的一个区间来进行某个操作。不用区间成员函数来解决这个问题，你就必须写一个显式循环

其他几种写法：

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));// copy函数内部存在循环

太多的STL程序员过度使用copy，几乎所有目标区间被插入迭代器指定的copy的使用都可以用调用的区间成员函数的来代替

区间构造。所有标准容器都提供这种形式的构造函数

container::container(InputIterator begin, // 区间的起点
InputIterator end); // 区间的终点

区间插入。所有标准序列容器都提供这种形式的insert：

void container::insert(iterator position, // 区间插入的位置
InputIterator begin, // 插入区间的起点
InputIterator end); // 插入区间的终点

区间删除。每个标准容器都提供了一个区间形式的erase，但是序列和关联容器的返回类型不同
序列容器提供这个：

iterator container::erase(iterator begin, iterator end);

关联容器提供这个——如果erase的关联容器版本返回一个迭代器会招致一个无法接受的性能下降：

void container::erase(iterator begin, iterator end);

区间赋值：所有标准列容器都提供了区间形式的assign

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

条款6：警惕C++最令人恼怒的解析

如果我们需要从一个文件中读取int数据到一个list中，以下为一个看似合理的方式：

list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

但实际不然，它可能会被编译器解释为一个函数，接收2个istream_iterator，返回list。一个比较好的解决办法是不要使用匿名变量，代码如下：

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

另一个解决办法，但是可能不具备可移植性：

list<int> data((istream_iterator<int>(dataFile)), // 注意在list构造函数
istream_iterator<int>()); // 的第一个实参左右的新括号

条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针

1.string，就像所有的标准STL容器，缺少虚析构函数
2.不显示的delete会造成内存泄露
3.迭代delete容器内指针时，使用for_each而不是for循环，因为for循环不是异常安全的，通过将仿函数传递给for_each可以解决这个问题。

template<typename T>
struct DeleteObject : // 条款40描述了为什么
public unary_function<const T*, void> { // 这里有这个继承
void operator()(const T* ptr) const
    {
delete ptr;
    }
};

for_each(containerObject.begin(), containerObject.end(), DeleteObject<T>);

上述方法可以解决for循环异常安全的问题，但同时带来了2个问题
1.调用时必须为DeleteObject指定要删除的容器所持有的指针的类型
2.如果要删除的类型是从一个没有虚析构函数的类继承而来的，但是填充DeleteObject时却使用的基类类型，则会造成资源不能正确的释放

解决方法如下：

将模板放到类内部，然后通过DeleteObject构造一个对象作为for_each的参数

struct DeleteObject { // 删除这里的
// 模板化和基类
template<typename T> // 模板化加在这里
void operator()(const T* ptr) const
    {
delete ptr;
    }
}
for_each(containerObject.begin(), containerObject.end(), DeleteObject());

最完美的解决方法，是通过使用C++11引进的shared_ptr来解决：

void doSomething()
{
typedef shared_ ptr<Widget> SPW; //SPW = "shared_ptr
// to Widget"
vector<SPW> vwp;
for (int i = 0; i < SOME_MAGIC_NUMBER; ++i)
vwp.push_back(SPW(new Widget)); // 从一个Widget建立SPW,
// 然后进行一次push_back
// ... // 使用vwp
} // 这里没有Widget泄漏，甚至在上面代码中抛出异常

条款8：永不建立auto_ptr的容器

auto_ptr是独享拥有权的智能指针，auto_ptr在赋值/拷贝操作时应该特别小心，因为此时会发生所有权转移，导致作为拷贝构造或者拷贝参数的auto_ptr对象被置空。
如果auto_ptr被放到容器内部——比如vector，则任何使用vector元素作为参数的调用都将使vector的元素被置为NULL。因为在诸如赋值、拷贝、构造等地方发生了拥有权转移。

最后：尽量不要使用auto_ptr

条款9：在删除选项中仔细选择

要删除容器中满足某一条件的元素，对于不同的容器操作方式会存在差异

1.删除特定的值
对于序列容器：

c.erase(remove(c.begin(), c.end(), 1963),c.end()); // 当c是vector、string或deque时，erase-remove惯用法是去除特定值的元素的最佳方法。这方法也适合于list，list的成员函数remove更高效
c.remove(1963); // 当c是list时，remove成员函数是去除特定值的元素的最佳方法

对于关联容器，其成员变量中没有remove函数，而且使用remove算法也会造成迭代器的失效，答案是使用erase成员函数：

c.erase(1963); // 当c是标准关联容器时，erase成员函数是去除特定值的元素的最佳方法

2.删除满足某一条件的值
比如，删除序列容器中所有满足以下函数的值：

bool badValue(int x); // 返回x是否是“bad

对于序列容器（vector、string、deque和list），我们要做的只是把每个remove替换为remove_if，然后就完成了：

c.erase(remove_if(c.begin(), c.end(), badValue), c.end()); // 当c是vector、string或deque时
c.remove_if(badValue); // 当c是list时

当容器是关联容器时，对于set、multiset条件判断函数依然可以使用badValue，对于map、multimap则使用以下函数：

bool badPair(pair<int,Typename> x);

以下为从关联容器中删除满足条件的方法（假设条件函数名为badfunc）：

// 1.通过remove_copy_if拷贝不要删除的元素，然后进行交换
// 从c拷贝不删除的值到goodValues
AssocContainer<int> goodValues;
remove_copy_if(c.begin(), c.end(), inserter(goodValuesgoodValues.end()), badfunc);
c.swap(goodValues); // 交换c和goodValues

// 2.通过遍历迭代器删除，必须要注意的是，要使用后++
AssocContainer<int> c;
...
for (AssocContainer<int>::iterator it = c.begin();it != c.end(); )
{
if (badValue(*it))// 对于坏的值，把当前的i传给erase，然后作为副作用增加i；对于好的值，只增加i
    {
        c.erase(it++); 
//展开后的代码与下列代码等价：
// AssocContainer<int>::iterator tmp = it + 1;
// c.erase(it);
// it = tmp;
    }
else
        ++it;  
}

如果在删除某一条件元素时，必须先取得其值，然后再删除，则关联容器只需要在第二种方法erase之前取it的值即可，对于序列容器，则需要进行同样的遍历，但是序列容器在删除某一迭代器后，其后面的迭代器会失效，此时只需要获取erase返回的迭代器即可：

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

说明：

关联容器的erase返回void（list可以使用同样方法）
序列容器的erase返回下一迭代器（list可以使用同样方法）

条款12：对STL容器线程安全性的期待现实一些

在STL容器里对多线程支持的黄金规则已经由SGI定义，其特性如下：

多个读取者是安全的。多线程可能同时读取一个容器的内容，这将正确地执行。当然，在读取时不能有任何写入者操作这个容器。
对不同容器的多个写入者是安全的。多线程可以同时写不同的容器。

秒客网