容器
条款1：仔细选择你的容器
C++提供了很多可供程序员使用的容器：
（1） 标准STL序列容器：vector，string，deque和list
（2） 标准STL关联容器：set，multiset，map和multimap
（5） vector<char>可以作为string的替代品
（6） vector作为标准关联容器的替代品
（7） 几种标准非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue
又新增了一些容器，包括：array，unordered容器，还有tuple容器。
不同容器有不同的优缺点，用户需要根据实际应用的特点综合决定使用哪种容器，如：vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。
条款2：小心对“容器无关代码”的幻想
本条款要告诫程序员：编写与容器无关的代码是没有必要的。
有人想编写这样的程序，刚开始时使用vector存储，之后由于需求的变化，将vector改为deque或者list，其他代码不变。实际上，这基本上是做不到的。这是因为：不同的序列容器所对应了不同的迭代器、指针和引用的失效规则，此外，不同的容器支持的操作也不相同，如：vector支持reserve()和capacity()，而deque和list不支持；即使是相同的操作，复杂度也不一样（如：insert），这会让你的系统产生意想不到的瓶颈。
此外，鼓励程序员在声明容器和迭代器的时候使用typedef进行重命名，这能够对你的程序进行封转，从而使用起来更简单，如有下面一个map容器：
map<string,vectorWidget>::iterator,CIStringCompare>;
如要用const_iterator遍历这个map，你需不止一次地写下：
map<string, vectorWidget>::iterator, CIStringCompare>::const_iterator
如果使用typedef，会快速方便很多。
条款3：使容器里对象的拷贝操作轻量而正确
容器容纳了对象，但不是你给它们的那个对象。当你向容器中插入一个对象时，你插入的是该对象的拷贝而不是它本身；当你从容器中获取一个对象时，你获取的是容器中对象的拷贝。
拷贝是STL的基本工作方式。当你删除或者插入某个对象时，现有容器中的元素会移动（拷s贝）；当你使用了排序算法，remove、uniquer或者他们的同类，rotate或者reverse，对象会移动（拷贝）。
一个使拷贝更高效、正确的方式是建立指针的容器而不是对象的容器，即保存对象的指针而不是对象，然而，指针的容器有它们自己STL相关的头疼问题，改进的方法是采用智能指针。
条款4：用empty来代替检查size()是否为0
对于任意容器c，写下
if (c.size() == 0)
本质上等价于写下
if (c.empty())
但是为什么第一种方式比第二种优呢？理由很简单：对于所有的标准容器，empty是一个常数时间的操作，但对于一些list实现，size花费线性时间。
这什么造成list这么麻烦？为什么不能也提供一个常数时间的size？如果size是一个常数时间操作，当进行增加/删除操作时每个list成员函数必须更新list的大小，也包括了splice，这会造成splice的效率降低（现在的splice是常量级的），反之，如果splice不必修改list大小，那么它就是常量级地，而size则变为线性复杂度，因此，设计者需要权衡这两个操作的算法：一个或者另一个可以是常数时间操作。
条款5：尽量使用区间成员函数代替单元素操作
给定两个vector，v1和v2，怎样使v1的内容和v2的后半部分一样？
可行的解决方案有：
（1）使用区间函数assign：
v1.assign(v2.begin() + v2.size() / 2, v2.end());
（2）使用单元素操作：
vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
ci != v2.end();
++ci)
v1.push_back(*ci);
（3）使用copy区间函数
v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));
（4）使用insert区间函数
v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());
最优的方案是assign方案，理由如下：
首先，使用区间函数的好处是：
● 一般来说使用区间成员函数可以输入更少的代码。
● 区间成员函数会导致代码更清晰更直接了当。
使用copy区间函数存在的问题是：
【1】 需要编写更多的代码，比如：v1.clear()，这个与insert区间函数类似
【2】 copy没有表现出循环，但是在copy中的确存在一个循环，这会降低性能
使用insert单元素版本的代码对你征收了三种不同的性能税，分别为：
【1】 没有必要的函数调用；
【2】 无效率地把v中的现有元素移动到它们最终插入后的位置的开销；
【3】 重复使用单元素插入而不是一个区间插入必须处理内存分配。
下面进行总结：
说明：参数类型iterator表示容器的迭代器类型，也就是container::iterator，参数类型InputIterator表示可以接受任何输入迭代器。
【1】 区间构造
所有标准容器都提供这种形式的构造函数：
container::container(InputIterator begin,
// 区间的起点
InputIterator end);
// 区间的终点
【2】区间插入
所有标准序列容器都提供这种形式的insert：
void container::insert(iterator position,
// 区间插入的位置
InputIterator begin,
// 插入区间的起点
InputIterator end);
// 插入区间的终点
关联容器使用它们的比较函数来决定元素要放在哪里，所以它们了省略position参数。
void container::insert(lnputIterator begin, InputIterator end);
【3】区间删除
每个标准容器都提供了一个区间形式的erase，但是序列和关联容器的返回类型不同。序列容器提供了这个：
iterator container::erase(iterator begin, iterator end);
而关联容器提供这个：
void
container::erase(iterator begin, iterator end);
为什么不同？解释是如果erase的关联容器版本返回一个迭代器（被删除的那个元素的下一个）会招致一个无法接受的性能下降.
注意这个特点在新版本的STL中已经解决了
【4】 区间赋值
所有标准列容器都提供了区间形式的assign：
void
container::assign(InputIterator begin, InputIterator end);
条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针
条款8：永不建立auto_ptr的容器**//注意，在新版本中auto_ptr已经不再被使用
条款9：在删除选项中仔细选择
（1）假定你有一个标准STL容器，c，容纳int，
Container<int> c;
而你想把c中所有值为1963的对象都去，则不同的容器类型采用的方法不同：没有一种是通用的.
- 如果采用连续内存容器(vector、queue和string)，最好的方法是erase-remove惯用法：
c.erase(remove(c.begin(), c.end(), 1963),c.end());
// 当c是vector、string
// 或deque时，erase-remove惯用法是去除特定值的元素的最佳方法
- 对于list，最有效的方法是直接使用remove函数：
c.remove(1963);
- 对于关联容器，解决问题的适当方法是调用erase：
c.erase(1963);
// 当c是标准关联容器时,erase成员函数是去除特定值的元素的最佳方法
（2）让我们换一下问题：不是从c中除去每个有特定值的元素，而是消除下面判断式返回真的每个对象：
bool badValue( int x);
// 返回x是否是“bad”
- 对于序列容器（vector、list、deque和string），只需要将remove换成remove_if即可：
// 当c是vector、string
// 或deque时这是去掉badValue返回真的对象的最佳方法
c.erase(remove_if(c.begin(), c.end(), badValue),c.end());
// 当c是list时这是去掉badValue返回真的对象的最佳方法
c.remove_if(badValue);
- 对于关联容器，有两种方法处理该问题，一个更容易编码，另一个更高效。“更容
易但效率较低”的解决方案用remove_copy_if把我们需要的值拷贝到一个新容器中，然后把原容器的内容和新的交换：
“更高效”的解决方案是直接从原容器删除元素。不过，因为关联容器没有提供类似remove_if的成员函数，所以我们必须写一个循环来迭代c中的元素，和原来一样删除元素：
AssocContainer<int> c;
...
for(AssocContainer<int>::iterator i = c.begin();i != c.end();){
if(badValue(*i))
c.erase(i++);
else
++i;
}
- 对于vector、string、list和deque，必须利用erase的返回值。那个返回值正是我们需要的：一旦删除完成，它就是指向紧接在被删元素之后的元素的有效迭代器。换句话说，我们这么写：
for(SeqContainer<int>::iterator i = c.begin(); i != c.end();){
if(badValue(*i)){
i = c.erase(i);
// 通过把erase的返回值赋给i来保持i有效
}
else
++i;
}
条款12：对STL容器线程安全性的期待现实一些
在工程中多线程操作STL的场景应该还是比较常见的，一个典型的例子就是用其来做生产者——消费者模型的队列或者其他共享队列，这样为了应对线程安全问题我们必须自己对容器操作进行封装。这是我自己实现的的封装类:
template< typename Container>
// 获取和释放容器的互斥量的类的模板核心；
class Lock {
public :
// 忽略了很多细节
Lock( const Containers container) : c(container){
// 在构造函数获取互斥量
getMutexFor(c);
}
~Lock(){
// 在析构函数里释放它
releaseMutexFor(c);
}
private:
const Container& c;
};
原创文章，转载请注明： 转载自董的博客
本文链接地址: http://dongxicheng.org/cpp/effective-stl-part1/
网友评论