Which of these is faster?

Question

I was wondering if it was faster to have a std::vector<std::vector<double>>where the nested vector always has 2 elements, or is it faster to have a std::vector<MyPoint>where MyPoint is defined like:

struct MyPoint {
  double Point[2];
};

Thanks

Answer 1

I assume in the second example you meant: std::vector<MyPoint>? Yes that variant would be more efficient. For example you can reserve a large amount of memory easier and you will have to do less allocations overall.

Instead of MyPoint you could also use std::pair<double, double>.

Answer 2

Do you mean std::vector<MyPoint> in the second example? This would be considerably better than having a vector within a vector.

Answer 3

The vector<MyPoint> is preferable, because MyPoint is likely:

1. to be smaller than vector<double> (you can check this with sizeof), and/or
2. to make fewer allocations. A vector object itself is small, but generally points to data on the heap. It's possible for small vectors to be optimised to avoid the extra allocation by embedding the data in the vector object, but don't count on that, hence
3. to have lower overhead of initialization, destruction, and copying.

For example on my 32bit gcc, std::vector<double> has size 12, while MyPoint has size 16, but the vector makes the extra allocation. On a 64bit implementation, MyPoint will almost certainly be the same size, but std::vector will probably be bigger.

Also, a vector represents a variable-sized, ordered container using contiguous memory. So it's arguably overkill for a size-2 array, since the use of a vector introduces the possibility that the size might change.

Answer 4

Not only the vector of two elements is slower, it also looks strange to have a dynamic structure to keep always 2 elements (assuming it is not going to change). I would use struct MyPoint { double x, y; }; for convenience.

Answer 5

std::vector<MyPoint> is faster