Я недавно решил закодить одну задачу, а т.к. я уже отучился от привычки использовать глобальные массивы с фиксированным размером, пришлось нагородить вот такую некрасивую штуку: 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;
}
}
This is pretty cool idea, but I'd suggest that you make support for default values with syntax like this:
Also in C++14, you can simplify your current implementation quite a bit:
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)."... since C++ won't allow you to call it as
create_vec<int>(n, m)"I think it will.
Sorry, I was confused about that due to some reason.
Вложенные три раза вектора работают при этом значительно медленнее трехмерных массивов. Если не нравится использовать глобальные массивы, а все размеры ограничены, то лучше пользоваться array.
Можно пойти дальше и написать структуру, которая ведёт себя именно так, как структура из поста, но устроена как одномерный
std::vector<T>, а выражение[x1][x2][x3]развернётся в соответствующий одномерный индекс в этом векторе. Для этого, видимо, понадобится завести дополнительные k - 1 прокси-типов (где k — размерность вектора), обозначающих срез вектора по первым 1, 2, ..., k - 1 координатам. Работать будет явно быстрее.Не думаю, что быстрее, чем array, скорее всего также
Быстрее, чем авторская реализация. Преимущество перед array в том, что размеры не обязательно должны быть известны на стадии компиляции (но количество измерений надо знать). Так-то array, как и глобальный многомерный массив, конечно, побыстрее будут.
Я попробовал написать такую структуру. Судя по выводу дизассемблера, 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. Погоняйте кто-нибудь бенчмарки, пожалуйста...
Только эти самые array'и не умеют менять размер:(
Речь идет о скорости создания или доступа? Можно уточнить, почему vector<vector<vector>> будет существенно медленнее T[][][]?
Upd. А, кажется, понял, речь идет о массивах фиксированного во время компиляции размера.
Как раз-таки мне хотелось решить задачу создания удобного в использовании многомерного массива, размерности которого задаются во время выполнения.
Речь идет о скорости доступа.
Смотрите: у нас есть глобальный массив, допустим,
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). Это значит, что мы:pлокальной переменнойarr.pвектораarr[i], лежащего где-то на куче.pвектораarr[i][j], лежащего тоже где-то на куче.arr[i][j][k].Итого четыре обращения к памяти вместо одного.
Но: если итерироваться по всему нашему массиву в порядке возрастания индексов, то все четыре обращения к памяти практически всегда будут попадать в L1-кэш. Если доступ будет случайный, то да, все уже не так радужно (хотя оно и при хранении всего массива в виде одного куска данных тоже будет не очень хорошо).
Короче говоря, в олимпиадном программировании если не хочется пользоваться глобальными массивами — юзайте вложенные векторы с реализацией от Jacob'а из комментария к этому посту (или от меня, если компилятор не поддерживает C++14) и не парьтесь.
У кого-нибудь хватит смелости сделать GUI-библиотеку на шаблонах C++14?