Multi-Dimensional Vector

Multidimensional Vectors in C++

If you are able to use C++11, multidimensional arrays and vectors of vectors can be initialized in a similar manner.

int a1[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
std::vector<std::vector<int>> a2 = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };

However, there are differences that must be understood to access the elements without running into undefined behavior.

For a multidimensional array, memory for the elements of the array is required to be allocated contiguously. For a vector of vector, the memory for the elements is most likely going to be disjoint.

Memory for a1:

a1[0][0]    a1[1][0]    a1[2][0]
|           |           |
v           v           v
+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

Memory for a2 (most likely):

a2[0][0]
|
v
+---+---+---+
|   |   |   |
+---+---+---+

a2[1][0]
|
v
+---+---+---+
|   |   |   |
+---+---+---+

a2[2][0]
|
v
+---+---+---+
|   |   |   |
+---+---+---+

Also, it is possible to defined a vector of vectors in which the number of columns is not same for each row.

std::vector<std::vector<int>> a2 = { {1, 2, 3}, {4, 5}, {6, 7, 8, 9} };

In a multidimensional array, the number of columns is guaranteed to be same for each row.

Given the above multidimensional array a1, a1[1][2] will be a valid element and a1[2][3] will be an invalid element. In the case of a vector of vectors, using the above line, a2[1][2] is not a valid element and a2[2][3] is a valid element.

C++: generate multidimensional vector of unknown depth

Here is a solution using a template MultiVector class that returns a MultiVectorView from it's operator[].

The underlying data is stored in a plain std::vector but can be accessed with the vec[x][y][z] syntax.

There is no checking for correct usage, and only very basic functionality is implemented but it gives an idea how it could be done.

#include <iostream>
#include <vector>

template <typename T>
class MultiVector;

template <typename T>
class MultiVectorView {
public:
    MultiVectorView(MultiVector<T>& vec_, int index_, int dimension_) : vec(vec_), index(index_), dimension(dimension_) {}

    MultiVector<T>& vec;
    int index;
    int dimension;

    MultiVectorView& operator[](std::size_t n_index) {
        int index_multiplyer = 1;
        for (int i=0; i<dimension; ++i)
            index_multiplyer *= vec.dimensions[i];
        index += n_index*index_multiplyer;
        dimension++;
        return *this;
    }

    operator T() {
        return vec.content[index];
    }

    MultiVectorView& operator=(T val) {
        vec.content[index] = val;
        return *this;
    }
};

template <typename T>
class MultiVector {
public:
    MultiVector(std::vector<int> dimensions_) : dimensions(dimensions_) {
        int size = dimensions[0];
        for (int i = 1; i<dimensions.size(); ++i)
            size *= dimensions[i];

        content.resize(size);
    }

    MultiVectorView<T> operator[](std::size_t index) {
        return MultiVectorView<T>(*this, index, 1);
    }

    std::vector<T> content;
    std::vector<int> dimensions;
};

int main() {
    std::vector<int> v = {2,3,2};
    MultiVector<int> test(v);

    int tmp = 0;
    for (int x = 0; x < v[0]; ++x)
        for (int y = 0; y < v[1]; ++y)
            for (int z = 0; z < v[2]; ++z) {
                test[x][y][z] = tmp++;
            }

    for (int i=0; i<test.content.size(); ++i)
        std::cout << std::endl << test.content[i] << " ";

    int b = test[1][2][1];

    std::cout << std::endl << "b = " << b << std::endl << "test[0][1][1] = " << test[0][1][1] << std::endl;
}

How does C++ create different vectors in two dimensional vector initialization?

From the constructor reference

3) Constructs the container with count copies of elements with value value.

There are no references to tmp, just copies. All the individual vectors are distinct, and modifying one won't modify any of the others.

How to reserve a multi-dimensional Vector without increasing the vector size?

If your data is guaranteed to be N x 4, you do not want to use a std::vector<std::vector<int>>, but rather something like std::vector<std::array<int, 4>>.

Why?

• It's the more semantically-accurate type - std::array is designed for fixed-width contiguous sequences of data. (It also opens up the potential for more performance optimizations by the compiler, although that depends on exactly what it is that you're writing.)
• Your data will be laid out contiguously in memory, rather than every one of the different vectors allocating potentially disparate heap locations.

Having said that - @pasbi's answer is correct: You can use std::vector::reserve() to allocate space for your outer vector before inserting any actual elements (both for vectors-of-vectors and for vectors-of-arrays). Also, later on, you can use the std::vector::shrink_to_fit() method if you ended up inserting a lot less than you had planned.

