What are the Issues with a vector-of-vectors?

by

For a std::vector the underlying array is dynamically allocated from the heap. If you have e.g. std::vector<std::vector<double>>, then your outer vector would look like

{v1, v2, v3, v4, ... vn}

This looks like each of the inner vectors will be in contiguous memory, and they will, but their underlying arrays will not be contiguous. See the diagram of the memory layout in this post. In other words the you cannot say that

&(v1.back()) + 1 == &(v2.front()) // not necessarily true!

Instead if you used a single vector with striding then you would gain data locality, and it would inherently be more cache friendly as all your data is contiguous.

For the sake of completeness, I would use neither of these methods if your matrix was sparse, as there are more elegant and efficient storage schemes than straight 1D or 2D arrays. Though since you mentioned you have a “fixed 2nd dimension” I will assume that is not the case here.

More Related Contents:

  1. dynamical two dimension array according to input
  2. Vector of Vectors to create matrix
  3. Vector assignment crashing
  4. Get the first column of a matrix represented by a vector of vectors
  5. Print 2-D Array in clockwise expanding spiral from center
  6. Array of vectors
  7. How do I print out the contents of a vector?
  8. Are std::vector elements guaranteed to be contiguous?
  9. How do I sort a std::vector by the values of a different std::vector?
  10. Is it safe to assume that STL vector storage is always contiguous?
  11. Sending and receiving 2D array over MPI
  12. Efficient way of reading a file into an std::vector?
  13. How to use an iterator?
  14. How to initialize std::vector from C-style array?
  15. What is the best way to concatenate two vectors?
  16. Iterating C++ vector from the end to the beginning
  17. Moving elements from std::vector to another one
  18. C++ compile time error: expected identifier before numeric constant
  19. Sorting a std::vector by the string?
  20. c++ Vector, what happens whenever it expands/reallocate on stack?
  21. How to pass a vector of strings to execv
  22. std::vector to string with custom delimiter
  23. How performing multiple matrix multiplications in CUDA?
  24. Inverting a 4×4 matrix
  25. Vector.erase(Iterator) causes bad memory access
  26. Erasing vector::end from vector
  27. Why don’t std::vector’s elements need a default constructor?
  28. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  29. How to erase & delete pointers to objects stored in a vector?
  30. C++ trying to swap values in a vector

Leave a Comment