vector和string

所有的STL容器都很有用，但是相比于其他容器，vector和string更常用。本章从多个角度覆盖vector和string，如：为什么提倡使用 vector代替数组，怎样改进vector和string的性能？怎样除去过剩的内存，vector<string>是个什么东西？

条款13：尽量使用vector和string来代替动态分配的数组

使用vector和string代替动态分配的数组是个很明智的选择，它们不仅能够自动管理内存（主要是自动释放内，自动增加内存），还提供了很多可用的函数和类型：既有像begin、end和size这样的成员函数，也有内嵌的像iterator、 reverse_iterator或value_type的typedef。
对于string实现，可能使用了引用计数器，这是一种那个消除了不必要的内存分配和字符拷贝的策略，而且在很多应用中可以提高性能。但这种方案在多线程环境下可能会严重降低性能，可能的解决方法是：
（1）关闭引用计数（如果可能的话）
（2）寻找或开发一个不使用引用计数的string实现（或部分实现）替代品
（3）考虑使用vector<char>来代替string，vector实现不允许使用引用计数，所以隐藏的多线程性能问题不会出现了

条款14：使用reserve避免不必要的重新分配

reserve成员函数允许你最小化必须进行的重新分配的次数，因而可以避免真分配的开销和迭代器/指针/引用失效。

• size()返回容器中已经保存的元素个数
• capacity()返回容器可以保存的最大元素个数。如果要知道一个vector或string中有多少没有被占用的内存，可以让capacity() 减去size()；如果size和capacity返回同样的值，容器中就没有剩余空间了，而下一次插入（通过insert或push_back等）会引 发重分配。
• resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后，size将会返回n。如果n小于当前大小，容器尾部的元素会被销毁。如果n大于当前大小，新默认 构造的元素会添加到容器尾部。如果n大于当前容量，在元素加入之前会发生重新分配。
• reserve(Container::size_type n)强制容器把它的容量改为至少n，提供的n不小于当前大小。这一般强迫进行一次重新分配，因为容量需要增加。（如果n小于当前容量，vector忽略 它，这个调用什么都不做，string可能把它的容量减少为size()和n中大的数，但string的大小没有改变。）

条款16: 如何将vector和string的数据传给遗留的API

我们可以将vector或者string传递给数组/指针类型的参数，如：

• 用C风格API返回的元素初始化一个vector，可以利用vector和数组潜在的内存分布兼容性将存储vecotr的元素的空间传给API函数：

// C API：此函数需要一个指向数组的指针，数组最多有arraySize个double
// 而且会对数组写入数据。它返回写入的double数，不会大于arraySize
size_t fillArray(double *pArray, size_t arraySize);
// 建立一个vector，它的大小是maxNumDoubles 
vector<double> vd(maxNumDoubles); 
// 让fillArray把数据写入vd，然后调整vd的大小 为fillArray写入的元素个数
vd.resize(fillArray(&vd[0], vd.size())); 

• 让C风格API把数据放入一个vector，然后拷到你实际想要的STL容器中的主意总是有效的：

size_t fillArray(double *pArray, size_t arraySize); // 同上
vector<double> vd(maxNumDoubles); // 一样同上
vd.resize(fillArray(&vd[0], vd.size()));
deque<double> d(vd.begin(), vd.end()); // 拷贝数据到deque
list<double> l(vd.begin(), vd.end()); // 拷贝数据到list
set<double> s(vd.begin(), vd.end()); // 拷贝数据到set

• 如何将vector和string以外的STL容器中的数据传给C风格API？只要将容器的每个数据拷到vector，然后将它们传给API：

void doSomething(const int* pints, size_t numInts); // C API (同上)
set<int> intSet; // 保存要传递给API数据的set
...
vector<int> v(intSet.begin(), intSet.end()); // 拷贝set数据到vector
if (!v.empty()) doSomething(&v[0], v.size()); // 传递数据到API

条款17：使用“交换技巧”来修整过剩容量

