c++ - How is vector<vector<int>> "heavier" than vector<pair<int,int>>?

ID : 131352

viewed : 5

Tags : c++algorithmvectorc++

Top 5 Answer for c++ - How is vector<vector<int>> "heavier" than vector<pair<int,int>>?

vote vote

92

Each vector is a single contiguous area of memory, dynamically allocated.

Let's say that you have 1000 values you'll be working with.

std::vector<std::pair<int, int>> 

This gets you a single, contiguous block of memory, for 2000 integers.

std::vector<std::vector<int>> 

This gets you a single contiguous block of memory for 1000 vectors.

Each one of those 1000 std::vectors gets you another contiguous block of memory for just two integers.

So, instead of one single contiguous block of memory, for this data structure, it will consist of 1001 blocks of memory scattered all over. You have no guarantees, whatsoever, that all those blocks of memory will be contiguous, one after another.

Each dynamic memory allocation comes at a cost. The cost is fairly small but it adds up very, very quickly. A single penny is easily ignored. A thousand pennies should be enough to get you a cup of coffee at Starbucks.

Furthermore, modern CPUs are very, very good at accessing contiguous blocks of memory. Iterating over a single contiguous block of memory to add up two thousand ints will be much, much faster than doing the same over a thousand disjointed sections of memory.

vote vote

86

You can answer this without reference to any particular language. The problem called for storing a sequence of 2-tuples. Your chosen type should be capable of storing 2-tuples, of course, but also be incapable of storing tuples of other sizes. So given two types that are both capable of storing the desired values, prefer the one that is less capable of storing undesired values.

vector<int> would allow you to store 2-element vectors, but also empty vectors, singleton vectors, 3-element vectors, 4-element vectors, etc. pair<int,int> is more precise, since it can only store exactly two values.

(Not to discount the performance benefits mentioned in the accepted answer, only to provide a purely semantic argument for using precise types.)

vote vote

77

As others mentioned, std::vector<int> adds for example a counter of the number of elements.

But an interesting aspect you could have suggested in the interview would be to use std::array<int, 2>. It should have a similar cost as std::pair<int, int> as it will store the numbers in a fixed-sized array. One advantage would be the API, which allows to use a[0] instead of a.first and also is easier to generalize when you may need to store, for example, three values per entry after some new features was added.

vote vote

68

To simplify the explanation, let's say that

  • A[ a | b ] B[ c ] means: a and b are in chunk A and c in chunk B.
  • Chunks here are continuous pieces of memory, so a is next to b

With that in mind, lets see an example: the memory usage of { { 1, 1 } , { 2, 2 }, ... }

For std::vector<<std::vector<int>>

  • A[ size info | ptr to B ]
  • B[ [ size info | ptr to C ] | [ size info | ptr to D ] | ... ]
  • C[ 1 | 1 ]
  • D[ 2 | 2 ]

For std::vector<std::pair<int, int>>

  • A[ size info | ptr to B ]
  • B[ [ 1 | 1 ] | [ 2 | 2 ] | ... ]

I think the example is very clear: there is one layer of indirection less when doing std::vector<std::pair<int, int>>. Meaning

  1. There is less memory consumption (you don't need extra variables for the size and a pointer to a chunk for each element).
  2. To get a desired value you would do less steps (otherwise, you would have to first load and read the pointer and then with that address load the desired value).
vote vote

58

A vector is a dynamically-resizing array. You sacrifice some performance to get the ability to resize dynamically.

A vector of vectors (vector<vector<int>>) has that performance overhead for both the outer vector and each of its elements. With a vector of pairs (vector<pair<int, int>>), you don't have the latter. A pair is always of a fixed size, so you needn't worry about having to resize it as needed (and relocate it to another position in memory if needed).

Top 3 video Explaining c++ - How is vector<vector<int>> "heavier" than vector<pair<int,int>>?

Related QUESTION?