c++ - 什么时候拥有太多动态数组会很危险？

Question

我目前正在为一项涉及城市和桥梁的作业编写代码。我必须在他们受人尊敬的地区打印出城市和桥梁，例如:

//unorganized inputs from user given the # of "paths" we need
4       // the # of paths
1 2 5  // 1 = city , 2 = city, 5 = bridge length
6 7 5  // 6 = city , 7 = city, 5 = bridge length
2 3 7  // 2 = city , 3 = city, 7 = bridge length
6 9 7  // 6 = city , 9 = city, 7 = bridge length

程序运行后，排序为:

first district
1 2 5
2 3 7

2nd district
6 7 5
6 9 7

现在，我将通过 cin 读取这些输入。我想把1 2 5等所有可能的路径都存储到一个数组中，然后通过程序对它们进行排序和组织。问题是我可能有超过 500,000 条来自用户的路径。我想创建 500k 动态数组。这会导致严重的内存问题吗？

我研究了其他可能的解决方法，例如 kruskal 算法和不相交集(我认为这是最有用的)。我很难理解不相交集的编码，我想我尝试了一种我更熟悉的方法。

任何有关在何处存储值以及比较和组织它们的帮助都会很棒。链接到我阅读这方面信息的地方会有所帮助。在过去的几天里，我读了很多东西。帮助不大。

总而言之，我的问题是:

• 500k 动态数组是否会在内存方面造成严重问题？
• 在哪里存储值并根据路径比较和组织它们？

Answer 1

Will 500k dynamic arrays cause serious problems in terms of memory?

没问题，假设每个只是 3 个整数的数组。通常，您会避免将其作为单独的分配来执行，因为它太多了——它会有点慢，而且所需的簿记也会消耗相当多的内存。有更好的方法:

Where to store the values and compare and organize them given the paths?

我将从包含这 3 个字段的结构/类开始，然后使用它们的 std::vector。这会将您的所有值存储为一个连续的分配。相比之下，创建、搜索和分配速度非常快。