Как передать двумерный массив в функцию без динамического выделения памяти?

Question

[Drottarutarnum]

Есть двумерный массив, его второй уровень может быть от 0 до 10, а первый неограничен
Сейчас сделано так:

template<typename dataType, size_t dataSize>
size_t GetSize(dataType(&)[dataSize]) { 
	return dataSize; 
}


struct ArrayData {
	int data[10];
	int size;
};


void foo(ArrayData *data, size_t size) {
	for (size_t i = 0; i < size; i++) {
		std::cout << i << ": ";

		for (size_t i2 = 0; i2 < data[i].size; i2++) {
			std::cout << data[i].data[i2] << ", ";
		}

		std::cout << std::endl;
	}
}



int main() {
	ArrayData test[] = {
		{{1, 2, 3}, 3},
		{{1, 2, 3, 4, 5}, 5},
		{{1}, 1},
	};

	foo(test, GetSize(test));

	std::system("pause");
}

Очень неудобно задавать каждому массиву количество элементов, сейчас я сделал это для тестирования, но потом их станет очень много

Можно ли как-то возложить на компилятор эту работу? Или другой способ? Хотелось бы просто писать как-то так:

ArrayData test[] = {
		{1, 2, 3},
		{1, 2, 3, 4, 5},
		{1}
	};

Answer 1

[Mercury13]

Для неизменяемых данных я придумал.

#include <iostream>

template <class T>
struct Array
{
    const size_t size;
    const T* const data;

    const T* begin() const { return data; }
    const T* end() const { return data + size; }

    constexpr Array(const std::initializer_list<T>& x)
        : size(x.size()), data(x.begin()) {}
};

using Row = Array<int>;
using Matrix = Array<Row>;

Matrix mtx = {
  {1, 2, 3 },
  { 10, 20, 30, 40, 50 },
  {},
  { 100 }
};

int main()
{
    for (auto& u : mtx) {
        for (auto& v : u) {
            std::cout << v << ' ';
        }
        std::cout << std::endl;
    }
    return 0;
}

Для изменяемых данных пока вышло только так.

#include <iostream>

// Изменяемый вариант
template <class T>
struct Array2
{
    const size_t size;
    T* const data;

    T* begin() { return data; }
    T* end() { return data + size; }
    const T* begin() const { return data; }
    const T* end() const { return data + size; }
    T& operator[](int i) { return data[i]; }

    template <size_t N>
    constexpr Array2(T (&x)[N])
        : size(N), data(x) {}
};

using Row2 = Array2<int>;
using Matrix2 = Array2<Row2>;

int main()
{
    int i;
    std::cin >> i;

    int row1[] = { 1, i, 3 };
    int row2[] = { 10, 2*i, 30, 3*i, 50 };
    int row3[] = { 13 };
    int row4[] = { 100 };

    Row2 mtx[] = { row1, row2, row3, row4 };

    mtx[1][4] = i * 6;

    for (auto& u : mtx) {
        for (auto& v : u) {
            std::cout << v << ' ';
        }
        std::cout << std::endl;
    }
    return 0;
}

Comments

[Vitaly]

Ваш вариант явно проще, чем мой :)

[Mercury13]

И ещё одно решение.

// Изменяемый вариант, ограниченный длиной 10
// (начиная с Си++14 без копирования!!)
template <class T>
struct Array3
{
    unsigned size = 0;
    T data[10];

    T* begin() { return data; }
    T* end() { return data + size; }
    const T* begin() const { return data; }
    const T* end() const { return data + size; }
    T& operator[](int i) { return data[i]; }

    Array3() {}
    constexpr Array3(const std::initializer_list<T>& x)
        : size(x.size()) { std::copy(x.begin(), x.end(), data); }
};

using Row3 = Array3<int>;
using Matrix3 = Array3<Row3>;


int main()
{
    int i;
    std::cin >> i;

    Matrix3 mtx = {
        { 1, i, 3 },
        { 10, 2*i, 30, 3*i, 50 },
        { 13 },
        { 100 }
    };

    mtx[1][4] = i * 6;

    for (auto& u : mtx) {
        for (auto& v : u) {
            std::cout << v << ' ';
        }
        std::cout << std::endl;
    }
    return 0;
}