实际项目中可能遇到这样的情况：刚开始时，将大量数据插入到一个vector中，后来随着实际的需要，将大量元素从这个vector中删除，这样的 话，vector中会占用大量未使用的内存（通过函数capacity()可看到结果），如何将这些未使用的内存释放，可采用以下几种方法：

vector<Contestant>(contestants).swap(contestants);

表达式vector<Contestant>(contestants)建立一个临时vector，它是 contestants的一份拷贝：vector的拷贝构造函数做了这个工作。但是，vector的拷贝构造函数只分配拷贝的元素需要的内存，所以这个临 时vector没有多余的容量。然后我们让临时vector和contestants交换数据，这时contestants只有临时变量的修整过的容量， 而这个临时变量则持有了曾经在contestants中的发胀的容量。在这里（这个语句结尾），临时vector被销毁，因此释放了以前 contestants使用的内存
同样的技巧可以应用于string：

string s;
... // 使s变大，然后删除所有它的字符
string(s).swap(s); // 在s上进行“收缩到合适”

条款18：避免使用vector<bool>

作为一个STL容器，vector<bool>有两个问题。
它不是一个STL容器。它并未实际保存一个bool, 而是用位域的概念进行了封装。

标准库提供了两个替代品，它们能满足几乎所有需要。
第一个是deque<bool>。deque提供了几乎所有vector所提供的（唯一值得 注意的是reserve和capacity），而deque<bool>是一个STL容器，它保存真正的bool值。
当然，deque内部内存不是连续的。所以不能传递deque<bool>中的数据给一个希望得到bool数组的C API。
第二个vector<bool>的替代品是bitset。bitset不是一个STL容器，但它是C++标准库的一部分。与STL容器不同，它的大小（元素数量）在编译期固定，因此它不支持插入和删除元素。此外，因为它不是一个STL容器，它也不支持iterator。
标准非STL容器是指可以认为它们是容器，但是他们并不满足STL容器的所有要求。前文提到的容器适配器stack、queue及priority_queue都是标准非STL容器的一部分。此外，valarray也是标准非STL容器。
bitset：一种高效位集合操作容器。

关联容器

条款19：了解相等和等价的区别

set中的find函数采用的是等价准则，而find算法采用的是相等准则。

find算法在某个区间中查找一个元素时，需要比较两个对象，看一个对象的值是否等于零一个对象，它对相同的定义是相等，是以operator==为基础的。
set的insert需要确定插入的元素的值是否已经在set中了，它对相同的定义是等价，是以operator<为基础的。
两个对象相等并不意味着它们的所有数据成员都有相等的值。
等价关系是以“在已排序的区间中对象值的相对顺序”为基础的。对于两个对象x和y，如果按照关联容器的排列顺序，每个都不在另一个的前面，那么称这两个对象按照关联容器的排列顺序有等价的值。用表达式表示就是：!(x < y) && !(y < x) 为true，x和y对于operator<有等价的值。
一般情况下，一个关联容器的比较函数不是operator<，甚至也不是less，是用户定义的判别式，只要把<改为判别式的调用即可。
如果有一个不区分大小写的set<string>，我们向其中插入Persephone，如果再插入persephone，后面一个将不会被插入，因为两个是等价的。稍后我们使用成员函数find去查找persephone，查找会成功，但是如果用find算法去查找，那么查找将会失败。

条款20：为指针的关联容器指定比较类型

当关联容器中保存的是对象指针时，需要自己定义比较器（不是一个函数，而是一个仿函数模板），不然关联容器会按照指针大小进行排序，而不是指针指向的内容。

条款21: 永远让比较函数对“相等的值”返回false

在关联容器中，用户自定义比较类型时，当两个元素相等时，应该返回false。
举例：建立一个set，比较类型用less_equal，然后插入一个10：

set<int, less_equal<int> > s; // s以“<=”排序
s.insert(10); // 插入10
然后再插入一次10：
s.insert(10);

