STL容器之vector

3040阅读　0评论2013-08-13　梦醒潇湘love
分类：C/C++


一、vector
    vector模塑出一个动态数组。因此，它本身是“将元素置于动态数组中加以管理”的一个抽象概念。不过，请注意，C++ Standard并未要求必须以动态数组实作vector，只是规定了相应条件和操作复杂度。
    使用vector之前，必须包含头文件。
    其中，型别vector是一个定义于namespace std内的template：
  1. namespace std
  2. {
  3.      template <class T, class Allocator = allocator<T> > class vector;
  4. };
    vector的元素可以是任意型别T，但是必须具备assignable和copyable两个性质。第二个template参数可有可无，用来定义内存模型。缺省的内存模型是C++标准程序库提供的allocator。

1.1 vector的能力
    vector将其元素复制到内部的dynamic array中。元素之间总是存在某种顺序，所以vector是一种有序群集。vector支持随机存取，因此只要知道位置，你可以在常数时间内存取任何一个元素。vector的迭代器是随机存取迭代器，所以对任何一个STL算法都可以奏效。
    在末端添加或删除元素时，vector的性能相当好。可是如果你在前端或中部安插或删除元素时，性能就不怎么样了，因为操作点之后的每个元素都必须移动到另一个位置，而每一次移动都得调用assignment（赋值）操作符。
    
1.2 大小（size）和容量（capacity）
    vector优异性能的秘诀之一，就是配置比其所容纳的元素所需更多的内存。为了能够高效运用vectors，你应该了解大小和容量之间的关系。
    vector之中用于操作大小的函数由size()、empty()、max_size()。另一个与大小有关的函数是capacity()，它返回vector实际能够容纳的元素数量。如果超过这个数量，vector就有必要重新配置内部存储器。
    vector的容量之所以重要，有以下两个原因：
    （1）一旦内存重新配置，和vector元素相关的所有references、pointers、iterators都会失效；
    （2）内存重新配置很耗时间
    所以如果你的程序管理了和vector元素相关的references、pointers、iterators，或如果执行速度对你而言很重要，那么就必须考虑容量问题。
    你可以使用reserve()保留适当容量，避免一再重复配置内存。如此一来，只要保留的容量尚有，就不必担心references失效。
  1. std::vector<int> v; //create an empty vector
  2. v.reserve(80); //reserve memory for 80 elements
    另外一种避免重新配置内存的方法是：初始化期间就向构造函数传递附加参数，构造出足够的空间。如果你的参数是个数值，它将成为vector的起始大小。
  1. std::vector<T> v(5); //create a vector and initializes it with five values
    当然，要获得这种能力，此种元素类型必须提供一个default构造函数。请注意，如果类型很复杂，就算提供了default构造函数，初始化操作也很耗时。如果这么做只是为了保留足够的内存，那倒不如使用reserve()。
    vectors的容量，概念上和strings类似。不过有一个大不同点：vector不能使用reserve()来缩减容量，这一点和strings不同。如果调用reserve()所给的参数比当前vector的容量还小，不会引发任何反应。
    既然vector的容量不会缩减，便可确定，即使删除元素，其references、pointers、iterators也会继续有效，继续指向动作发生前的位置。然而安插操作却可能使其失效（因为安插操作可能导致vector重新配置空间）。
    这里有一个间接缩减vector容量的小窍门。注意，两个vector交换内容后，两者的容量也会交换，因此，下面的例子虽然保留了元素，却缩减的容量：
  1. template <class T>
  2. void shrinkcapacity(vector<T> &v)
  3. {
  4.       vector<T> tmp(v);
  5.       v.swap(tmp);
  6. }
    不过请注意，swap()之后原先所有的references、pointers、iterators都换了指涉对象；它们仍然指向原本位置。

