std::vector的元素是否保证是连续的？

Question

std::vector的元素是否保证是连续的？

c++vectorlanguage-lawyerstdvector

140

我的问题很简单：`std::vector`的元素是否保证是连续的？换句话说，我能否将指向`std::vector`第一个元素的指针用作C数组？

如果我记得没错的话，C++标准并没有做出这样的保证。然而，`std::vector`的要求几乎不可能在元素不连续的情况下满足。

有人能澄清一下吗？

示例：

std::vector<int> values;
// ... fill up values

if( !values.empty() )
{
    int *array = &values[0];
    for( int i = 0; i < values.size(); ++i )
    {
        int v = array[i];
        // do something with 'v'
    }
}

- Martin Cote

1

我知道如果你在那个“if”块内改变了“values”，你会遇到麻烦。不过，我不知道你问题的答案，所以我只是留下了一条评论。 :) - Greg D

1

@Greg：有什么问题吗？你能详细说明一下吗？ - Reunanen

1

我想他的意思是，推入新值可能会触发"realloc"，从而使数组变为无效状态。 - Martin Cote

改变 values 值的调用，特别是改变其大小（例如 push_back()），可能会触发对基础向量的重新分配，从而使复制到 array 中的指针无效。这背后的原理与使用 vector::iterator 而不是指向向量的指针相同。 :) - Greg D

好的。我看到过这样的说法，如果你改变了值，也就是给元素赋值。我认为这应该不会引起任何问题。 - Reunanen

1

是的，我在值周围加上了“”以尝试清楚地表明我正在谈论类本身，而不是其中包含的值。 :) 不幸的命名等等。我认为在这个问题相关的一般情况下，这并不是一个问题 - 为什么有人会抓取指向内存的指针，然后开始搞乱向量而不是使用指针呢？真是愚蠢。 - Greg D

7个回答

39

正如其他答案所指出的，向量的内容保证是连续的（除了bool类型的奇怪性质）。

我想补充的一点是，如果您在向量中进行插入或删除操作，这可能会导致向量重新分配内存，从而使您保存的所有指针和迭代器失效。

- Bill Lynch

2

元素仍将存储在连续的内存块中，只是位置不同。问题特别涉及连续性。 - Dima

3

现有的指针和迭代器将会失效。 - Bill Lynch

@user2891462：https://dev59.com/kWsz5IYBdhLWcg3wWmYy - Bill Lynch

@BillLynch 谢谢！这就是我最终选择的，但我无法理解 segfault 是什么意思。 - user2891462

1

@iaomw: 1. vector.push_back(3) 是插入操作，因此会使迭代器失效。2. 我不认为 swap(vector[3], vector[4]) 会使迭代器失效，因为没有分配新的内存，但我没有参考资料来支持这一点。3. swap(vector_1, vector_2) 很有趣。我可能不会相信此后的迭代器，但我不确定它们是否仍然有效。 - Bill Lynch

显示剩余5条评论

9

标准确实保证了一个vector在内存中是连续的，而且&a[0]可以传递给期望数组的C函数。

不过，这个规则有一个例外：vector<bool>。它每个bool只使用一个比特位，因此尽管它具有连续的内存，但不能用作bool*（这被广泛认为是错误的优化和错误）。

顺便问一下，为什么不使用迭代器呢？那正是它们的用处所在。

- Motti

1

顺便问一句，你为什么不使用迭代器？这就是它们的作用。也许他读了Alexanrescu关于这个主题的新论文：http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf - Nemanja Trifunovic

谢谢提供链接，我会把它加入我的阅读列表（我尽量不错过Alexandresu的文章）。 - Motti

哈哈哈，这几天每个人都在谈论那个演示文稿。看，讨论仍在继续：http://groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/9b74808d7d869060 - Johannes Schaub - litb

如果你仔细阅读Alexandrescu的文章，他并没有真正说“不要在C++中使用迭代器”，而是说“看看D语言”。他在那篇论文中描述的方法与任何已经吸收了函数式遗产（List、Scheme、Haskell）的现有语言和框架非常相似，我严重怀疑又一个基于C语法的语言是否是更好的列表处理起点。去年我曾试图让他把他的才华投入到改进像C#这样的已经成熟的语言中，但我恐怕没有成功！ :) - Daniel Earwicker

6

正如其他人已经说过的那样，vector 内部使用一组对象的连续数组。每当调用任何非 const 成员函数时，指向该数组的指针应被视为无效（如果我没记错的话）。

然而，有一个例外！！ vector<bool> 有一个专门的实现，旨在节省空间，使每个 bool 只使用一个位。底层数组不是 bool 的连续数组，而且在 vector<bool> 上的数组算术运算不像 vector<T> 那样工作。

（我想这对于 vector 的任何特化也可能是正确的，因为我们总是可以实现一个新的特化。但是，std::vector<bool> 是唯一一个简单指针算术无法正常工作的标准特化。）

- Wuggy

用户不允许专门化std::vector，所有其他向量都需要使用连续存储。因此，std::vector<bool>是（幸运的是）唯一奇怪的标准向量。(我坚信这种特殊化应该被弃用，并由具有相同功能的std::dynamic_bitset等替代。它不是一个坏数据结构，只是不是向量。) - Arne Vogel

3

我找到了这个帖子，因为我有一个使用连续内存向量的用例。

我正在学习如何在OpenGL中使用顶点缓冲对象。我创建了一个包含缓冲逻辑的包装器类，所以我只需要传递一个浮点数数组和一些配置值来创建缓冲区。我希望能够根据用户输入从函数生成缓冲区，因此长度在编译时未知。像下面这样做将是最简单的解决方案:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

现在我可以将向量的浮点数作为数组传递给OpenGL的缓冲相关函数。这样也消除了使用sizeof确定数组长度的需要。

这比分配一个巨大的数组来存储浮点数并希望我足够大，或者制作自己的具有连续存储的动态数组要好得多。

- NobodyImportant

2

这个函数对我来说没有任何意义。你是想传递一个引用或指针给 v 而不是 v 本身吗？因为仅传递 v 将导致在函数内部创建一个副本，该副本在函数结束后将被销毁。因此，你只是在向向量中添加一些内容，但在函数结束时却删除了向量。 - johnbakers

3

是的，std::vector 的元素是保证连续的。

- Benoît

2

cplusplus.com:

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

- Igor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dirkgently · Accepted Answer

这个特性在C++98标准中被忽略了，但后来作为TR的一部分添加了进来。即将发布的C++0x标准当然会将其作为一个要求。

来自n2798（C++0x草案）：

23.2.6 类模板 vector [vector]

1 vector是一个支持随机访问迭代器的序列容器。此外，它支持（平均意义下的）常数时间插入和删除操作在末尾；在中间插入和删除需要线性时间。存储管理是自动处理的，虽然可以给出提示以提高效率。vector的元素是连续存储的，这意味着如果v是一个T类型而不是bool类型的向量，则对于所有0 <= n < v.size()，都遵守 &v[n] == &v[0] + n 的恒等式。