17

我是 C++ 新手，我在我的项目中使用矢量类。我发现它非常有用，因为我可以拥有一个在必要时自动重新分配的数组（即，如果我想 push_back 一个项目并且向量已经达到它的最大容量，它会重新分配自己，向操作系统请求更多内存空间），所以访问向量的元素非常快（它不像列表，要到达“第 n 个”元素，我必须通过“n”个第一个元素）。

我发现这个问题非常有用，因为他们的答案完美地解释了当我想将向量存储在堆/堆栈上时“内存分配器”的工作原理：

[1] vector<Type> vect;
[2] vector<Type> *vect = new vector<Type>;
[3] vector<Type*> vect;

然而，一个疑问困扰了我一段时间，我找不到答案：每当我构建一个向量并开始推入很多项目时，它会到达向量将满的时刻，所以继续增长它需要重新分配，将自身复制到一个新位置，然后继续 push_back 项目（显然，这种重新分配隐藏在类的实现中，所以它对我来说是完全透明的）

好吧，如果我在堆 [2] 上创建了向量，我可以毫不费力地想象可能发生的事情：类向量调用 malloc，获取新空间，然后将自身复制到新内存中，最后删除调用 free 的旧内存。

然而，当我在堆栈上构造一个向量时，面纱隐藏了正在发生的事情[1]：当向量必须重新分配时会发生什么？AFAIK，每当在 C/C++ 上输入一个新函数时，计算机都会查看变量的声明，然后扩展堆栈以获得放置这些变量所需的空间，但是当功能已经在运行。类向量如何解决这个问题？

4

7 回答 7

58

你写了

[...] 将自身复制到新位置 [...]

这不是向量的工作方式。矢量数据被复制到新位置，而不是矢量本身。

我的回答应该让您了解矢量是如何设计的。

常见的 std::vector 布局*

注意：std::allocator实际上可能是一个空类，并且std::vector可能不包含此类的实例。对于任意分配器，这可能不是真的。

std::vector 布局

在大多数实现中，它由三个指针组成，其中

  • begin指向堆上向量的数据存储器的开始（如果不是，则始终在堆上nullptr）
  • end将一个内存位置指向矢量数据的最后一个元素 ->size() == end-begin
  • capacity内存位置上的点经过向量内存的最后一个元素->capacity() == capacity-begin

堆栈上的向量

我们声明一个类型的变量，std::vector<T,A>其中T是任何类型，并且A是T(ie std::allocator<T>) 的分配器类型。

std::vector<T, A> vect1;

这在记忆中是什么样子的？

堆栈上的 std::vector

正如我们所看到的：堆上什么都没有发生，但变量占用了堆栈上所有成员所需的内存。它就在那里，它会一直呆在那里直到vect1超出范围，因为vect1它只是一个对象，就像任何其他类型的对象double一样int。无论它在堆上处理多少内存，它都会坐在它的堆栈位置并等待被销毁。

的指针vect1不指向任何地方，因为向量是空的。

堆上的向量

现在我们需要一个指向向量的指针并使用一些动态堆分配来创建向量。

std::vector<T, A> * vp = new std::vector<T, A>;

让我们再看看内存。

堆上的 std::vector

我们在堆栈上有我们的 vp 变量，我们的向量现在在堆上。同样，向量本身不会在堆上移动，因为它的大小是恒定的。如果发生重新分配，只有指针 ( begin, end, capacity) 会移动到内存中的数据位置。让我们来看看。

将元素推送到向量

现在我们可以开始将元素推送到向量。让我们看看vect1。

T a;
vect1.push_back(a);

单次 push_back 后的 std::vector

该变量vect1仍在原来的位置，但堆上的内存被分配以包含T.

如果我们再添加一个元素会发生什么？

vect1.push_back(a);

第二次推送后的 std::vector

  • 在堆上为数据元素分配的空间是不够的（因为它只是一个内存位置）。
  • 将为两个元素分配一个新的内存块
  • 第一个元素将被复制/移动到新存储中。
  • 旧内存将被释放。

我们看到：新的内存位置不同。

为了有更多的了解，让我们看看如果我们破坏最后一个元素的情况。

vect1.pop_back();

分配的内存不会改变，但最后一个元素将调用其析构函数，并且结束指针向下移动一个位置。

