13

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?
MrPisarik
  • 1,260
  • 1
  • 11
  • 21
  • 12
    The memory would be contiguous, but in `generate(arr.front().begin(), arr.back().end()` you are using iterators into two different containers and *that* is not allowed. – Bo Persson Nov 05 '17 at 11:29
  • 4
    You are definitely not allowed to treat this as a continuous array of ints, but I'm pretty sure continuous memory layout is guaranteed. – MikeMB Nov 05 '17 at 11:33
  • @BoPersson, Yes, it is wrong in conception of iterators, but an `_Array_iterator` works over pointers, so it seems that this code unacceptable only because of iterator conception? – MrPisarik Nov 05 '17 at 11:44
  • 2
    The memory is *contiguous* but the elements are not required to be (because of padding) so mixing iterators from different array elements is undefined behavior (as would be using the actual pointers). – Galik Nov 05 '17 at 12:46
  • Possible duplicate of [Is the data in nested std::arrays guaranteed to be contiguous?](https://stackoverflow.com/questions/9762662/is-the-data-in-nested-stdarrays-guaranteed-to-be-contiguous) – Toby Speight Nov 06 '17 at 11:49

1 Answers1

4

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?

Ron
  • 14,674
  • 4
  • 34
  • 47
  • Ha, so simple.. `array` contiguously places N blocks of contiguous `array` of M elements, but for some reasons I was scaried to think that Array2D will be contiguous. Thank you. The question about iterators left – MrPisarik Nov 05 '17 at 11:48
  • 1
    @MrPisarik: This [answer](https://stackoverflow.com/a/9762712/8157187) contradicts. Maybe something has changed in C++14? – geza Nov 05 '17 at 12:06
  • @geza If every element in an array is contiguous then every array in an array is placed next to each other. The standard is pretty clear on this one. – Ron Nov 05 '17 at 12:18
  • 1
    @Ron: It is guaranteed, if there is no padding at the end of an `std::array`. I don't know what the standard says about this. But I bet a sane implementation would not do any padding there (but the possibility still there, if the standard doesn't prohibit this). – geza Nov 05 '17 at 12:19
  • 2
    The problem is that each *individual* array has contiguous content but the gaps *between* different `std::array` elements are undefined. So the *contiguity* of an *array of array* is "lumpy" at best. – Galik Nov 05 '17 at 12:50
  • 2
    @geza A `std::array` can have padding at the end. – Galik Nov 05 '17 at 12:51