c++ - 需要一种更快的方法在 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 ，我将引用他的最终建议:

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和 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);
    // ...
}