2

I recently learned how to do two- and three-dimensional arrays in plain C using pointers, however being a C++ enthusiast, I'd also like to figure out how to do multi-dimensional arrays in C++.

I know that the preferred way of doing one-dimensional arrays in C++ is to use std::vector<T>, but what about two- and three-dimensional arrays? Would they be represented as std::vector<std::vector<T>> and std::vector<std::vector<std::vector<T>>>?

bodacydo
  • 75,521
  • 93
  • 229
  • 319
  • 4
    Sure you can do that. But IMHO using a 1D vector with [proper indexing](http://en.wikipedia.org/wiki/Row-major_order) (e.g., column major or row major order) is more sufficient. – 101010 Jul 23 '14 at 20:20
  • Yes. This is an array of arrays, so a 2D array. And you could do a 3D array the same way. – Shlublu Jul 23 '14 at 20:22
  • That is one way to do it, but it has the significant drawback that, unlike a normal 2D array, each row is not constrained to be the same length. Another way to do it would be to write a class that internally uses a 1D vector, overloads array operators (mainly just `[]`), and handles get/set operations with row- or column-major ordering. – Parthian Shot Jul 23 '14 at 20:23
  • 1
    I would risk great wrath in suggesting the preferred method of array representation is arguably `std::array<>` unless you *need* heap-storage and/or dynamic sizing. Regardless, yes a vector of vectors (of vectors...) will "work". – WhozCraig Jul 23 '14 at 20:23
  • Another possible drawback is that the elements are not contiguous. This may make interfacing to libraries that use single blocks of data for multi-dimensional arrays difficult. – juanchopanza Jul 23 '14 at 20:26

3 Answers3

3

While you can technically do that, it is a better idea to use a single std::vector<T> and calculate the offsets by hand. The resulting memory layout will be much more cache-friendly, since everything will be tightly packed together and can be traversed sequentially or indexed with no indirection.

However, if C++11 is an option and the size of your array is fixed at compile-time, you should use nested std::arrays. Dynamic allocation can be easily achieved with std::unique_ptr. Note however that the data won't necessarily be strictly contiguous between sub-arrays, which could be a problem when interfacing with API's expecting a single ol' block of data.

Quentin
  • 62,093
  • 7
  • 131
  • 191
  • 3
    Note that an `std::array` of `std::array` is not guaranteed to have all elements contiguous. So a single `std::array` with clever indexing would be a better option. – juanchopanza Jul 23 '14 at 20:27
  • @juanchopanza True, but even though the `std::array` headers (size and so on) will get squeezed in-between data, the difference won't even be noticeable, expecially compared to the cost of a cache miss on each element from nested `std::vector`s. And with nested `std::array`s you get neat `operator[]`s straight out of the box. – Quentin Jul 23 '14 at 20:31
  • 1
    There's no need for data members like size, but there could be some padding, and the standard allows for extra space at the end. But the issue is that the elements aren't contiguous like they are in a plain C-style 2D array, and this has implications if you need to use, say, high performance linear algebra libraries that expect a single block of data. – juanchopanza Jul 23 '14 at 20:34
  • @juanchopanza of course there's no size member, it's a template parameter... one "duh" moment for me. The external library argument holds, I'm adding it up there. – Quentin Jul 23 '14 at 20:36
  • I do not see how nested `std::array`s will ever look any different than multidimensional native arrays memory layout wise. Can someone give an example of that mysterious padding actually manifesting? I thought `std::array` was specifically made to work with API's expecting a continuous block of memory. – nwp Jul 23 '14 at 20:46
  • @nwp well, it's just [next door](http://stackoverflow.com/a/9762712/3233393). But as said answer states, it would ba a bit weird to implement `std::array`with padding, but still standard-compliant. That's in such cases that I usually trust the implementation not to do weird things, and drop in a `static_assert()` to be warned if it ever changes. – Quentin Jul 23 '14 at 20:52
2

Of course you may use class std::vector to simulate arrays. For example

#include <iostream>
#include <vector>

int main() 
{
    size_t n;
    size_t m;

    std::cout << "Enter the number of rows: ";
    std::cin >> n;

    std::cout << "Enter the number of columns: ";
    std::cin >> m;

    std::vector<std::vector<int>> v( n, std::vector<int>( m ) );

    return 0;
}

Also consider using of the combination of std::vector with std::array when the number of columns is a compile time constant.

A definition of so-called 3-dimensional array can look as for example

std::vector<std::vector<std::vector<int>>> 
    v( 2, std::vector<std::vector<int>>( 3, std::vector<int>( 4 ) ) );

A more interesting example

#include <iostream>
#include <vector>
#include <numeric>

int main() 
{
    size_t n;
    size_t m;

    std::cout << "Enter the number of rows: ";
    std::cin >> n;

    std::cout << "Enter the number of columns: ";
    std::cin >> m;

    std::vector<std::vector<int>> v( n, std::vector<int>( m ) );

    for ( size_t i = 0; i < n; i++ )
    {
        std::iota( v[i].begin(), v[i].end(), i * m );
    }

    for ( const auto &v1 : v )
    {
        for ( auto x : v1 ) std::cout << x << ' ';
        std::cout << std::endl;
    }

    return 0;
}

If to enter 3 and 5 correspondingly for n and m then the output will be

0 1 2 3 4 
5 6 7 8 9 
10 11 12 13 14
Vlad from Moscow
  • 301,070
  • 26
  • 186
  • 335
1

Sure!

#include <vector>
#include <iostream>

int main()
{
    typedef std::vector<double> VD;
    typedef std::vector<VD>    VVD;

    // 10x5 matrix filled with ones
    VVD mtx(10, VD(5, 1));

    std::cout << mtx.size() << " " << mtx[0].size() << std::endl;
    std::cout << mtx[3][2] << std::endl;


    return 0;
}
Kknd
  • 3,033
  • 26
  • 29