几个关于vector的问题

说到vector,想必读者都十分熟悉了,几乎所有C++程序员都会使用它,不过许多人并不清楚真正的语义,无意间会犯一些很奇怪的错误,今天看几个关于vector的问题,当然不可能把vector所有的东西都拿出来讲,否则就变成讨论vector的实现了。

1. 一个简单的例子

下面代码中,AB两行代码有何区别?

void simple(std::vector v) {
  v[0];       // A
  v.at(0);    // B 
}

破冰
上面AB两行代码都是在访问v的第一个元素,区别如下

  • v非空,则没有区别;
  • v为空,B会抛出一个std::out_of_range,至于A的行为,标准未作出声明。

再探
结合这两个函数在标准库里的声明看看,我稍稍的改写下,方便阅读,不影响理解

reference at(size_type __n);
reference operator[](size_type __n) noexcept;

从声明我们可以看到两个函数都是返回容器中第 n(参数)个位置的元素的引用,它们还有两个返回const引用的版本。operator[]是不会抛出异常的。使用成员函数at去访问vector里面的元素,会先进行下标越界检查,当越界发生将抛出out_of_range的异常。但标准并未强制要求operator[]做下标检查,一个原因设计vector是为了代替数组的,对operator[]效率要求很高。当你需要显示检查下标,请使用at成员函数。

相关话题
C++2.0之后引入了std::array来代替内置数组,下表简单总结了它们之间的差异

容器 底层数据结构 时间复杂度 其他
array 数组 随机读改 O(1) 支持随机访问
vector 数组 随机读改、尾部插入、尾部删除 O(1);头部插入、头部删除 O(n) 支持随机访问

2. 考虑 reserve

考虑下面的例子,会有什么问题

std::vector v;
v.reserve(2);
v[0] = 1;
std::cout << v[0];

先看看上面第二行调用reserve保证v容量capacity大于等于2,事实上很可能大于2,因为vector的大小呈指数速度上升。
问题比较明显出在最后两行,但是可能不易发觉,甚至在有些编译器上 “勉强” 能够 “正常运行”。
问题出在混淆了sizecapacity的概念。我们先理清下面两个概念

  • sizecapacity

size用来指示容器当前的元素个数;capacity表示容器的容量,一般大于size,告诉你一般最少添加多少个元素才会导致容器重新分配内存。

  • resizereserve

resize是改变容器的大小,且在创建对象;
reserve表示容器预留空间,不会创建对象,只修改capacity大小,不修改size大小;

所以在调用第二行代码之后,v仍然是空的。但是标准并未强制要求operator[]做下标检查,所以很可能在你的编译器中会出现v[0] = 1;被认为是正确的情况,最后在标准输出上打出1,跟 "错误的" 预期相符合。
强调一下,上述的情形只是一种典型的可能情况,并不一定会出现在所有地方。

3. 再看reserve

如果我们在2的后面再加上下面这两句,会出现什么情况

v.reserve(100);
std::cout << v[0];
  • 一种可能的情况

接着之前的典型(错误的)情况,这个时候输出的值可能为0,不必诧异,刚刚赋值的1去哪了。

  • 解释

假定第一次reserve(2)并没有使内部缓冲区扩大到100或者更大,这里reserve(100)就会引入一次内部缓冲区的重新分配,这时v的元素会被复制到新分配的缓冲区中,而问题是此时v中根本没有元素,空空如是,因此不会复制任何元素,此外,新分配的缓冲区初值可能为0(严格来说不确定是0,这里我们只是假设),因此就出现了上面的情况。

  • 替代方案

将上面的v[0] = 1;替换成v.push_back(1);就不会有问题了,它总是会像容器的尾部追加元素。

4. 遍历vector

思考一下下面的代码片段

for (vector::iterator iter = v.begin(); iter < v.end(); iter++) {
  std::cout << *iter << std::endl;
}

上面的程序正常运行没有任何问题,有些小细节需要注意

  • 尽量使用!=

尽量使用!=而不是<来比较两个迭代器。因为<只对随机访问迭代器有效,而!=对任何迭代器都有效。方便将来需要时改变容器的类型,例如std::list迭代器不支持<

  • 尽量使用前置++
  • 尽量使用const_iterrator
  • 尽量使用\n代替endl

华丽分割线来了.......

  • 使用标准库算法

C++标准库提供了一百多种有用的算法,可以避免使用原始循环。例如copyfor_eachtransformaccumulate...,

我们使用标准库算法重写上面的代码

// 尽量使用标准库算法而不是原始for循环
std::copy(v.cbegin(), v.cend(), std::ostream_iterator(std::cout, "\n"));
  • C++2.0的福音

C++11之后范围for语句的引入,使得循环写起来得心应手,也不容易出错

for (auto i : v) {
  std::cout << i << "\n";
}
  • 相关话题

C++14以后,由于对lambda表达式的增强,使得其与标准库算法相结合往往可以写出更加简短的代码,往往表现力更强,这里简单举个例子,

int main() {
  std::vector words{"One", "small", "step", "One", "big", "leap"};

  std::transform(begin(words), end(words), begin(words), [](const auto& word) {
    return "<" + word + ">";
  });
  std::for_each(begin(words), end(words), [](const auto& word) {
    std::cout << word << " ";
  });
}
// output
//      

不熟悉lambda的读者可以参考我的另一篇文章第4节可调用对象,或者查阅其它资料。

End

独乐乐不如众乐乐,大家学习到的好东西也可以分享出来。