2x push 和 1x pop 后的 std::vector

如您所见：capacity() == capacity-begin == 2而size() == end-begin == 1

于 2013-06-25T16:17:23.863 回答
7

向量对象很可能在堆栈上实例化，但向量中的数据将在堆上。

（平凡的类class foo {int* data;};有这个特点）

于 2013-06-25T14:27:02.380 回答
6

您构造向量（堆栈或堆）的方式对此无关紧要。

请参阅文档std::vector

在内部，向量使用动态分配的数组来存储它们的元素。当插入新元素时，可能需要重新分配该数组以增加大小，这意味着分配一个新数组并将所有元素移至该数组。

当向量“增长”时，向量对象不会增长，只有内部动态数组发生变化。

至于它的实现，可以看GCC的vector实现。

为简单起见，它将 vector 声明为具有一个受保护成员的类，类型为_Vector_impl。

如您所见，它被声明为包含三个指针的结构：

  • 指向存储开头（和数据开头）的
  • 指向数据末尾的
  • 一个用于存储结束
于 2013-06-25T14:28:06.543 回答
4

您本质上是在询问 a 的实现细节vector。C++ 标准没有定义a的实现方式——它只定义了 a应该做什么以及需要实现什么操作。没有人能 100% 准确地告诉您重新分配 a 时会发生什么，因为每个编译器在理论上都是不同的。vectorvectorvector

话虽如此，不难理解 avector通常是如何实现的。向量本身只是一个数据结构，它有一个指向存储“在”中的实际数据的指针vector。这些方面的东西：

template <typename Val> class vector
{
public:
  void push_back (const Val& val);
private:
  Val* mData;
}

以上显然是psudocode，但你明白了。当 avector在堆栈（或堆）上分配时：

vector<int> v;
v.push_back (42);

内存可能最终看起来像这样：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +=======+

当你push_back到一个完整的向量时，数据将被重新分配：

+=======+        
| v     |
+=======+       +=======+
| mData | --->  |  42   |
+=======+       +-------+
                |  43   |
                +-------+
                |  44   |
                +-------+
                |  45   |
                +=======+

...并且指向新数据的向量指针现在将指向那里。

于 2013-06-25T15:04:09.993 回答
1

你也可以保留预定的尺寸，

vect.reserve(10000);

这将保留 10000 个所用类型的对象空间

于 2013-06-25T15:17:34.770 回答
1

向量不是元素数组，也不是用于存储元素的内存。

向量管理一个元素数组，它根据需要为其分配、取消分配、收缩和增长的内存。

您对如何分配向量本身的选择与向量自己决定如何以及在何处分配它为您管理的内存无关。

我不想阻止您对矢量内部如何工作的兴趣（它既有趣又有用），但是……编写类和记录它们的全部意义在于您只需要了解接口，而不是实现。

于 2013-06-25T15:29:03.213 回答
0

如果您制作一些不断增长的向量，从空到某个大小，将使用加倍策略，并且大部分时间重新分配，在此示例中使用从 1 到 10000 的整数，并且 clang (std=2a -O3) 会得到这个，这只是为了好玩，显示使用储备的重要性。vector::begin() 指向实际数组的开头，vector::capacity 显示实际容量。另一方面，显示迭代器无效。

std::vector<int> my_vec;
auto it=my_vec.begin();
for (int i=0;i<10000;++i) {
    auto cap=my_vec.capacity();
    my_vec.push_back(i);
    if(it!=my_vec.begin()) {
        std::cout<<"it!=my_vec.begin() :";
        it=my_vec.begin();
    }
    if(cap!=my_vec.capacity())std::cout<<my_vec.capacity()<<'\n';
}

这会产生以下结果：

it!=my_vec.begin() :1
it!=my_vec.begin() :2
it!=my_vec.begin() :4
it!=my_vec.begin() :8
it!=my_vec.begin() :16
it!=my_vec.begin() :32
it!=my_vec.begin() :64
it!=my_vec.begin() :128
it!=my_vec.begin() :256
it!=my_vec.begin() :512
it!=my_vec.begin() :1024
it!=my_vec.begin() :2048
it!=my_vec.begin() :4096
it!=my_vec.begin() :8192
it!=my_vec.begin() :16384
于 2019-06-07T15:36:55.523 回答