[Евгений Шатунов]

Mercury13,

constexpr Array(const std::initializer_list<T>& x)
        : size(x.size()), data(x.begin()) {}

Подход капельку разбивается о специфику листа инициализации.
До C++14:

The underlying array is not guaranteed to exist after the lifetime of the original initializer list object has ended. The storage for std::initializer_list is unspecified (i.e. it could be automatic, temporary, or static read-only memory, depending on the situation).

Начиная с C++14:

The underlying array is a temporary array of type const T[N], in which each element is copy-initialized (except that narrowing conversions are invalid) from the corresponding element of the original initializer list. The lifetime of the underlying array is the same as any other temporary object, except that initializing an initializer_list object from the array extends the lifetime of the array exactly like binding a reference to a temporary (with the same exceptions, such as for initializing a non-static class member). The underlying array may be allocated in read-only memory.

[Mercury13]

Евгений Шатунов, Жаль. Получается, код компиляторозависим.
Думаю, в следующих редакциях «си с крестами» ужесточат требования к i_l.

По крайней мере третий вариант ни на каком диком компиляторе не откажет.
UPD. И второй тоже.

[Евгений Шатунов]

Mercury13, второй довольно тяжел в использовании, на деле он плохо поддается рефакторингу. :)
А третий - да, он и правда самый надежный и пригодный для работы. Там только ассертнуться не помешает на случай превышения допустимого размера массива. Или копирование ограничить как-нибудь так:

std::copy( x.begin(), std::next( x.begin(), std::max( std::size( data ), x.size() ) ), data );

Answer 2

[res2001]

Можно ли как-то возложить на компилятор эту работу?

int arr[] = {1, 2, 3};
size_t size = sizeof(arr)/sizeof(arr[0]);  // size == 3

Но как вы это прикрутите к вашей схеме не знаю.
Возможно есть смысл определить ваши массивы как константы по одному и использовать эти константы для инициализации test и вычисления sizeof().

Comments

[Евгений Шатунов]

res2001
int arr = {1, 2, 3}; - это будет компилироваться, как думаешь?

Но даже если предположить, что ты имел в виду int arr[] = {1, 2, 3};, то точно ли 3 вернет операция sizeof(arr)? Я так не думаю.

[res2001]

Евгений Шатунов, Спасибо за замечание, поправил ответ.

Answer 3

[vanyamba-electronics]

Нужно просто освоить std::vector:

#include <vector>

using namespace std;

void foo(vector<ArrayData>& data)
{
    for (vector<ArrayData>::iterator it = data.begin(); it != data.end(); ++it)
        cout << it->data[0] << " ";
    cout << endl;
}

int main() {
   vector<ArrayData> test;
   ArrayData data0 = {{1, 2, 3}, 3};

   test.push_back(data0);
   foo(test);
}

Comments

[Mercury13]

Ответ не решает задачу, вектор под капотом выделяет память.

[vanyamba-electronics]

Mercury13, в функцию передаётся ссылка, то есть указатель. Копирование массива при этом не происходит.

[Mercury13]

vanyamba-electronics, Когда будет создан vector из пользовательских данных, он УЖЕ выделяет память.
В строчке test.push_back(data0);.

[vanyamba-electronics]

Mercury13, чтобы хранить данные, используется память. Так работает компьютер.

[Mercury13]

vanyamba-electronics, Имеется в виду другое. Он хочет, чтобы таблица влинковывалась в сегмент данных, и при развёртывании её в памяти проводилось максимум переливание инфы, но не выделение динамической памяти.

[Mercury13]

И ещё одно, чем это решение не годится,— строкой ArrayData data0 = {{1, 2, 3}, 3};. Он хотел избавиться от этой длины!

[vanyamba-electronics]

Mercury13, операционная система может переместить страницу кодового сегмента в другую область память, и указатель станет невалидным, а код будет работать, потому что при компиляции указатели в коде - это смещения относительно текущего значения регистра PC.

[Mercury13]

