STL-vector和string使用reserve来避免不必要的重新分配

my godness!
使用reserve来避免不必要的重新分配
关于STL容器,最了不起的一点是,它们会自动增长以便容纳下你放入其中的数据,只要没有超出它们的最大限制就可以。对于vector和string,增长过程是这样来实现的:每当需要更多空间时,就调用realloc类似的操作。这一类似的操作分为以下4部分:

  1. 分配一块大小为当前容量的某个倍数的新内存。在大多数视线中,vector和string的容量每次以2的倍数增长;
  2. 把容器的所有元素从旧的内存复制到新的内存中;
  3. 析构掉旧内存中的对象;
  4. 释放旧内存。

每当这些步骤发生时,vector和string指针、迭代器、和引用都变得无效,所以有必要避免这些步骤。
reserve成员函数能使你把重新分配的次数减小到最低限度,从而避免了重新分配和指针、迭代器、引用失效带来的开销。但是,在解释reverse是怎么做到这一点之前,先简单概括一下4个相互关联,但有时又被混淆的成员函数。在标准容器中只有vector和string提供了所有这4个函数。

  1. size()告诉该容器有多少元素。它不会告诉你该容器为自己所包含的元素分配了多少内存;
  2. capacity()告诉你该容器利用已经分配的内存可以容纳多少个元素。这是容器所能容纳的元素总数,而非它还能容纳多少个元素;
  3. resize(Container::size_type n)强迫容器改变到n个元素的状态。在调用resize()后size将返回n,如果n比size要小,则容器尾部的元素将会被析构;如果n比size要大,则通过默认构造函数创建的新元素将被添加到容器的末尾。如果n比当前的容量要大,那么在添加元素之前,将先重新分配内存;
  4. reverse(Container::size_type n)强迫容器把它的容量变为至少是n,前提是n不小于当前的大小。如果n比当前容量小,则vector忽略该调用,什么也不做;而string则可能把自己的容量减小为size和n的最大值。
    所以每次使用容器时,尽量尽早地使用reverse,把容器容量设为最大值。
    如:
    1
    2
    3
    vector<int> v;
    v.reverse(1000);
    for(int i = 0; i <= 1000; ++i) v.push_back(i);

如果有容量剩余,程序结束后再去释放内存。

容器是否为空检查策略

my godness!
当代码中需要检查某个容器是否为空时,调用empty,而不是检查size()是否为0.
对于任一容器c,下面的代码

1
if(c.size() == 0)

本质上与

1
if(c.empty())

是等价的。既然如此,为何还要纠结使用那种形式呢?empty通常被实现为内联函数,并且它所做的仅仅是返回size是否为0.
其实理由很简单:empty对所有的标准容器都是常数时间的操作,而对一些list实现,size耗费线性时间。
那么问题又来了,到底什么使list如此讨厌呢?为什么它不提供常数时间的size呢?答案在于list所独有的splice函数。考虑如下代码:

1
2
3
4
5
6
7
8
9
list<int> list1;
list<int> list2;

list1.splice(
list1.end(),
list2,
find(list2.begin(), list2.end(), 5), // 寻找第一个含5的节点
find(list2.rbegin(), list2.rend(), 10).base() // 需找最后一个含10的节点
)

代码中find(list2.begin(), list2.end(), 5), find(list2.rbegin(), list2.rend(), 10).base()所定义的范围不确定,也就是说不知道这个区间中元素的个数。所以size()操作是线性时间而不是常数时间。

而作为常用的容器list为何不维护一个size,使得求其长度时是常数时间呢?试想如果list的size()是常数时间,那么类似splice这种连接操作也会因为维护长度而使其效率降低一个数量级。权衡考虑,作为list更为重要的是快速的连接操作。

empty作为检查是否为空是常数的时间,所以这种情况下使用empty更高效。其他容器使用empty同样也不会使效率降低,因此不管发生什么调用empty而不是检查size()==0是否成立总是没错的。

STL-容器

STL

容器

STL中有迭代器(iterator)、算法(algorithm)、和函数对象(function object),但是对于大多数C++程序员来说,最值得注意的还是容器。容器相对于数组功能更强大、更灵活。它可以动态增长(缩减),可以自己管理内存,可以记住自己包含多少对象。为很多更复杂的问题设计出了更优雅的解决方案。

容器分类

  1. 标准STL序列容器:vector、string、deque和list。
  2. 标准STL关联容器:set、nultiset、map和multimap。
  3. 非标准序列容器:slist和rope。
  4. 非标准关联容器:hash_set、hash_multiset、hash_map和hash_multimap。
  5. vector作为string的替代。
  6. vector作为关联容器的替代。

如何选择合适的容器

vector、list和deque为程序员提供了不同的复杂性,使用时要对此做出权衡。vector是默认应使用的序列类型;当需要频繁的在序列中间做插入和删除时,应使用list;当大多数的插入和删除操作发生在序列的头部和尾部时,deque是应考虑的数据结构。
如果从算法复杂性上考虑,以上是对的,但是需要考虑的因素还很多。
连续内存容器把他的元素存放在一块或多块内存中,每块内存有多个元素。当有新元素插入或者已有元素删除时,同一内存块中的其他元素要向前或向后移动,以便为新元素让出空间,或者补全被删除元素所留下的空隙。这种移动会影响到效率和异常安全性。标准连续内存容器有vector、string和deque。非标准的rope也是一个连续内存容器。
基于节点的容器在每一个内存块中只存放一个元素。容器中元素的插入和删除只影响到指向结点的指针,而部影响节点本身的内容,所以当有插入或删除操作时,元素不用移动。表示链表的容器有list和slist。

总结

对于容器,STL给了多种选择。在选择一个容器之前要,充分考虑问题情境与各个容器的特点,选择适合的容器,切忌削足适履。生活中也是,适合自己的才是最好的,不要看着别人做什么,你就要做什么,那是不成熟的表现。