Оптимальный контейнер для коллекции?

А map <coords, vector <> > чем не нравится?

map<coords, ...> уже не нравится тем, что скорость доступа кардинально проигрывает обычному двумерному массиву. В данном случае двумерный массив будет не настолько разрежен, что бы имело смысл юзать map.

Вот насчет std::vector в ячейке я как раз сейчас думаю. Я с ним никогда плотно не работал. Там забавно сделано резервирование памяти по умолчанию - при нехватке выделяется вдвое больше, чем было. Но м.б. я чего то не знаю, и есть че нить получше? Я в свое время писал шнягу с блочным выделением памяти.

Что ты имеешь ввиду под «памятью» - адресное пространство?

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

Пишут что некоторые реализации могут увеличивать и в 1.5 раза. Если заранее знаешь размер массива можно вызвать reserve()

Под памятью я понимаю занятую память. В байтах;-)

Про reserve знаю, но заранее размер не знаю. Если бы знал, юзал бы совсем другую структуру;-)

map<coords, ...> уже не нравится тем, что скорость доступа кардинально проигрывает обычному двумерному массиву.

unordered_map?

а что на счет двухмерного массива индексов из вектора и вектора векторов ячеек?

Это ЕМНИП хэш, по реализации те же яйцы что и map, тока в профиль. И вообще, выше ж написано - двумерный массив тут не настолько разрежен что бы юзать что то кроме двумерного массива, потому что скорость доступа к элементу у двумерного массива самая высокая.

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

а что на счет двухмерного массива индексов из вектора и вектора векторов ячеек?

Думал. sizeof(std::vector<...>)==>24. Ну будет 4, 20 байт экономии на одну пустую ячейку (на самом деле экономии будет даже 28 байт поскольку в непустых ячейках еще double приделан), зато лишний переход по пойнтеру + более сложное решение. Я ХЗ, насколько это серьезный профит... сходу кажется что не очень? Размер 2D массива порядка 400х400.

https://code.google.com/p/cpp-btree/ ?

делать подобное с минимальным оверхедом по памяти

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

Зачем?

Под linux. Мысль интересная... но как то стремно;-)

Зачем?

Затем что:

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

Я переформулирую. вопрос - каким образом Вы предлагаете прикрутить это к данной задаче? Потому что вместо 2D массива я никаких деревьев юзать точно не буду. Вместо вектора в одной ячейке - а как там с локальностью, если число элементов заранее неизвестно?

но как то стремно;-)

Стрёмно, да. Зато эффективно и делать ничего не надо.

Вот насчет второго не уверен. Из скромного личного опыта - все беды из за лени;-)

Это ЕМНИП хэш, по реализации те же яйцы что и map, тока в профиль

Хеш, да. Скорость доступа по индексу больше (константная в идеале), чем у мапы с её бинарным поиском.

В остальном, ну подходит двумерный массив и отлично.

каким образом Вы предлагаете прикрутить это к данной задаче?

Прикрутить к структуре (x, y).

Потому что вместо 2D массива я никаких деревьев юзать точно не буду.

Дело хозяйское.

а как там с локальностью, если число элементов заранее неизвестно?

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

Скорость доступа по индексу больше (константная в идеале), чем у мапы с её бинарным поиском.

ЕМНИП unordered_map реализован как map<long>, ключами которого выступают хэш-значения. Там сделаны некоторые оптимизации, и скорость доступа ЕМНИП на порядок выше чем у обычного map<log>, но она отнюдь не O(1). Чудес не бывает, как Вы себе представляете скорость доступа O(1) по массиву с разженным ключем O_O?

В остальном -да.

У меня фактически 3D массив переменной толщины, и локальность волнует именно по третьей координате.

У меня фактически 3D массив переменной толщины, и локальность волнует именно по третьей координате.

На Вас царь так плохо влияет? Я как то уже не уверен, мы сейчас про B-Tree говорим :)

Можно тройку (x,y,z) в качестве индекса, будет по z локально.

Мы сейчас про мою задачу говорим - по третьей координате местами размер массива равен нулю;-)

Не то, что я спец по деревьям, но есть ощущения что деревья в данном случае вообще не про то. Хотя надо бы с B-tree поподробней таки разобраться, который раз оно всплывает в обсуждении...

по третьей координате местами размер массива равен нулю;-)

И это прекрасно. Больше нулей — ниже дерево.

деревья в данном случае вообще не про то.

Если количество элементов заранее неизвестно, то они как раз про то.

Но есть нюанс - нулевые элементы тоже придется проверять на нулевость.;-)

Но есть нюанс - нулевые элементы тоже придется проверять на нулевость.;-)

Не читайте на ночь царя. А вообще проще всего взять и проверить. Иногда бывает что самое простое работает лучше всего.

Я уже запилил std::vector. Проверить лучше всего, но цейтнот. И проэкт уж больно сложный, думаю никогда еще человечество не видело столько разнообразных интерполяций в одном отдельно взятом коде;-)

Деревья это страшно интересная тема, особенно для адаптивно-рекурсивных сеток. Но пока некогда;-(

map<coords, ...> уже не нравится тем, что скорость доступа кардинально проигрывает обычному двумерному массиву

unordered_map?

Может, /dev/null подойдёт? Хранит что угодно, правда, доставать сложно.

Тред не читай, сразу отвечай!

Вот не надо возвращаться к этой теме.

ещё в том варианте индексы можно расставлять с каким-нибудь умыслом...

организовать массив в каждой клетке ? свой вектор пишится минут за пять, да еще и всем своим условиям удолетворят будет, и никакого флейма не надо

Доставать можно через /dev/random.

ЕМНИП unordered_map реализован как map<long>, ключами которого выступают хэш-значения.

Нее, там именно «массив» внутри. Соответственно доступ по индексу. Сложность не константная в том случае, если возникают коллизии - несколько значений по одному хешу и приходится уже проверять их.

Ну и если заранее известно какие данные будут, то хеш-функцию можно оптимизировать.

Ну тебе собсна уже рассказали, что в unordered_map массив и при отсутствии коллизии O(1). Гарантированно без коллизий - perfect hashing.

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

sdt::vector::reserve( ...) поможет решить эту проблему, ты ведь примерно знаешь, сколько тебе необходимо памяти.

Ребят ( invy), ну посмотрите что ли исходники unordered_map и потестите скорость доступа, к чему мифы то плодить... лично я смотрел и тестил (Текстовые индексы. (комментарий) Текстовые индексы. (комментарий) - картинка правда протухла за давностью лет, но там есть код, можно ее заново построить).

Еще раз повторяю вопрос - как вы себе представляете массив с разреженным ключем типа long? Т.е. на современном железе такое конечно возможно, но с учетом особенностей работы подсистемы памяти это O(1) будет ну оооочень большим;-)

Аналитика и умственная медитация это хорошо, но иногда не обойтись без метода научного тыка. Я бы посоветовал ТС попытаться как-то отабстрагироваться от структуры коллекции и метода обхода и потом начать перебирать варианты. Так хоть можно получить информацию «по существу», а не просто пустой треп аналитиков на ЛОРе.

Для тех кому лень читать весь этот флейм с царем, повторяю - все, сделал уже через вектор. Всем спасибо;-)