3

In C++11, how does a 2D vector against 1D vector in terms of time?
In the 2D vector given, all the inner vectors are of the same size.

Ex:

std::vector<std::vector<int>> X{10, std::vector<int>(4)};

vs 

std::vector<int> Y(40);

Which avatar of the vector would perform better when the elements are randomly accessed?

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
letsBeePolite
  • 2,183
  • 1
  • 22
  • 37
  • 6
    As with any time measurement, you must measure on the system you care about. – merlin2011 Dec 30 '16 at 17:23
  • 1
    @merlin2011 I was wondering is there anything different that C++ optimizes 2D vector in comparison to 1D. I was worried as my few runs and not so expertise in C++11 might end up me assuming something incorrectly. – letsBeePolite Dec 30 '16 at 17:26
  • 1
    The first rule of any performance measurements is that the first measurement is always wrong. But that's why we keep measuring until we have reason to be confident. :P – merlin2011 Dec 30 '16 at 17:30

1 Answers1

7

A single std::vector is inherently simpler, it's just a contiguous block of memory stored somewhere.

A std::vector of std::vector has more overhead but it's also more powerful (since each inner vector can be of different size, for example).

Random access performance should be benchmarked thoroughly for your specific pattern of usage but the main difference is that:

  • with single vector you just compute size_t index = x + y*WIDTH and access the element
  • with nested vector you have two levels of indirection, first you must obtain the memory containing the inner vector, then you must obtain the memory of the data of the inner vector.
Jack
  • 131,802
  • 30
  • 241
  • 343
  • 1
    Yep, the extra level of indirection results in extra memory accesses that slow things down, sometimes by large factors in modern systems. On now archaic CPUs the extra indirection could sometimes be faster since multiplies could be quite time consuming relative to memory access. One sometimes sees code written over 20 years ago that did that. Generally bad practice these days unless one needs variable row sizes. – doug Dec 30 '16 at 19:05
  • 1
    If you know any of the inner or outer sizes at compile time, use, for example, `std::array, 4>`. If you are really after performance, you can have a new matrix type either as a stand alone type, OR, deriving from or composing `std::vector`. If you are going to do the latter, please read this [link](http://stackoverflow.com/questions/4353203/thou-shalt-not-inherit-from-stdvector). – NameRakes Dec 30 '16 at 22:58