动态内存分配，C++

Question

我需要编写一个函数，能够读取文件，并将所有唯一的单词添加到动态分配的数组中。如果您要求数组中条目的数量，我知道如何创建动态分配的数组：

int value;
cin >> value;
int *number;
number = new int[value];

我的问题是我无法事先知道文件中有多少个不同的单词，因此我不能一开始就读取或请求它。另外，我需要让这个程序使用数组而不是向量。是否有一种类似于使用动态分配数组进行push_back的方法？

目前，我唯一能想到的是首先创建一个存储文件中所有单词（1000）的数组，然后通过它找到唯一单词的数量。然后使用该值创建一个动态分配的数组，然后再次通过它来存储所有唯一单词。显然，这个解决方案听起来非常复杂，应该有更有效的解决方案。

有人可以指点我正确的方向吗？我觉得这应该很容易用向量完成，所以我认为要求使用数组有点傻（除非在这个作业任务中需要学习有关动态分配数组的重要内容）。

编辑：这里又有一个问题。我知道文件中将有1000个单词，但是我不知道有多少个唯一的单词。我的想法是，我可以创建一个1000个元素的数组，将所有唯一单词写入该数组，并跟踪我完成了多少个。完成后，我可以根据该计数来提供一个动态分配的新数组，然后只需将单词从初始数组复制到第二个数组即可。不确定这是否是最有效的方法，但由于我们不能使用向量，因此我认为效率在这个任务中不是一个很大的问题。

- Nate

---

@ruakh：作业只是说你应该使用动态分配的数组。我可能会给我的教授发电子邮件以获得一些澄清。能够使用向量就好了。 - Nate

啊，对不起！我会进行编辑。 - Nate

我目前在本地大学的计算机科学系工作，如果你的教授不让你使用动态分配内存，而是用std::vector, 我会感到惊讶。必须练习处理那些数组！;-) - Victor Zamanian

Answer 1

相比于数组，向量确实更适合这个任务。真的。

但如果你一定要使用数组，你可以让它的行为像一个向量 :-).

方法如下：分配一个具有一定容量的数组。将分配的容量存储在一个“容量”变量中。每次添加到数组时，增加一个单独的“长度”变量。当您要添加某些内容到数组中并发现它不够大（长度==容量）时，请分配第二个更长的数组，然后将原始内容复制到新数组中，最后释放原始数组。

这样就可以实现扩展数组的效果。如果性能成为问题，请一次增加多个元素。

恭喜，按照这些简单的步骤，您已经在数组上实现了std::vector功能的一个小子集！

- Borealid

---

是的，使用向量会更容易。要求使用数组，我想是为了教我们更多关于指针的知识。你的答案听起来是个不错的解决方案，谢谢！不过我可能也会给教授发邮件，看看是否可以使用向量。 - Nate

Answer 2

正如你所指出的那样，使用 Vector 是很容易解决的。

然而，如果你只能使用数组，你可能需要执行以下操作之一：

1. 初始化数组为一个足够大的尺寸并接受内存利用不佳
2. 编写自己的代码，在运行时动态增加数组的大小（基本上是 Vector 的内部实现）

如果允许的话，某种哈希映射或链表也是一个好的解决方案。

- ose

Answer 3

如果我必须使用数组，我会首先分配一个具有一定初始大小的数组，然后在填满该数组时将其大小增加一倍，以容纳任何无法适应以前大小的数组中的新值。

由于这个问题涉及到C++，所以内存分配将使用关键字new。但是，如果可以使用realloc()函数，那就太好了，它可以调整内存大小并保留先前分配的内存中的值。这样就不需要把新值从旧数组复制到新数组中。尽管我不确定realloc()是否能与使用new分配的内存很好地配合工作。

- Victor Zamanian

---

realloc在使用new时并不兼容。但是在C++中使用malloc没有问题，完全可以这样做。 - Borealid

我早有所料。但是，可以使用malloc()，只是我不确定与使用new相比如何受到赞赏。也许这是另一个我们可以在某处找到答案的问题。;-) - Victor Zamanian

Answer 4

你可以像这样“调整大小”数组（N 是 currentArray 的大小，T 是其元素的类型）：

// create new array
T *newArray = new T[N * 2];
// Copy the data
for ( int i = 0; i < N; i++ )
 newArray[i] = currentArray[i];
// Change the size to match
N *= 2;
// Destroy the old array
delete [] currentArray;
// set currentArray to newArray
currentArray = newArray;

使用这个解决方案，您需要复制数据。可能有一种不需要它的解决方案。

但我认为对于您来说更方便的是使用std::vectors。您只需将其push_back到向量中，它们会自动调整大小。

- clime

---

啊，明白了。那基本上就是Borealid建议的实现方式对吧？（是的，我更喜欢使用向量，但似乎必须使用数组。） - Nate

是的，这正是Borealid提出的建议，只是没有呈现“length == capacity”的检查。 - clime

Answer 5

你可以有点作弊：

使用 std::set 获取所有唯一的单词，然后将 set 复制到动态分配的数组（或更好的 vector）中。

#include <iterator>
#include <set>
#include <iostream>
#include <string>


    // Copy into a set
    // this will make sure they are all unique   
    std::set<std::string>   data;
    std::copy(std::istream_iterator<std::string>(std::cin),
              std::istream_iterator<std::string>(),
              std::inserter(data, data.end()));

    // Copy the data into your array (or vector).
    std::string* words  = new std::string[data.size()];
    std::copy(data.begin(), data.end(), &words[0]);

- Martin York

Answer 6

这可能有点过头了，但你可以在C++中实现一个链表...它实际上允许你使用类似于向量的实现，而不必使用向量（实际上向量是最好的解决方案）。

实现相当容易：只需指向下一个和前一个节点，并将“头”节点存储在可以轻松访问的位置。然后只需循环遍历列表即可检查哪些单词已经存在，哪些不存在。您甚至可以实现计数器，并计算文本中单词重复的次数。

- Misguided