3

这个问题来源于这个话题：

矢量储备 c++

我正在使用类型的数据结构vector<vector<vector<double> > >。double在添加项目（s）之前，不可能知道这些向量中的每一个（除了外部向量）的大小。我可以得到每个“维度”中项目数量的近似大小（上限）。

具有共享指针的解决方案可能是要走的路，但我想尝试一个解决方案，其中vector<vector<vector<double> > >简单地拥有.reserve()足够的空间（或以其他方式分配了足够的内存）。

A.reserve(500)（假设 500 是大小，或者大小的上限）是否足以容纳大尺寸的“2D”向量，比如 [1000][10000] ？

我提出问题的原因主要是因为我看不到任何合理估计当时的内部大小的A方法.reserve(500)。

我的问题的一个例子：

vector<vector<vector<int> > > A;
A.reserve(500+1);
vector<vector<int> > temp2;
vector<int> temp1 (666,666);
for(int i=0;i<500;i++)
{
  A.push_back(temp2);
  for(int j=0; j< 10000;j++)
  {
    A.back().push_back(temp1);
  }
}

这会确保不对 A 进行重新分配吗？

如果temp2.reserve(100000)并且temp1.reserve(1000)在创建时添加，这将确保根本不会发生重新分配吗？

.reserve()在上面请忽略由于保守的调用可能会浪费内存的事实。

谢谢大家！

4

10 回答 10

1

预先在 A 中保留 500 个条目如何足以满足 [1000][1000] 的需求？

您需要为 A 保留 > 1000（这是您的实际上限值），然后每当您向 A 添加条目时，在其中保留另外 1000 左右（同样，上限，但为第二个值）。

IE

A.reserve(UPPERBOUND);

for(int i = 0; i < 10000000; ++i)
   A[i].reserve(UPPERBOUND);

顺便说一句，reserve 保留元素的数量，而不是字节数。

于 2010-02-28T15:50:09.897 回答
1

您的示例将导致大量复制和分配。 

vector<vector<vector<double>>>  A;
 A.reserve(500+1);
 vector<vector<double>>  temp2; 
vector<double> temp1 (666,666);
 for(int i=0;i<500;i++) 
{
 A.push_back(temp2);
 for(int j=0; j< 10000;j++)
 {
 A.back().push_back(temp1);
 }
}

问：这会确保不对 A 进行重新分配吗？
答：是的。

问：如果在创建时添加 temp2.​​reserve(100000) 和 temp1.reserve(1000)，这将确保根本不会发生重新分配吗？
A：这里 temp1 已经知道自己的创建时间长度，不会被修改，所以添加 temp1.reserve(1000) 只会强制进行不需要的重新分配。
我不知道向量类在他们的复制ctor中复制了什么，使用 A.back().reserve(10000) 应该适用于这个例子。
更新：刚用g++测试过，不会复制temp2的容量。所以 temp2.​​reserve(10000) 将不起作用。

并且请在发布代码时使用源格式，使其更具可读性:-)。

于 2010-02-28T16:08:35.993 回答
1

该reserve功能会为您正常工作vector A，但不会像您期望的那样工作temp1和temp2。

temp1向量是用给定的大小初始化的，所以它会被设置为正确的，只要你不打算增加它的大小capacity，你就不需要使用它。reserve

关于temp2，capacity属性不会被复制到副本中。考虑到每当您使用push_back函数时，您都会将副本添加到您的vector, 代码中

vector<vector<double>> temp2;
temp2.reserve(1000);
A.push_back(temp2); //A.back().capacity() == 0

您只是为将很快释放的临时增加分配的内存，而不是vector像您期望的那样增加元素容量。如果你真的想使用vector作为vector你的解决方案，你将不得不做这样的事情

vector<vector<double>> temp2;
A.push_back(temp2);
A.back().reserve(1000); //A.back().capacity() == 1000
于 2010-02-28T16:25:44.083 回答
1

有一天我遇到了同样的问题。一种干净的方法（我认为）是编写自己的Allocator并将其用于内部向量（的最后一个模板参数std::vector<>）。这个想法是编写一个分配器，它实际上并不分配内存，而只是在外部向量的内存中返回正确的地址。如果您知道每个先前向量的大小，则可以轻松知道该地址。

于 2010-03-01T17:56:32.343 回答
1

为了避免复制和重新分配数据结构，例如vector<vector<vector<double> > >，我建议如下：

vector<vector<vector<double> > > myVector(FIXED_SIZE);

为了给它“分配”值，在你真正知道它们所需的尺寸之前不要定义你的内部向量，然后使用 swap() 而不是赋值：

vector<vector<double> > innerVector( KNOWN_DIMENSION );
myVector[i].swap( innerVector );

请注意，push_back()它将执行复制操作并可能导致重新分配，而swap()不会（假设两个向量使用相同的分配器类型）。

于 2010-04-08T12:02:27.773 回答
0

在我看来，您需要一个真正的矩阵类而不是嵌套向量。看看 boost，它有一些强大的稀疏矩阵类。

于 2010-02-28T16:49:25.407 回答
0

好的，现在我自己做了一些小规模的测试。我使用从http://www.tek-tips.com/faqs.cfm?fid=5575获得的“2DArray”来表示分配内存静态的结构。对于动态分配，我几乎按照我原来的帖子中的说明使用了向量。

我测试了以下代码（hr_time 是在网络上发现的一个计时例程，由于反垃圾邮件，我很遗憾无法发布，但感谢 David Bolton 提供它）

#include <vector>
#include "hr_time.h"
#include "2dArray.h"
#include <iostream>
using namespace std;

int main()
{
    vector<int> temp;

    vector<vector<int> > temp2;

    CStopWatch mytimer;

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp2.push_back(temp);
        for(int j=0; j< 2000; j++)
        {
            temp2.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors without reserved: " << mytimer.getElapsedTime() << endl;

    vector<int> temp3;

    vector<vector<int> > temp4;

    temp3.reserve(1001);

    mytimer.startTimer();

    for(int i=0; i<1000; i++)
    {
        temp4.push_back(temp3);
        for(int j=0; j< 2000; j++)
        {
            temp4.back().push_back(j);
        }
    }

    mytimer.stopTimer();

    cout << "With vectors with reserved: " << mytimer.getElapsedTime() << endl;

    int** MyArray = Allocate2DArray<int>(1000,2000);

    mytimer.startTimer();
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 2000; j++)
        {
            MyArray[i][j]=j;
        }
    }


    mytimer.stopTimer();

    cout << "With 2DArray: " << mytimer.getElapsedTime() << endl;

    //Test
    for(int i=0; i<1000; i++)
    {
        for(int j=0; j< 200; j++)
        {
            //cout << "My Array stores :" << MyArray[i][j] << endl;
        }
    }

    return 0;
}

事实证明，这些尺寸大约有 10 倍。因此，我应该重新考虑动态分配是否适合我的应用程序，因为速度至关重要！

于 2010-03-01T17:28:29.913 回答
0

为什么不在构造函数中子类化内部容器和reserve()？

于 2010-03-17T00:09:55.983 回答
0

如果矩阵确实变得非常大而且空闲，我也会尝试一个稀疏矩阵库。否则，在弄乱分配器之前，我会尝试用双端队列替换向量。双端队列不会在增长时重新分配，并且提供几乎与向量一样快的随机访问。

于 2010-04-16T17:26:35.803 回答
0

这或多或少在这里得到了回答。所以你的代码看起来像这样：

vector<vector<vector<double> > > foo(maxdim1,
    vector<vector<double> >(maxdim2,
    vector<double>(maxdim3)));
于 2010-05-07T15:11:46.023 回答