3

假设我有一个向量 V，它有 10 个元素。v.erase(v.begin())如果我使用STL 向量删除第一个元素（在索引 0 处）如何处理这个？

它是否会创建另一个新向量并将元素从旧向量复制到新向量并释放旧向量？或者它是否从索引 1 开始复制每个元素并将元素复制到 index-1 ？

如果我一次需要一个大小为 100,000 的向量，然后我不使用那么多空间，假设我只需要一个大小为 10 的向量，那么它会自动减小大小吗？（我不这么认为）

我在网上看了，只有 API 和如何使用 STL 库的教程。有什么好的参考资料可以让我了解 STL 库的实现或复杂性吗？

4

5 回答 5

5

实际上， 的实现vector是可见的，因为它是一个模板，因此您可以查看详细信息：

iterator erase(const_iterator _Where)
    {   // erase element at where
    if (_Where._Mycont != this
        || _Where._Myptr < _Myfirst || _Mylast <= _Where._Myptr)
        _DEBUG_ERROR("vector erase iterator outside range");
    _STDEXT unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);
    _Destroy(_Mylast - 1, _Mylast);
    _Orphan_range(_Where._Myptr, _Mylast);
    --_Mylast;
    return (iterator(_Where._Myptr, this));
    }

基本上，这条线

unchecked_copy(_Where._Myptr + 1, _Mylast, _Where._Myptr);

完全按照您的想法进行 - 复制以下元素（或如 bames53 指出的那样在 C++11 中移动它们）。

要回答您的第二个问题，不，容量不能自行减少。

std可以在http://www.cplusplus.com/reference/stl/找到算法的复杂性，并且如前所述，实现是可见的。

于 2012-06-13T22:19:44.403 回答
1

它是否从索引 1 开始复制每个元素并将元素复制到 index-1 ？

是的（尽管它实际上从 C++11 开始移动它们）。

它会自动减小尺寸吗？

不，减小大小通常会使现有元素的迭代器无效，并且只允许在某些函数调用上。

我在网上看了，只有 API 和如何使用 STL 库的教程。有什么好的参考资料可以让我了解 STL 库的实现或复杂性吗？

您可以阅读 C++ 规范，该规范会告诉您在实现方面什么是允许的，什么是不允许的。你也可以去看看你的实际实现。

于 2012-06-13T22:22:03.767 回答
1

Vector 会将元素复制（在 C++11 中移动）到开头，这就是为什么如果您想从集合的开头插入和擦除，您应该使用 deque。如果您想真正调整向量的内部缓冲区大小，您可以这样做：

vector<Type>(v).swap(v);

这有望制作一个大小正确的临时向量，然后将其内部缓冲区与旧的交换，然后临时向量超出范围，大缓冲区被释放。

正如其他人指出的那样，您可以vector::shrink_to_fit()在 C++11 中使用。

于 2012-06-13T22:28:07.053 回答
0

这是我（许多）对 C++ 的反对意见之一。每个人都说“使用标准库”......但即使你有 STL 源代码（可以从许多不同的地方免费获得。在这种情况下，包括头文件本身！）......它基本上是一个难以理解的噩梦深入研究并尝试理解。

相比之下，（仅 C 语言的）Linux 内核是简洁明了的典范。

但我们离题了:)

这是您问题的 10,000 英尺答案：

http://www.cplusplus.com/reference/stl/vector/

向量容器被实现为动态数组；与常规数组一样，向量容器的元素存储在连续的存储位置，这意味着不仅可以使用迭代器访问它们的元素，还可以使用指向元素的常规指针的偏移量来访问它们的元素。

但与常规数组不同，向量中的存储是自动处理的，可以根据需要进行扩展和收缩。

向量擅长：

  • 通过位置索引（恒定时间）访问单个元素。
  • 以任何顺序（线性时间）迭代元素。
  • 从其末尾添加和删除元素（恒定摊销时间）。

与数组相比，它们为这些任务提供几乎相同的性能，而且它们能够轻松调整大小。虽然，当它们的容量被自动处理时，它们通常比数组消耗更多的内存（这是为了为未来的增长提供额外的存储空间）。

与其他基本标准序列容器（双端队列和列表）相比，向量通常在访问元素以及从序列末尾添加或删除元素方面是最有效的。对于涉及在结尾以外的位置插入或删除元素的操作，它们的性能比双端队列和列表差，并且迭代器和引用的一致性不如列表。

...

就性能而言，重新分配可能是一项代价高昂的操作，因为它们通常涉及要复制到新位置的向量使用的整个存储空间。您可以使用成员函数 vector::reserve 来预先指示向量的容量。这有助于优化存储空间并在计划进行许多扩展时减少重新分配的次数。

...

于 2012-06-13T22:21:51.170 回答
-1

我只需要一个大小为 10 的向量，然后它会自动减小大小吗？

不，它不会自动缩小。
传统上你用一个新的空向量交换向量：减少一个 stl 向量的容量

但是 C++x11 包含一个 std::vector::shrink_to_fit() 它直接执行它

于 2012-06-13T22:23:46.103 回答