C++-多维向量如何存储？

Question

C++-多维向量如何存储？

4

我有两个关于向量的问题。

假设我有一个多维向量，如下所示：

vector< vector<int> > A;

那么A[0]、A[1]等都是向量。这些向量在A中是如何存储的？我的意思是，关于向量A[0]和A[1]的哪些信息存储在A中？单个向量(如A[2])的内存重新分配会导致A的重新分配吗？
第二个问题：我尝试查看向量在重新分配时地址如何改变。我使用了以下代码：

代码：

vector<int> A;
int* x ;
int* y ;

vector<int>* ad;
vector<int>* bd;

for(int i = 0 ; i < 10000; i++){

    A.push_back(i);
    if(i == 2){
        y = &A[0];
        ad = &A;
    }
    x = &A[0];
    bd = &A;    

}

我发现即使 A[0] 的地址改变，A 的地址也没有改变。这是可以预期的，因为向量在后台使用 new 和 delete。但我的问题是，在地址 &A 中存储了多少关于向量的信息（或哪些信息）（考虑到 &A 的地址没有改变）。这也是我对第一个问题的疑问。

我正在尝试通过默认方式更好地理解向量的工作原理。

- ameyask

1

很简单：一个 std::vector<X> 包含 X 对象，无论 X 的类型是什么（可能除了 std::vector<bool>）。 - juanchopanza

A 中存储的是 vector<int> 类型的元素，因为 A 的类型是 vector<vector<int>>（而不是某种类型 T 的 vector<T*>）。我怀疑它存储指针。那么你基于什么怀疑呢？ - Igor Tandetnik

STL并不等同于C++标准库。 - πάντα ῥεῖ

“&A” 存储的是多少信息，足以找到“A”所代表的内存位置就可以了，这对任何对象的地址都是适用的。 - Igor Tandetnik

我根据你的评论@Igor对原问题进行了一些更改。 - ameyask

3个回答

2

关于向量的地址：A的地址不会改变，不是因为A是一个向量，而是因为在定义它的变量（或者更准确地说，在执行特定的函数调用时），没有任何变量的地址会改变。我认为您可能将A的地址（例如您的示例中的ad、bd）与A用于存储向量元素的地址（在您的示例中本质上是x和y）混淆了。向量分配、释放或重新分配存储空间。

请注意，A[0]不是您定义的变量，它是对A.operator[]的调用的结果；因此，它的位置可以改变。

关于实际存储在&A中的内容：这有点复杂。您需要查看C++安装中的头文件vector，或者最好查看std::vector的网页，位于cppreference.com上。请注意，有很多模板、一些子类和一些显式模板特化，所以就像我说的那样 - 复杂。您可能想重新考虑一下，是否真的想要深入了解这个容器的工作方式作为一般规则，或者现在类的公共方法和sizeof()数字是否已经足够。

- einpoklum

是的，但A [0]的地址已更改。也就是说，A [0]所在的位置已更改，我想这是由于重新分配造成的。 - ameyask

我想知道它是否将实际元素存储在&A中，但我现在不认为它会这样做。我的主要关注点是，如果在多维向量A（问题1）中插入元素到向量A [2]中，A中会有任何内存重新分配吗？（A [2]中可能会有内存重新分配。但是A中的向量数量没有改变，因此我确认是否会在A中重新分配。） - ameyask

@Blastfurnace，我的疑虑是因为，在我的应用程序中，我有n个1维向量，每个向量的大小可能在运行时动态改变。但是n的数量是固定的。因此，我考虑使用2维向量来解决它（之前由于担心子向量重新分配导致父向量重新分配而困惑是否应该存储对n个1维向量的指针）。 - ameyask

@ameyask86：我不会使用原始指针。只要外部向量不增长（固定为n），那么内部向量就不会移动。每一行可能会重新分配它拥有的内存，但向量对象本身不会移动。 - Blastfurnace

@Blastfurnace：是的，当然。我让C编程在我的脑海中占据了一秒钟（即a[b] <=> *(a + b)，这在C++中不成立）。 - einpoklum

"你可能需要重新考虑是否真的想要看看引擎盖下面发生了什么。我不同意这一点。了解引擎盖下面发生的事情总是值得的，可以帮助我们理解、提高自己的技能，并且知道当抽象变得有缺陷时会发生什么（http://www.joelonsoftware.com/articles/LeakyAbstractions.html）。" - cmaster - reinstate monica

0

我是一个c++和STL的初学者，所以我只是用一些简单的代码来测试你的问题；首先，我有这些代码：

std::vector<int> tmp;
std::cout << sizeof(tmp) << " " << tmp.size() << " " << tmp.capacity << std::endl;

输出结果为：

12 0 0

然后，我们将一些值插入到向量中

for(int i = 0; i != 10; ++i) tmp.push_back(i);
std::cout << sizeof(tmp) << " " << tmp.size() << " " << tmp.capacity << std::endl;

输出结果为

12 10 16

那么，我们可以得出结论，向量只是保留了一个指针，因此sizeof()的结果没有改变。所以，你的问题的答案是，子向量的push_back不会导致父向量的重新分配（我不知道这两个向量的作用如何表达）。以下是一些简单的代码：

std::vector<int> v1(10);
std::vector<int> v2(10);

int i;
for(i = 0; i != 10; ++i)
    v1[i] = i;
for(i = 0; i != 10; ++i)
    v2[i] = i;

vv.push_back(v1);
vv.push_back(v2);

std::cout << "v1 capacity: " << v1.capacity() << "  v1 size: " << v1.size() << std::endl;
std::cout << "v2 capacity: " << v2.capacity() << "  v2 size: " << v2.size() << std::endl;
std::cout << "vv capacity: " << vv.capacity() << "  vv size: " << vv.size() << std::endl;

for(i = 10; i != 20; ++i)
    v1.push_back(i);
for(i = 10; i != 20; ++i)
    v2.push_back(i);

std::cout << "v1 capacity: " << v1.capacity() << "  v1 size: " << v1.size() << std::endl;
std::cout << "v2 capacity: " << v2.capacity() << "  v2 size: " << v2.size() << std::endl;
std::cout << "vv capacity: " << vv.capacity() << "  vv size: " << vv.size() << std::endl;

输出：

v1 capacity: 10  v1 size: 10
v2 capacity: 10  v2 size: 10
vv capacity: 2  vv size: 2
v1 capacity: 20  v1 size: 20
v2 capacity: 20  v2 size: 20
vv capacity: 2  vv size: 2

- Yinuo

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

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

- Sergey Kalinichenko · Accepted Answer

关于向量，存储在地址&A中的信息有多少（或哪些）？

您的想法是正确的，向量的数据通常与向量对象本身分开存储，存储在动态内存中。

向量对象本身需要知道以下三件事情：

- 向量数据的位置 - 我们需要此来执行[]操作符， - 当前分配的大小 - 我们需要此来了解何时增加数组大小，以及 - 实际放置到向量中的元素数量 - 我们需要此来确定push_back的位置以及从size()返回的值。

不同的实现可能存储尽可能少的单一指针在向量对象中。然而，典型实现会存储一个指向分配块开头的指针，一个指向分配块的活动部分末端的指针和一个指向分配块的末端的指针。