关联容器对“相同”的定义是等价，因此set测试10B是否等价于10A。当执行这个测试时，它自然是使用set的比较函数。在这一例子 里，是operator<=，因为我们指定set的比较函数为less_equal，而less_equal意思就是operator<=。 于是，set将计算这个表达式是否为真：

!(10A <= 10B) && !(10B <= 10A) // 测试10A和10B是否等价

显然，该表达式返回false，于是两个10都会插入这个set，结果是set以拥有了两个为10的值的拷贝而告终，也就是说它不再是一个set了。通过使用less_equal作为我们的比较类型，我们破坏了容器！

条款22：避免原地修改set和multiset的键

原地修改map和multimap的键值是不允许的，同时，应避免原地修改set和multiset的键（尽管这是允许的），因为这可能影响容器有序性的元素部分，破坏掉容器。

条款23：考虑用有序vector代替关联容器

在你的应用中，如果查找的频繁程度比插入和删除的高很多，那么推荐你用有序vector代替关联容器，这主要是从内存引用失效频率考虑的。
用vector模拟关联数组的代码如下：

typedef pair<string, int> Data; // 在这个例子里 "map"容纳的类型
class DataCompare { // 用于比较的类
 public:
     bool operator()(const Data& lhs, // 用于排序的比较函数
     const Data& rhs) const {
         return keyLess(lhs.first, rhs.first); // keyLess在下面
     }
 
   // 用于查找的比较函数
    bool operator()(const Data& Ihs, const Data::first_type& k) const{ 
         return keyLess(lhs.first, k);
    }

   bool operator()(const Data::first_type& k,  const Data& rhs) const{
         return keyLess(k, rhs.first);
   }
 
 private:
     bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const{
         return k1 < k2;
     }
};
 
vector<Data> vd; // 代替map<string, int>
... // 建立阶段：很多插入，几乎没有查找

// 结束建立阶段。（当模拟multimap时，你可能更喜欢用stable_sort 来代替）
sort(vd.begin(), vd.end(), DataCompare());  
string s; // 用于查找的值的对象
... // 开始查找阶段
if (binary_search(vd.begin(), vd.end(), s, DataCompare()))... // 通过binary_search查找
vector<Data>::iterator i = lower_bound(vd.begin(), vd.end(), s, 
DataCompare()); // 再次通过lower_bound查找，

对于这么使用它们的数据结构的应用来说，一个vector可能比一个关联容器能提供更高的
性能（时间和空间上都是）。但不是任意的vector都会，只有有序vector。因为只有有序
容器才能正确地使用查找算法——binary_search、lower_bound、equal_range等。但为什么一个（有序的）vector的二分法查找比一个二叉树的二分法查找提供了
更好的性能？其中的一个是大小问题，另外一个是引用局部性问题。

考虑第一个大小问题。假设我们需要一个容器来容纳Widget对象，而且，因为查找速度对
我们很重要，我们考虑一个Widget的关联容器和一个有序vector<Widget>。如果我们选择
一个关联容器，我们几乎确定了要使用平衡二叉树。这样的树是由树节点组成，每个都不
仅容纳了一个Widget，而且保存了一个该节点到左孩子的指针，一个到它右孩子的指针，
和（典型的）一个到它父节点的指针。这意味着在关联容器中用于存储一个 Widget的空间
开销至少会是三个指针。

与之相对的是，当在vector中存储Widget并没有开销：我们简单地存储一个Widget。当然
，vector本身有开销，在vector结尾也可能有空的（保留）空间（参见条款14），但是每
个vector开销是可以忽略的（通常是三个机器字，比如，三个指针或两个指针和一个int）
，而且如果必要的话，末尾空的空间可以通过“交换技巧”去掉（看见条款17）。即使这
个附加的空间没有去掉，也并不影响下面的分析，因为当查找时不会引用那段内存。

