Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Does std::array of std::array have contiguous memory?

Seems, that I found how to easily get normal 2D Array with contiguous memory in 2 lines of code:

template<int N, int M>
using Array2D = array<array<int, M>, N>;

Let's solve easy task of swapping min and max in Array2D (a little of c++17):

template<int N, int M>
void printArray2D(const Array2D<N, M> &arr);

int main() {
    const int N = 5;
    const int M = 5;
    Array2D<N, M> arr;

    // random init of Array2D 
    generate(arr.front().begin(), arr.back().end(), []()->int {
                                                        return rand() % 100;
                                                    });

    printArray2D(arr);

    auto[a, b] = minmax_element(arr.front().begin(), arr.back().end());

    cout << "Swap minimum and maximum: " << *a << " " << *b << endl << endl;

    iter_swap(a, b);
    printArray2D(arr);

    return 0;
}

template<int N, int M>
void printArray2D(const Array2D<N, M> &arr) {
    for (const auto &row : arr) {
        for (const auto &elem : row) {
            cout << std::setw(3) << elem;
        }
        cout << endl;
        cout << endl;
    }
}

I got next result in Visual Studio 2017:

 41 67 34  0 69

 24 78 58 62 64

  5 45 81 27 61

 91 95 42 27 36

 91  4  2 53 92

Swap minimum and maximum: 0 95

 41 67 34 95 69

 24 78 58 62 64

  5 45 81 27 61

 91  0 42 27 36

 91  4  2 53 92

Pros:

  • Only 2 simple lines to get 2D array
  • You can normally access elements as arr[2][2]
  • You can use stl algorithms

Cons:

  • This solution doesn't work normally in Debug mode, I've got runtime error array iterators incompatible
  • I don't know if the memory always will be allocated contiguously
  • I don't know if it works in other compilers
  • Magic iterators

Questions:

  • Is contiguous allocation for Array2D ensured by anything?
  • Is it eligible to use array iterators in this way? (different iterators, but bear in mind contiguous and implementation on pointers)
  • Is Array2D safe to use in this manner (as in example) in production code? If not, can you present good code for solving this task with minimum code overhead?
  • geza: This answer contradicts to continuity of nested arrays. Maybe something has changed in C++14?
like image 527
MrPisarik Avatar asked Nov 05 '17 11:11

MrPisarik


1 Answers

According to the standard the memory should be contiguous. The 26.3.7.1 [array.overview] paragraph states (emphasis mine):

The header defines a class template for storing fixed-size sequences of objects. An array is a contiguous container. An instance of array stores N elements of type T, so that size() == N is an invariant.

Update: It appears the implementation might include the padding. More info on the subject in these SO posts:
Is the size of std::array defined by standard?
and specifically this answer:
Is the data in nested std::arrays guaranteed to be contiguous?

like image 180
Ron Avatar answered Nov 10 '22 09:11

Ron