从一个文件中讲稿未知数目的整数。对这些整数排序,然后把它们输出到标准输出设备。选用vector、deque 还是 list?
在这个场景中,我们需要从一个文件中读取未知数目的整数,然后对这些整数进行排序并输出到标准输出设备。
选择 std::vector
理由
- 高效读取: 对于从文件中读取大量数据的情况,std::vector 可以一次性读取整个文件到一个大的连续的内存块中,这通常比逐个插入到其他容器中更有效率。
- 排序功能: std::vector 有 sort 成员函数,可以直接对vector中的元素进行排序。
- 内存连续性: 连续的内存布局有助于提高缓存的效率。
优点:
- 一旦读取所有整数,可以一次性对整个 vector 进行排序,这比逐个插入到 std::list 或 std::deque 然后排序要高效得多。
不选择 std::deque
理由
- 频繁重新分配: std::deque 需要在插入或删除时管理多个节点的内存分配,如果频繁进行这种操作,可能会导致多次内存重新分配和复制,从而降低效率。
- 不必要的高内存开销: 如果不使用双端特性,std::deque 的内存分配模式可能不如 std::vector 高效。
不选择 std::list
理由
- 插入和删除慢: 虽然可以在 std::list 的任意位置插入和删除元素,但这种操作的时间复杂度为 O(1),但排序操作的时间复杂度是 O(n log n)。对于大量的整数,这会变得非常耗时。
- 随机访问慢: 与 std::deque 和 std::vector 相比,std::list 的随机访问速度较慢。
结论
对于这个任务,std::vector 是最合适的选择。
代码示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
int main() {
std::ifstream file("input.txt"); // 假设整数存储在 "input.txt" 文件中
std::vector<int> numbers;
if (!file.is_open()) {
std::cerr << "Unable to open file." << std::endl;
return 1;
}
int number;
while (file >> number) {
numbers.push_back(number);
}
std::sort(numbers.begin(), numbers.end()); // 对整数进行排序
for (int num : numbers) {
std::cout << num << std::endl; // 输出到标准输出
}
file.close();
}