Динамический прямоугольный массив в Си++

Что значит динамический? Просто с изменяемым размером? Или разреженный?

В STL многие более подходящие вещи с большим скрипом добавляют, что уж говорить о такой мелкой фишечке.

Во-первых, двумерный массив всегда можно развернуть в одномерный. Во-вторых, всегда есть int** rectarray. Красивую обёртку можно всегда самому за 10 минут написать.

Развернуть-то можно, но насколько им потом неудобно пользоваться?
У меня просто array[x][y]=z. А что мне делать с линейным?
Я лучше помучаюсь с определением, а потом буду удобно пользоваться, чем долго мучиться с простым определением.

Сплошной (если я правильно понял, о чём ты). Просто да, с изменяемым размером. Строки одинаковой длины и столбцы тоже одинаковы, хотя и могут отличаться от строк. В общем прямоугольный, а не квадратный и сплошной.

Длины всех строк одинаковы? Если одинаковы, то кто мешает использовать vector размера m * n и обращаться к элементам как a[i * m + j]?

А так для таких придумали Boost Multiarray.

обращаться к элементам как a[i * m + j]

Самому-то не смешно? Или у тебя поломалось чувство прекрасного?
Сравни с array[x][y]=z.

Еще у Страуструпа в 29-й главе (в 4-м издании) разбирается создание шаблона класса для n-мерных массивов с вектором внутри.

Удобство пользования зависит от того во что ты его завернёшь. В мире ООП принято над стандартными безликими сущностями создавать обёртки, которые подходят под конкретный контекст.

Создать класс Stahl::rectarray<int, int, bool>, внутри вместо array[x][y] у тебя будет какой-нибудь array[x*N + y], а снаружи какой-нибудь get(x, y).

Да это понятно. Мне просто показалось, что моя хотелка настолько банальна и очевидна, что я удивился почему она до сих пор не в стандарте.

Потому что это слишком уж мелкая хотелка. В загромождении стандарта тоже ничего хорошего нет.

Комфорт строится из мелочей:)
Вот когда будет у меня пьяное состояние, напишу письмо в соответствующую организацию:)

Кстати, по поводу (свежего) стандарта: почему ты используешь map, а не uordered_map в своем примере?

Я пока не осилил новый стандарт. Я пока даже плюшками из 11 стандарта пользуюсь очень мало. Привычки меняются медленно. Со временем само придёт.

А чем плох обычный двухмерный массив в духе С, выделяемый через new ?

Я ударение делаю на удобство и красоту. Сишный массив по этим критериям не катит.

Я к тому, что обычным map лучше вообще не пользоваться, если на то нет веской причины, т.к. в нем скорость доступа к элементу O(log(n)). У unordered_map в среднем O(n).

Я понимаю. Мою конструкцию можно вообще из векторов собрать.
Что-то вроде std::vector<std::vector<bool>>. Будет шустрее.
Но я использую такой массив для данных не очень часто обновляемых, так что проблем это не вызывает.

Если ты про массив массивов, то он плох всем. В нем надо выполнить число строк + 1 выделений памяти, что весьма небыстрая операция, а также хранить лишние число строк указателей.

Что, вообще-то говоря, намного эффективнее, чем у ТС, где вообще на каждый элемент его массива выделяется отдельный блок памяти, многократно превышающий размер хранящегося в этом блоке элемента данных (если речь про хранение bool-ов).

Кроме того в векторе векторов довольно просто удалять и добавлять как столбцы, так и строки.

Сильно зависит от объема данных. У меня в некоторых случаях на маленьких map-ах доступ к элементам был заметно быстрее, чем в аналогичных по размеру unordered_map. Зато на больших объемах unordered_map выигрывал у map-а.

Так что тут мерить приходится, просто так априори сложно судить.

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

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

Ей богу, сделали бы вектор векторов и получили бы те самые a[i][j] + более эффективное размещение в памяти.

Правда, ЕМНИП, vector<bool> имеет специальную реализацию, с которой можно получить сюрпризы. Но эти штуки уже давным-давно описаны и информацию по ним найти не сложно.

й богу, сделали бы вектор векторов

Да я так и сделаю. На самом деле я и сам сейчас удивляюсь какого хрена я в таких случаях уже хрен знает сколько времени пишу мапы. Когда-то для чего-то так было нужно, а потом сформировалась привычка и эта тема теперь пишется на автомате без участия критического мышления:)
Впрочем, bool я написал просто для примера. У меня там много всякой разной гадости может быть.