Finally, one other option is to use a gsl::multispan and pre-allocate memory for it (GSL is the C++ Core Guidelines Support Library).

Initialize c++ multi dimensional vector with multi dimensional array?

The problem of doing this is a memory layout: two dimensional C array [4][4] is located in memory as 16 (4*4) floats like float[16] array. But vector of vector located in other way: it is more similar like float** dynamic array and every element of type float* is allocated separately. It means you cannot just pass a pointer of your two dimensional array and be good. But you can use STL algorithms.

First of all std::vector and plain C array both are STL compatible. Let's say you need initialize std::vector with one dimentional C array. I must write something like this:

float testArray[4]={0.99962944, -0.023989394, -0.012864082, -0.032067116};
vector<float> testVector(testArray,testArray+4);

It will construct a new vector and iterate from testArray (it's a pointer) to testArray+4 (it's a pointer too) and push_back every element into testVector. So the easiest way to achieve what you want is:

vector<vector<float>> floatVector{
    {viewerMatrix[0],viewerMatrix[0]+4},
    {viewerMatrix[1],viewerMatrix[1]+4},
    {viewerMatrix[2],viewerMatrix[2]+4},
    {viewerMatrix[3],viewerMatrix[3]+4},
};

Of course 4 value in dimensions can be changed so it is better to create a function that takes a two dimensional array of any number of elements and returns std::vector<std::vector<float>>. For example:

template<size_t M,size_t N>
std::vector<std::vector<float>> initVectorWithTwoDimArray(float (&ar)[M][N]){
    std::vector<std::vector<float>> res;
    res.reserve(M);
    for(auto i=0;i<M;++i){
        res.emplace_back(ar[i],ar[i]+N);
    }
    return std::move(res);
}

float viewerMatrix[4][4] =
{
    {0.99962944, -0.023989394, -0.012864082, -0.032067116},
    {0.02354476, 0.9991557, -0.033667795, -0.0060634422},
    {0.013660891, 0.033352438, 0.99935031, 0.047027141},
    {   0, 0, 0, 1}
};

auto floatVector=initVectorWithTwoDimArray(viewerMatrix);

Now floatVector is std::vector of std::vector<float> contained your two dim array.

Edit

If you like this function it can be recreated with array of any type not just float:

template<class T,size_t M,size_t N>
std::vector<std::vector<T>> initVectorWithTwoDimArray(T (&ar)[M][N]){
    std::vector<std::vector<T>> res;
    res.reserve(M);
    for(auto i=0;i<M;++i){
        res.emplace_back(ar[i],ar[i]+N);
    }
    return std::move(res);
}

This version will work for any type of arrays: int, double, AnyYourClass etc. Usage is the same:

float viewerMatrix[4][4] =
{
    {0.99962944, -0.023989394, -0.012864082, -0.032067116},
    {0.02354476, 0.9991557, -0.033667795, -0.0060634422},
    {0.013660891, 0.033352438, 0.99935031, 0.047027141},
    {   0, 0, 0, 1}
};

auto floatVector=initVectorWithTwoDimArray(viewerMatrix);

How to sum all the elements of a multi-dimensional std::vector?

This can be done without any template meta programming. You can let the compiler infer the type using auto and decltype:

template <class T>
T Sum(const T x) {
    return x;
}

template <class T>
auto Sum(const std::vector<T> &v) {
    decltype(Sum(v[0])) sum = 0;
    for (const auto &x : v)
        sum += Sum(x);
    return sum;
}

The return type of Sum is automatically deduced from sum and the type of sum is whatever Sum(v[0]) returns. Eventually you will end up with the first version of Sum which returns T and the compiler knows that type.

Demo

C++ - How are multi-dimensional vectors stored?

how much information (or which information) about the vector is stored in the address &A

You are correct in assuming that the data for the vector is stored separately from the vector object itself - typically, in dynamic memory.

The three things the vector object itself needs to know are

• The location of the vector's data - we need this to perform the [] operator,
• The size currently allocated - we need this to know when to grow the array, and
• The number of elements actually placed into the vector - we need this to know where to push_back, and what to return from size().

Different implementations are possible, storing as little as a single pointer in the vector object itself. However, a typical implementation stores a pointer to the beginning of the allocated block, a pointer to the end of the active part of the allocated block, and a pointer to the end of the allocated block.

---

Related Topics