c++ - 在 C++ 中分配动态数组的附加成员

Question

我正在尝试找出是否可以为 C++ 中的动态数组的其他成员分配额外的内存。为简单起见，下面的代码被精简为基本内容。

我基本上想做的是从文件中将元素读入 someClass 中的 arr 中，但我想这样做，这样文件就不必指定如何它包含许多元素(这对于我正在处理的整个项目来说是必不可少的)。我显然想到了分配一个size+1的新数组，然后将所有当前元素复制到其中并读取一个新元素的解决方案，但我发现这将是一种残酷的浪费处理时间和内存，如果可以简单地分配下一个内存地址并将其用于我的数组。有没有办法在 C++ 中做到这一点？

总而言之，我想读取一个元素，为我的数组分配一个新的内存地址，然后将另一个元素读入新分配的内存地址。重复直到文件结束。

我不会让你厌烦的原因，但使用简单的 std::vector 不是一个选项。

代码如下:

class someClass {
public:
    int *arr;
    void Read(ifstream&,int&);
};

void someClass::Read(ifstream &inFile, int &size) {
    arr = new int[0];
    inFile.open("input.txt");

    int index = 0;
    int element;
    while (!inFile.eof()) {
        inFile >> element;
        *(arr + index) = element;
        index ++;
    }

    size = index;
    inFile.close();
}

int main() {

    int size;
    someClass a;
    ifstream inFile;

    a.Read(inFile,size);
    //obviously unnecessary, just for testing
    for(int i = 0; i < size; i ++) {
        cout << a.arr[i] << " ";
    }
    cout << endl;
}

Answer 1

我只是喜欢这个问题并自己做了一些实验，使用 MSVC14编译器(禁用优化)。
C++11/14 具有以下序列容器(有意排除了 C++14 中引入的 dynarry):

1. 没有动态调整大小(由程序员分配和解除分配)
   • 原始数组(例如 int char[])
   • 数组(例如 new array<int, size>(){...} )
2. 动态调整大小
   • vector (连续内存分配)
   • 列表(类似于数组的链表)
   • forward_list(类似于列表)
   • deque(双端队列)

让我从你的问题开始，

the solution of allocating a new array with a size+1, and then copying all the current elements into it and reading a new element, but I find that this would be a brutal waste of processing time and memory

你是对的，但是为了减轻开销，当你分配内存使用然后你发现你需要比分配更多的内存时，你需要分配新内存并复制以前的数据，然后释放以前分配的内存。
可是等等!分配多少(size+1 不好)？每次你被迫分配更大的内存块时，你最好分配你手头现有大小的两倍，这样你就可以减少另一次内存重新分配的可能性；因为它被认为是一项极其昂贵的操作。

if it is possible to simply allocate the next memory address and use it for my array. Is there a way to do that in C++?

这并不完全在您的控制之中，因为 C++ 运行时已经实现了内存管理功能。你新分配的内存在哪里，不在你的控制之下，但是有时会发生新分配的空间与前一个空间具有相同的基地址;这取决于运行时和 memory fragmentation它面向。

我使用 malloc 获得了一些基准测试和 realloc借用的功能来自 C。这是代码:

    auto start = chrono::steady_clock::now();

    auto partialSize = 100;
    auto arr = (int *) malloc(sizeof(int) * partialSize);


    for (auto i = 0; i < SIZE; i++) {
        arr[i] = i;
        if (i == partialSize - 1) {
            partialSize = partialSize << 1; // for 2X
            arr = (int *) realloc(arr, sizeof(int) * partialSize);
        }
    }

    auto duration = chrono::steady_clock::now() - start;

    free(arr);

    cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl;

结果(插入 100,000,000 个整数；时间是 3 次运行的平均值):

• 起始大小 = 100，增量步长 = 1.5X，时间 = 1.35s
• 起始大小 = 100，增量步长 = 2X，时间(s)= 0.65s

• 起始大小 = 100，增量步长 = 4X，时间 = 0.42 秒

• 起始大小 = 10,000，增量步长 = 1.5X，时间 = 0.96 秒

• 起始大小 = 10,000，增量步长 = 2X，时间 = 0.79s

• 起始大小 = 10,000，增量步长 = 4X，时间(s)= 0.51s

  另一种情况是使用 C++ 的 new关键字和检查重定位:

  auto start = chrono::steady_clock::now();
  auto partialSize = 100;
  auto arr = new int[partialSize];
  
  
  for (auto i = 0; i < SIZE; i++) {
      arr[i] = i;
      if (i == partialSize - 1) {
          auto newArr = new int[partialSize << 2]; // for 4X
          partialSize = partialSize << 2;
          arr = newArr;
      }
  }
  
  auto duration = chrono::steady_clock::now() - start;
  
  delete[] arr;
  
  cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl;  
  

结果(插入 100,000,000 个整数；时间是 3 次运行的平均值):

• 起始大小 = 100，增量步长 = 1.5X，时间 = 0.63s
• 起始大小 = 100，增量步长 = 2X，时间 = 0.44s

• 起始大小 = 100，增量步长 = 4X，时间 = 0.36 秒

• 起始大小 = 10,000，增量步长 = 1.5X，时间 = 0.65 秒

• 起始大小 = 10,000，增量步长 = 2X，时间 = 0.52 秒
• 起始大小 = 10,000，增量步长 = 4X，时间 = 0.42 秒

对于其余部分(动态可调整大小的容器):

auto start = chrono::steady_clock::now();

//auto arr = vector<int>{};
//auto arr = list<int>{};
//auto arr = new std::array<int, SIZE>{};
//auto arr = new int[SIZE];
//auto arr = deque<int>{};
auto arr = forward_list<int>{};

for (auto i = 0; i < SIZE; i++) {
    arr.push_front(i);
    // arr.push_back(i)
}

auto duration = chrono::steady_clock::now() - start;

cout << "Duration: " << chrono::duration_cast<chrono::milliseconds>(duration).count() << "ms" << endl;

结果(插入 100,000,000 个整数；时间是 3 次运行的平均值):

1. vector

   • 时间 = 2.17s

2. 列表

   • 时间 = 10.31s

3. 数组(无重新分配)

   • 时间 = N/A；错误:编译器超出堆。

4. 原始整型数组(无重新分配)

   • 时间(秒)= 0.22s

5. 双端队列

   • 时间 = 3.47s

6. forward_list

   • 时间 = 8.78s

希望对您有所帮助。