1.3 vector的操作函数
    构造、拷贝和析构
    下表列出了vectors所有的构造函数和析构函数。你可以在构造时提供元素，也可以不。如果只指定大小，系统便会调用元素的默认构造函数一一制造新元素，记住：即使对基本类型如int，显示调用default构造函数进行初始化，也是一样可行。
        
    
    非变动性操作
    下表列出了vectors的所有非变动性操作。
    
    
    赋值操作
    
    上表列出了“将新元素赋值给vectors，并将旧的元素全部移除”的方法。一系列assign()函数和构造函数一一对应。所有的赋值操作都可能会调用元素类型的default构造函数、copy构造函数、assignment操作符和析构函数，视元素数量的变化而定。
    
    元素存储
    下表列出用来直接存取vector元素的全部操作函数。按照惯例，第一个元素的索引为0，最后元素的索引为size() - 1。对于non-const vector，这些函数都返回元素的reference，也就是说，你可以使用这些操作函数来更改元素的内容。
    
    对于调用者来说，最重要的事情莫过于搞清楚这些操作是否进行范围检查。只有at()会那么做。如果索引越界，at()会抛出一个out_of_range异常。其他函数都不作检查的。如果发生越界错误，会引发未定义行为。对着一个空vector调用operator[]、front()、back()都会引发未定义行为。---->这个我遇到过，怎么也找不出错误，好囧啊
    调用operator[]时，你必须确定索引有效；调用front()或back()时必须确定容器不空。

    vector迭代器相关函数
    vector提供了一些常规函数获取迭代器，vector迭代器是随机存储迭代器，因此从理论上来讲，你可以通过这个迭代器操作所有STL算法。
    
    vector迭代器持续有效，除非发生两种情况：（1）使用者在一个较小索引位置上安插或移除元素；（2）由于容量变量而引起内存重新分配。

    安插（insert）和移除（remove）元素
    依照STL惯例，必须保证传入的参数合法：（1）迭代器必须指向一个合法位置；（2）区间的起始位置不能再结束位置之后；（3）决不能从空容器中移除元素。
    
    关于性能，以下情况你可以预期安插操作和移除操作会比较快写：
    （1）在容器尾部安插或移除元素；
    （2）容量一开始就够大；
    （3）安插多个元素时，“调用一次”当然比“调用多次”来得快；
    安插元素和移除元素，都会使“作用点”之后的各元素的references、pointers、iterators失效。如果安插操作甚至引起内存重新分配，那么该容器上的所有references、pointers、iterators都会失效。
    vector并未提供任何函数可以直接移除“与某值相等”的所有元素。这是算法发挥威力的时候，比如remove函数。

1.3 将vector当作一般arrays使用
    简单的说，任何地点只要你需要一个动态数组，你就可以使用vector。例如，你可以利用vector来存放常规的C字符串（类型为char *或const  char *）：
  1. vector<char> v;

  3. v.resize(41):
  4. strcpy(&v[0], "hello world");
  5. printf("%s\n", &v[0]);
    不过，这么运用vector必须小心，例如你必须保证上述vector的大小足以容纳所有的数据，如果你使用C-string，记住最后有个'\0'元素。
    注意：千万不要把迭代器当做第一个元素的地址来传递。vector迭代器是由实作版本定义，也许并不是个一般指针。
  1. printf("%s\n", v.begin()); //Error:might work ,but not portable
  2. printf("%s\n", &v[0]); //OK
    
1.4 异常处理
    vector只支持最低限度的逻辑错误检查。subscript（下标）操作符的安全版本at()，是唯一被标准规格书要求可能抛出异常的一个函数。此外，标准规格书也规定，只有一般标准异常（例如内存不足时抛出bad_alloc），或用户自定义操作函数的异常，才可能发生。
    ..........

2. class vector
    C++标准程序库专门针对元素类别为bool的vector设计了一个特殊的版本，目的是获取一个优化的vector。其耗用空间远远小于一般vector实作处理的bool型vector。一般的vector的实作版本会为每个元素至少分配一个byte空间，而vector特殊版本内部只用一个bit来存储一个元素。所以通常小8倍之多。不过这里有个小麻烦：C++的最小可寻址通常以byte为单位。所以上述vector特殊版本需针对references和pointers作特殊考虑。
    ..........
    这里具体不作讲述。
    
3. vector实例运用
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>

  6. using namespace std;

  8. int main()
  9. {
  10.     //create empty vector for strings
  11.     vector<string> sentence;

  13.     //reserve memory for five elements to avoid reallocation
  14.     sentence.reserve(5);

  16.     //append some elements
  17.     sentence.push_back("Hello");
  18.     sentence.push_back("how");
  19.     sentence.push_back("are");
  20.     sentence.push_back("you");
  21.     sentence.push_back("?");


  24.     //print elements separated with spaces
  25.     copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
  26.     cout << endl;

  28.     //print "technical data"
  29.     cout << "max_size(): " << sentence.max_size() << endl;
  30.     cout << "size(): " << sentence.size() << endl;
  31.     cout << "capacity(): " << sentence.capacity() << endl;

  33.     //swap second and fourth elemet
  34.     swap(sentence[1], sentence[3]);

  36.     //insert element "always" before element "?"
  37.     sentence.insert(find(sentence.begin(), sentence.end(), "?"), "always");

  39.     //assign "!" to the last element
  40.     sentence.back() = "!";

  42.     //print elements separated with spaces
  43.     copy(sentence.begin(), sentence.end(), ostream_iterator<string>(cout, " "));
  44.     cout << endl;

  46.         //print "technical data"
  47.     cout << "max_size(): " << sentence.max_size() << endl;
  48.     cout << "size(): " << sentence.size() << endl;
  49.     cout << "capacity(): " << sentence.capacity() << endl;

  51.     return 0;
  52. }
    一种可能的运行结果（VC6.0 32位Windows 7）如下：
上一篇：第三章——目标文件里有什么
下一篇：斐波那契数列