vanyamba-electronics, Во-первых, этот регистр называется не PC, а IP (соответственно EIP, RIP).
Во-вторых, какого текущего, это счётчик команд, он постоянно меняется!
Во-третьих, то, что вы описали, действует только для коротких переходов (jz и т.д.) — для упрощения линковки и уменьшения количества relocations.
Для общей работы программы независимо от других используется «плоская» модель памяти, виртуальная память и защищённый режим. Это тоже аппаратно-программный механизм, я с ним толком не знаком, т.к. не лез в дебри ОС.
Для загрузки исполняемого модуля по тому или иному адресу — т.н. relocations, специальный блок, позволяющий подправить адреса, если модуль загрузили не в тот адрес, под который его слинковали.

[Mercury13]

vanyamba-electronics, В схеме с виртуальной памятью логические адреса (доступные пользовательской программе) не меняются, как бы ни работала система подкачки!
Но, извините, топикстартеру не нужны такие дебри. Поняли задачу: таблица будет большая, и он хочет влинковать её в сегмент данных, без выделения динамической памяти через malloc/new.

[vanyamba-electronics]

Mercury13, да что тут непонятного, просто это не к C++ вопрос, а к компилятору. Простейший способ - вставить эти данные как ассемблерную вставку. Некоторые компиляторы позволяют задать атрибут константе, в каком сегменте она должна быть размещена.

[Mercury13]

vanyamba-electronics, Вопрос даже не в том, чтобы передать данные. Задача — добавить автоматики при компиляции.

[Mercury13]

vanyamba-electronics, Простите за немного устаревшие знания, но в x64 действительно есть режим «RIP relative». Он совсем не упрощает линковку, несколько уменьшает количество relocations, и служит в первую очередь для сжатия кода: сами адреса 64-битные, а смещения зачастую 32-битные.

Answer 4

[Vitaly]

Да есть. В C++ есть стандартная библиотека, в которой есть некоторые структуры данных:

#include <vector>

template <class T>
using Matrix = std::vector<std::vector<T>>;

// ... 

template <class T>
void print(const Matrix<T> &matrix)
{
    for (auto &&r : matrix) {
        for (auto &&e : r) {
            std::cout << e << " ";
        }
        std::cout << std::endl;
    }
} 

// ...

Matrix<int> m = {
    {1, 2, 3},
    {5, 6, 7, 8},
    {9, 10}
}

print(m);

Вот тут можно прочитать о классе vector: https://en.cppreference.com/w/cpp/container/vector

PS
Я это всё не компилировал, но как-то так в общем должно работать.

Comments

[Mercury13]

Ответ не решает задачу, вектор «под капотом» выделяет память.

[Vitaly]

Mercury13, Ну на std::array можно переписать... На стеке сильно много не выделишь всё равно.

[Евгений Шатунов]

Vitaly, а предложи, пожалуйста, код на основе std::array, который позволил бы инициализацию произвольной длины для объекта этого типа.
Автору нужно именно это.

[Vitaly]

Евгений Шатунов, Да я бы и рад, но там скорее всего просто не получится. Либо через variant, либо через что-то экспериментальное вроде этого:

decltype (auto) m = std::make_tuple(
        std::experimental::make_array(1, 2, 3),
        std::experimental::make_array(1, 2),
        std::experimental::make_array(1, 2, 3, 56)
    );

Надо в общем попробовать.

[Vitaly]

Евгений Шатунов, Ну в общем, то что выше работает, я проверил, а печатать так можно:

template <class T>
void print(const T &m)
{
    std::apply([](auto &&... r){
        ((std::copy(r.begin(), r.end(), std::ostream_iterator<int>(std::cout, " ")), std::cout << std::endl), ...);
    }, m);
}

Ну и обходить тоже. В принципе, все функции вроде make_tuple/make_array можно и самому написать. Так что вариант рабочий.

[Евгений Шатунов]

Vitaly, да, такой механизм работает. Только еще остается условие, что эту конструкцию требуется передать в качестве аргумента функции.
Я понимаю что можно сделать обобщенную функцию с выводимым параметром. Но представь, что свою конструкцию ты передаешь в подсистему, где она будет блуждать по самым странным маршрутам.

[Vitaly]

Евгений Шатунов, Да, это не самый простой код, тут согласен. Там ниже вроде бы есть вариант проще.