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

Question

I'm trying to create an adjacency list from an input of vertices, edges and single connections. The input looks like this:

3 2 (vertices, edges)

1 2 (connection)

1 3

Right now, my code is

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);
    }
}

Is there a faster/more efficient way to do this, or is this the best way?

`vector storage[vertices+1];` is not standard C++. Variable length arrays are only possible if you're using compiler specific extensions to C++. See also [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/q/1887097/11082165) — Brian61354270, Dec 08 '21 at 00:26
`vector storage[vertices+1];` -- I guess you didn't realize what `std::vector` is used for. If you did, then this should be `std::vector> storage(vertices + 1);` — PaulMcKenzie, Dec 08 '21 at 00:34
It’s not a surprise. It’s a compiler extension it fully works with your compiler. But it’s not portable and so discouraged. — Ben, Dec 08 '21 at 01:50
Try setting `vertices` to 1 billion and see how you get on with that variable-length array.... — paddy, Dec 08 '21 at 02:07
I guess you want to use `vector> storage(vertices+1);` (or `vector storage[vertices+1];`) since the current code does not work/compile. Besides this, I find this a bit strange to ask for faster performance with a user input function (`scanf`) in the middle main hot loop... Is this really a practical issue? How many `vertices` do you plan to have? — Jérôme Richard, Dec 12 '21 at 01:15

score 1 · Accepted Answer · answered Dec 12 '21 at 23:12

It's nearly impossible to give a general answer to this kind of question, because the execution time is going to depend on factors that may be orders of magnitude apart. For instance, it could be that the cost of populating the data structure is insignificant compared to what you do with it afterwards. See also this answer, whose final recommendation I'll quote:

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.

That answer also mentions some different STL containers you could consider. Here and here are two more questions on this topic.

With that said, measure before trying to improve anything. If reading the input piecewise turns out to be a bottleneck, for example, you could consider reading it all into a std::string in one go before further processing.

For completeness, I might write your current code in standard C++ like this:

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

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

1 Answers1