У меня там много всякой разной гадости может быть.

Даже если там гадость какого-то большего размера, то при определенных сценариях использования данных vector может быть гораздо эффективнее ассоциативных контейнеров. Например, при последовательном проходе по строке (или части строки). Больше шансов попадания в кэш при переходе к следующему элементу строки.

В случае же с ассоциативными контейнерами, где каждый элемент лежит в своем отдельном блоке, может запросто оказаться, что эти блоки для «соседних» элементов контейнера разбросаны по разным страницам (особенно в многопоточных приложениях, если нет какого-нибудь хитрого аллокатора).

то при определенных сценариях использования данных vector может быть гораздо эффективнее

Ну, в масштабе сплошного массива вектор всегда будет эффективней.
Мне нужны ключи лишь в виде порядкового номера.
В моём случае использование мапа — пустая трата ресурсов.

Я к тому, что обычным map лучше вообще не пользоваться, если на то нет веской причины, т.к. в нем скорость доступа к элементу O(log(n)). У unordered_map в среднем O(n).

Асимптотические оценки освоил, молодец, но только нужно ещё и головой думать. Не всегда контейнеры растут бесконечно, размер некоторых ограничен, а когда он ограничен, работает не асимптотика, а константы. А константы в пользу map, потому что сравнить две строки быстрее, чем считать от каждой хэш.

Я поэтому и написал о «если нет веской причины». Случай небольшого количества элементов - как раз такой.

А константы в пользу map

Где твои бенчмарки, бро?

Во. Что бы ты не придумал, оно уже есть в Boost.

std::map < std::pair <int, int>, bool>

денегенераты блять. и откуда вы токо лезите?

А теперь, умный аноним, прикинь как будет выглядеть обращение к элементу. Круто? Совсем не по дегенеративному?

А почему ты map называешь массивом? Что в итоге сделать то хочешь?

auto it = m.find({10,20});

а на счёт перформанса я тебе анектод раскажу:

знаешь что такое инсталяция в современном искусстве? это насрать под дверью, позвонить и убежать. а что такое перформанс? это позвонить, подждать пока откроют и начать срать прямо перед дверью.

auto it = m.find({10,20});

Это был перформанс, как я понимаю?:)

я другой перформанс имел ввиду, ну ладно, понимай как хочешь.

Я к тому, что обычным map лучше вообще не пользоваться, если на то нет веской причины, т.к. в нем скорость доступа к элементу O(log(n)). У unordered_map в среднем O(n).

Ты хотел сказатьу анордеред в среднем O(1)?

Да, конечно.

Вложенные map-ы для прямоугольного массива bool-ов! Офигеть.

array[x*N + y]

Единственно верное решение.

Самому-то не смешно? Или у тебя поломалось чувство прекрасного?
Сравни с array[x][y]=z.

facepalm.hpp

А саня из соседнего подъезда часто использует трехмерные массивы. Вам надо собраться и написать два письма! И это еще дело до 4х-мерных не дошло.

а нет ли где-то в недрах STL специального контейнера для таких случаев?

Есть, называется std::vector. Над ним сделайте обертку, которая будет хранить размерность и перегрузите [][] для доступа к элементу.

знаешь что такое инсталяция в современном искусстве? это насрать под дверью, позвонить и убежать. а что такое перформанс? это позвонить, подждать пока откроют и начать срать прямо перед дверью.

Это пять!

Двачую!

Вообще я много видел извращений для создания многомерных массивов, но что бы через вложеннеы мапы...

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

O(log(n)). У unordered_map в среднем O(n)

Может O(1) ?

На самом деле там ЕМНИП O(log(n)), только множитель другой.

Ну зачем же get, если есть operator[], ещё одну обёртку, конечно, возвращать, но компилятор сведёт к тому же get.

Он джавер, им перегружаемые операторы не завезли.

Ну или так да. На С++ пишу редко, вылетело из головы, что там операторы-то переопределяются. У нас в Java только get(). :)

На самом деле там ЕМНИП O(log(n)), только множитель другой.

На самом деле надо читать стандарт, а не сосать палец

typedef

typedef уже не модно.

template<typename T1, typename T2, typename T3>
using rectarray = std::map<T1, std::map<T2, T3> >;