Блог пользователя AlexanderBolshakov

Создание многомерного std::vector с использованием Variadic Templates из C++11
Автор AlexanderBolshakov, история, 8 лет назад, По-русски

Я недавно решил закодить одну задачу, а т.к. я уже отучился от привычки использовать глобальные массивы с фиксированным размером, пришлось нагородить вот такую некрасивую штуку: vector<vector<vector<char>>> visited(n, vector<vector<char>>(n, vector<char>(n, false)));. Потом я вспомнил, что в современном C++ ничто не мешает сделать создание подобных векторов заметно более удобным, поэтому я реализовал вот это:

#include <vector>
#include <iostream>

template<typename T, size_t nDimensions>
struct VectorType
{
	typedef std::vector<typename VectorType<T, nDimensions - 1>::Type> Type;
};

template<typename T>
struct VectorType<T, 0>
{
	typedef T Type;
};

template<typename T>
struct MVector
{
	static typename VectorType<T, 0>::Type create();

	template<typename SizeType, typename... SizeTypes>
	static typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type create(SizeType sz, SizeTypes... sizes);
};

template<typename T>
typename VectorType<T, 0>::Type MVector<T>::create()
{
	return typename VectorType<T, 0>::Type();
}


template<typename T>
template<typename SizeType, typename... SizeTypes>
typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type MVector<T>::create(SizeType sz, SizeTypes... sizes)
{
	return typename VectorType<T, 1 + sizeof...(SizeTypes)>::Type(sz, create(sizes...));
}


int main()
{
	int n, m;
	std::cin >> n >> m;

	auto matrix = MVector<int>::create(n, m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cin >> matrix[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			std::cout << matrix[i][j] << " ";
		}
		std::cout << std::endl;
	}
}
  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

This is pretty cool idea, but I'd suggest that you make support for default values with syntax like this:

MVector<int>(-1).create(n, m)

Also in C++14, you can simplify your current implementation quite a bit:

template<typename T>
T create_vec()
{
	return T();
}


template<typename T, class SizeT, class ...SizeTs>
auto create_vec(SizeT sz, SizeTs... sizes)
{
	return vector<decltype(create_vec<T>(sizes...))>(sz, create_vec<T>(sizes...));
}
→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Yes, addition of default value was the most obvious improvement for my implementation (I thought that those who are really interested in my idea will implement this as an exercise even without being asked to do so).

    Return type deduction is really great in this case, thank you for this idea. But you still can't replace a member function with an ordinary function, since C++ won't allow you to call it as create_vec<int>(n, m).

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Вложенные три раза вектора работают при этом значительно медленнее трехмерных массивов. Если не нравится использовать глобальные массивы, а все размеры ограничены, то лучше пользоваться array.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Можно пойти дальше и написать структуру, которая ведёт себя именно так, как структура из поста, но устроена как одномерный std::vector<T>, а выражение [x1][x2][x3] развернётся в соответствующий одномерный индекс в этом векторе. Для этого, видимо, понадобится завести дополнительные k - 1 прокси-типов (где k — размерность вектора), обозначающих срез вектора по первым 1, 2, ..., k - 1 координатам. Работать будет явно быстрее.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Не думаю, что быстрее, чем array, скорее всего также

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Быстрее, чем авторская реализация. Преимущество перед array в том, что размеры не обязательно должны быть известны на стадии компиляции (но количество измерений надо знать). Так-то array, как и глобальный многомерный массив, конечно, побыстрее будут.

        → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Я попробовал написать такую структуру. Судя по выводу дизассемблера, VS2015 корректно оптимизирует мой код matrix[i][j] до matrix.data[i * matrix.MArray<T, 2>::elementSize + j], но вот то, что i * matrix.MArray<T, 2>::elementSize на одной итерации цикла по i есть константное выражение, компилятор почему-то не понимает. Причем, компилятор настолько тупой, что до него это не доходит даже если явно выставить для поля elementSize спецификатор const.

      P.S. std::enable_if в конструктор MArray я вставил для того, чтобы компилятор выдавал чуть более внятное сообщение об ошибке при передаче в конструктор неправильного количества аргументов.

      P.P.S. Погоняйте кто-нибудь бенчмарки, пожалуйста...

      → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Только эти самые array'и не умеют менять размер:(

    → Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Речь идет о скорости создания или доступа? Можно уточнить, почему vector<vector<vector>> будет существенно медленнее T[][][]?

    Upd. А, кажется, понял, речь идет о массивах фиксированного во время компиляции размера.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      Как раз-таки мне хотелось решить задачу создания удобного в использовании многомерного массива, размерности которого задаются во время выполнения.

      Речь идет о скорости создания или доступа? Можно уточнить, почему vector<vector> будет существенно медленнее T[][][]?

      Речь идет о скорости доступа.

      Смотрите: у нас есть глобальный массив, допустим, int arr[sz1][sz2][sz3];, где все три его размерности — величины, известные во время компиляции. Такой массив размещается в DATA-секции исполняемого файла (по крайней мере, так она называется в формате бинарных файлов COFF, используемом в Windows), и сам указатель на начало такого массива — это тоже значение, известное во время компиляции. Давайте же мы обратимся к элементу arr[i][j][k], где i, j и k становятся известны только во время выполнения. Это будет выглядеть так: *(_arr + i * _sz2 * _sz3 + j * _sz3 + k), где перед всеми известными во время компиляции значениями я поставил знак подчеркивания. В идеальном случае переменные i, j, k будут находиться в регистрах процессора, итого этот код будет производить ровно одно обращение к памяти.

      Теперь давайте посмотрим на такое же обращение к arr[i][j][k] для vector<vector<vector<int>>> arr;. Будем считать, что объект типа vector хранит указатель p на реальный массив, находящийся на куче. Итого: *(((arr.p + i)->p + j)->p + k). Это значит, что мы:

      1. Обращаемся к полю p локальной переменной arr.
      2. Обращаемся к полю p вектора arr[i], лежащего где-то на куче.
      3. Обращаемся к полю p вектора arr[i][j], лежащего тоже где-то на куче.
      4. Наконец-то добираемся до значения arr[i][j][k].

      Итого четыре обращения к памяти вместо одного.

      Но: если итерироваться по всему нашему массиву в порядке возрастания индексов, то все четыре обращения к памяти практически всегда будут попадать в L1-кэш. Если доступ будет случайный, то да, все уже не так радужно (хотя оно и при хранении всего массива в виде одного куска данных тоже будет не очень хорошо).

      Короче говоря, в олимпиадном программировании если не хочется пользоваться глобальными массивами — юзайте вложенные векторы с реализацией от Jacob'а из комментария к этому посту (или от меня, если компилятор не поддерживает C++14) и не парьтесь.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

У кого-нибудь хватит смелости сделать GUI-библиотеку на шаблонах C++14?

→ Ответить