需要更快的方法在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);
    }
}

是否有更快/更有效的方法来做到这一点，或者这是最好的方法？

Answer 1

几乎不可能给出这类问题的一般答案，因为执行时间将取决于可能相差数量级的因素。例如，与事后使用数据结构相比，填充数据结构的成本很小。还请参阅this answer，我将引用它的最后建议：

与往常一样，分析和测量运行时和内存，为您找到实际问题实现的瓶颈是关键，如果您正在实现一个highperf计算程序。

这个答案还提到了一些您可以考虑的不同的STL容器。Here和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);
    // ...
}