c++ - 处理输入 : growing an array, 或计数输入、分配、然后读取的速度

Question

基本上我想知道什么是处理来自标准输入的输入的更快方法:

方法一:声明一个任意大小的数组，读入数组，如果输入大于该大小，则分配一个两倍大小的新数组，将内容复制到新数组中，并释放前一个数组.

方法二:读取整个输入，边读边统计行数。将指针重置回输入的顶部，声明一个长度为行数大小的数组，然后输入到该数组中。一些背景:

1. 我没有使用 vector 。请不要说只使用 vector ...
2. 他们不会输入内容，它会从命令行重定向到一个文件。类似于 ./program < input.txt
3. 我知道第一种方法在空间方面效率较低，但它比方法第二种快吗？如果有，增加了多少？方法 2 基本上需要 2n 时间才能完成。我想知道第一种方法是否会增加我的代码的运行时间。

Answer 1

这两种方法都是 O(n)。但是，您正在从 stdin 读取数据，因此无法将其倒回到开头，除非某些东西已经将数据存储在某处，所以我不知道如何你可以使用方法 2。

您需要使用方法 1。如果您可以使用 realloc，它甚至可能不需要进行任何复制。如果您担心额外的复制，您可以将项目存储在大小呈指数增长的缓冲区链表中，然后在末尾创建一个数组，每个数组只复制一次。