假设我们的数据结构足够大，它们可以分成多个内存页面，但是vector比关联容器需要的
页面要少。那是因为vector不需要每个Widget的开销，而关联容器给每个Widget上附加了
三个指针。要知道为什么这很重要，假设在你使用的系统上一个Widget的大小是12个字节
，指针是4个字节，一个内存页面是4096（4K）字节。忽略每个容器的开销，当用vector保
存时，你可以在一页面上放置341个Widget，但使用关联容器时你最多只能放170个。因此
关联容器和vector比起来，你将会使用大约两倍的内存。如果你使用的环境可以用虚拟内
存，就很可以容易地看出那会造成大量的页面错误，因此一个系统会因为大数据量而明显
慢下来。

实际上我在这里还是对关联容器很乐观的，因为我们假设在二叉树中的节点都群集在一个
相关的小内存页面集中。大部分STL实现使用自定义内存管理器（实现在容器的配置器上—
—参见条款10和11）来达到这样的群集，但是如果你的STL实现没有改进树节点中的引用局
部性，这些节点会分散在所有你的内存空间。那会导致更多的页面错误。即使使用了自定
义群集内存管理器，关联容器也会导致很多页面错误，因为，不像连续内存容器，比如ve
ctor，基于节点的容器更难保证在容器的遍历顺序中一个挨着一个的元素在物理内存上也
是一个挨着一个。但当进行二分查找时那种内存组织方式（译注：遍历顺序中一个挨着一
个的元素在物理内存上也是一个挨着一个）正好是页面错误最少的。

概要：在有序vector中存储数据很有可能比在标准关联容器中保存相同的数据消耗更少的
内存；当页面错误值得重视的时候，在有序vector中通过二分法查找可能比在一个标准关
联容器中查找更快。

当然，有序vector的大缺点是它必须保持有序！当一个新元素插入时，大于这个新元素的
所有东西都必须向上移一位。它和听起来一样昂贵，如果vector必须重新分配它的内在内
存（参见条款14），则会更昂贵，因为vector中所有的元素都必须拷贝。同样的，如果一
个元素从vector中被删除，所有大于它的元素都要向下移动。vector的插入和删除都很昂
贵，但是关联容器的插入和删除则很轻量。这就是为什么只有当你知道你的数据结构使用
的时候查找几乎不和插入和删除混合时，使用有序 vector代替关联容器才有意义

条款24：当关乎效率时应该在map::operator[]和map-insert之间仔细选择

STL map的operator[]被设计为简化“添加或更新”功能，但事实上，当“增加”被执行时，insert比operator[]更高效。当进行更新时，情形正好相反，也就是，当一个等价的键已经在map里时，operator[]更高效。
理由如下：当进行“增加”操作时，operator[]会有三个函数调用：构造临时对象，撤销临时对象和对对象复制，而insert不会有；而对于更新操作，insert需要构造和析构对象，而operator[] 采用的对象引用，不会有这样的效率损耗。一个较为高效的“添加或更新”功能实现如下：

 // map的类型
// KeyArgType和ValueArgtype是类型参数
template<typename MapType, typename KeyArgType,  typename ValueArgtype>
typename MapType::iterator
efficientAddOrUpdate(MapType& m, const KeyArgType& k, const ValueArgtype& v)
{
  // 找到k在或应该在哪里；
  typename MapType::iterator Ib =  m.lower_bound(k); 
  // 如果Ib指向一个pair而且它的键等价于k...
  if(Ib != m.end() && !(m.key_comp()(k, Ib->first))) { 
       Ib->second = v; // 更新这个pair的值
       return Ib; // 并返回指向pair的迭代器
 } else{
      typedef typename MapType::value_type MVT;
      // 把pair(k, v)添加到m并返回指向新map元素的迭代器
       return m.insert(Ib, MVT(k, v)); 
 }
}

原创文章，转载请注明： 转载自董的博客
本文链接地址: http://dongxicheng.org/cpp/effective-stl-part1/