需要一种更快的方法来在 C++ 中创建邻接表

Question

我正在尝试根据顶点、边和单个连接的输入创建邻接表。输入如下所示：

3 2（顶点、边）

1 2（连接）

1 3

现在，我的密码是

int vertices, edges;
scanf("%d %d", &vertices, &edges);

vector<vector<int>> storage[vertices+1];
for (int i = 0; i < edges; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (find(storage[b].begin(), storage[b].end(), a) != storage[b].end() == false) {
        storage[b].push_back(a);
    }
    if (find(storage[a].begin(), storage[a].end(), b) != storage[a].end() == false) {
        storage[a].push_back(b);
    }
}

是否有 faster/more 有效的方法，或者这是最好的方法？

Answer 1

几乎不可能对此类问题给出一般性答案，因为执行时间将取决于可能相差几个数量级的因素。例如，与您之后对其进行的操作相比，填充数据结构的成本可能微不足道。另见，我将引用其最终建议：

As always, profiling and measuring runtime and memory to find bottlenecks for you actual problem implementation is key if you are implementing a highperf computation program.

该答案还提到了您可以考虑的一些不同的 STL 容器。 Here and here 还有两个关于这个主题的问题。

话虽如此，在尝试改进任何东西之前先进行衡量。例如，如果分段读取输入被证明是一个瓶颈，您可以考虑在进一步处理之前将其全部读入 std::string。

为了完整起见，我可能会像这样用标准 C++ 编写您当前的代码：

#include <algorithm>
#include <iostream>
#include <vector>

// ...

// Speeds up std i/o, but don't mix the C and C++ interfaces afterwards
std::ios_base::sync_with_stdio(false);

int vertices, edges;
std::cin >> vertices >> edges;

std::vector<std::vector<int>> storage(vertices + 1);
// When filling vectors with push_back/emplace_back, it's best to call 
// reserve first. If using 1-based indexing, skip the first vector:
for (auto v = std::next(storage.begin()); v != storage.end(); ++v)
    v->reserve(vertices - 1);

// With C++20 support you can #include <ranges> and write
for (auto& v : storage | std::views::drop(1))
    v.reserve(vertices - 1);

auto found = [](auto const& vector, auto value) {
    return std::find(vector.begin(), vector.end(), value) != vector.end();
// or, with C++20: std::ranges::find(vector, value) != vector.end()
};

for (int a, b, i = 0; i < edges && std::cin >> a >> b; ++i) {
    if (!found(storage[b], a))
        storage[b].push_back(a);
    // ...
}

需要一种更快的方法来在 C++ 中创建邻接表

Need a faster way to create an adjacency list in c++

c++

arrays

adjacency-list