Why std::array is faster than std::vector(10) in this scenario?

Question

The task (from a Bulgarian judge, click on "Език" to change it to English):

I am given N, where N belongs to [3; 1000000] different numbers X, where X belongs to [0; 18446744073709551616).

How many numbers can be formed by rearranging the digits of a different number in the input ?

Example:

6

25 21 10242 42210 52 24021

Answer:

5

Explanation:

There are 5 different numbers namely {25, 52} and {10242, 42210, 24021}

25 -> 52 and 52 -> 25

10242 -> 42210 and 42210 -> 10242

10242 -> 24021 and 24021 -> 10242

42210 -> 24021 and 24021 -> 42210

lhs -> rhs means that rhs can be formed from the digits of lhs

I solved the task successfully. Here is my solution:

#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <iterator>

namespace Const {
    std::string::size_type constexpr sz_max{ 20 };
}

int main() {
    // 0
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    // 1
    int n;
    std::cin >> n;
    int i;
    std::string x;
    x.reserve(Const::sz_max);
    std::vector<std::array<int, 10>> lut(n);
    for (i = 0; i != n; ++i) {
        std::cin >> x;
        for (auto const& ch : x) {
            ++lut[i][ch - '0'];
        }
    }
    // 2
    std::sort(lut.begin(), lut.end());
    // 3
    auto prev{ lut.cbegin() };
    decltype(prev) curr;
    auto cnt{ 1 }, ans{ 0 };
    for (curr = std::next(prev); curr != lut.cend(); ++curr) {
        if (*curr == *prev) {
            ++cnt;
        }
        else {
            if (cnt != 1) {
                ans += cnt;
            }
            prev = curr;
            cnt = 1;
        }
    }
    if (cnt != 1) {
        ans += cnt;
    }
    prev = curr;
    cnt = 1;
    // 4
    std::cout << ans << '\n';
    return 0;
}

The execution time of this version is 550-600 ms.

If I change the definition of lut in // 1 from

std::vector<std::array<int, 10>> lut(n);

to

std::vector<std::vector<int>> lut(n, std::vector<int>(10));

the execution time increases drastically to 1050-1150 ms.

In both cases heap allocations have to take place but why the first ones are faster than the second ones ?

Don't try to learn C++ by solving competitive coding puzzles. The reason is in the way [std::vector](https://en.cppreference.com/w/cpp/container/vector) and [std::array](https://en.cppreference.com/w/cpp/container/array) manage memory. Just read the reference material — Pepijn Kramer, Jul 24 '23 at 08:39
Learn C++ from : [a recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or from [learncpp.com](https://www.learncpp.com/) that site is decent and pretty up to date. Then use [cppreference](https://en.cppreference.com/w/) for reference material (and examples). When you have done all that keep using [C++ core guidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) to keep up to date with the latest best practices since C++ keeps evolving. — Pepijn Kramer, Jul 24 '23 at 08:40
`std::array` was added to the library because there are possible optimizations available when knowing the size beforehand. Now you have found a case where that doubles the speed. Good! (In practice, the first example can be done with 1 heap allocation, and the second would take 10). — BoP, Jul 24 '23 at 08:43
"_In both cases heap allocations have to take place_": Yes, but each nested `std::vector` does an additional one. `std::vector>` only needs one contiguous allocation. — user17732522, Jul 24 '23 at 08:44
@user17732522 10^6 heap allocations of std::array vs 10^6 heap allocations of std::vector(10) in worst case scenario where N = 10^6, right ? — Petar Ivanov, Jul 24 '23 at 08:49
`std::vector> lut(n);` is allocating memory for the vectors elements once. `std::vector> lut(n, std::vector(10));` 11 times. If your would do nothing else a factor of 10 is reasonable. Your code does more, hence your factor of 2 is reasonable — 463035818_is_not_an_ai, Jul 24 '23 at 08:52
@PetarIvanov `std::array` itself does not perform any heap allocation, but `std::vector` itself performs an allocation when initialized to a certain size. — user17732522, Jul 24 '23 at 09:03
@user17732522 Ah ok I think I got it. In the first case the vector wrapper has to make 10^6 allocations of std::array. In the second case the vector wrapper has to make 10^6 allocations of std::vector(10) and each one of these 10^6 has to allocate itself 10 elements. Is that correct ? — Petar Ivanov, Jul 24 '23 at 09:06
@PetarIvanov No, `vector` allocates its elements in a single contiguous storage range. It will only allocate at most once whenever you change its size, regardless of the number of elements. — user17732522, Jul 24 '23 at 09:10
No only 'n` allocations will be made. You might just as well remove all the code from `//0` too. There is no way this kind of code is ever found in real products. It is just meaningless blurb copied blindly (cargo cult) that will not even improve performance — Pepijn Kramer, Jul 24 '23 at 09:10
@Pepijn Kramer Yes ofc N allocations will be made. I am talking about the worst case scenario where N = 10^6 so once again N allocations of std::array vs N allocations of std::vector(10) and each one of these N allocations has to allocate itself 10 elements. Is that correct ? — Petar Ivanov, Jul 24 '23 at 09:13

score 2 · Accepted Answer · answered Jul 24 '23 at 12:18

2

std::array doesn't make a separate heap allocation for its elements like std::vector does, i.e.,

sizeof(std::array<int,16>) == sizeof(int) * 16

All of the elements are stored directly in the object. Because of this, all the data in a vector<array<int,10>> is stored in the same contiguous allocation.

answered Jul 24 '23 at 12:18

Matt Timmermans

53,709
3
46
87

If I understand correctly this means that in the vector> case the vector lut makes exactly 1 heap allocation for N elements each of which is array whereas in the vector> case the vector lut makes 1 heap allocation for N vectors each of which makes separate heap allocation for its 10 elements. So we have 1 vs (1 + N) heap allocations. – Petar Ivanov Jul 24 '23 at 12:35
that is correct – Matt Timmermans Jul 24 '23 at 12:36
vector does contigous allocation, so (1 + N) is worst case (assymptotic) implementation. – Swift - Friday Pie Jul 29 '23 at 08:37

Why std::array is faster than std::vector(10) in this scenario?

1 Answers1