几个关于vector的问题

2021年01月14日 阅读数:5
这篇文章主要向大家介绍几个关于vector的问题,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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

1. 一个简单的例子

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

void simple(std::vector<int> 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<int> v;
v.reserve(2);
v[0] = 1;
std::cout << v[0];

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

  • sizecapacity

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

  • 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<int>::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<int>(std::cout, "\n"));
  • C++2.0的福音

C++11以后范围for语句的引入,使得循环写起来驾轻就熟,也不容易出错

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

C++14之后,因为对lambda表达式的加强,使得其与标准库算法相结合每每能够写出更加简短的代码,每每表现力更强,这里简单举个例子,

int main() {
  std::vector<std::string> 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
// <One> <small> <step> <One> <big> <leap>

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

End

独乐乐不如众乐乐,你们学习到的好东西也能够分享出来。

上一篇: 浅析内存分配
下一篇: FP范式之旅