Как делать выбор навскидку (без профилирования):

Между stdext::hash_map, boost::unordered_map и std::map ?
Между CAtlMap и CRBMap, CSimpleMap ?

допустим, мэпы типа int на int или указатель на указатель.

Здравствуйте, Alexander G, Вы писали:

AG>Как делать выбор навскидку (без профилирования):

AG>Между stdext::hash_map, boost::unordered_map и std::map ?
AG>Между CAtlMap и CRBMap, CSimpleMap ?

AG>допустим, мэпы типа int на int или указатель на указатель.

Если без профилирования — кидай монетку, не ошибешься

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

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>Если без профилирования — кидай монетку, не ошибешься

J>У меня были случаи, когда хеш рвал деревянную мапу, и бывало наоборот.
J>Предсказать, что именно будет работать быстрее на современных системах, да еще и с оптимизирующими компиляторами, очень сложно.

Я понимаю. Но если всё равно, какой-то дефолтный выбор есть ?
Например, когда нет идей какой последовательный контейнер лучше, берут вектор.

Здравствуйте, Alexander G, Вы писали:

AG>Я понимаю. Но если всё равно, какой-то дефолтный выбор есть ?
AG>Например, когда нет идей какой последовательный контейнер лучше, берут вектор.

deque берут.
hashmap, вроде, стоит брать, когда есть больше сотни элементов + ключ std::string.

Здравствуйте, Nuzhny, Вы писали:

N>deque берут.

Только не на Dinkum STL. Там deque не намного лучше list'а

Здравствуйте, Кодт, Вы писали:

К>Только не на Dinkum STL. Там deque не намного лучше list'а

А где кошерный дек, и почему он дефолтнее вектора ?

Здравствуйте, Кодт, Вы писали:

К>Только не на Dinkum STL. Там deque не намного лучше list'а

Т.е. дек из студии нарушает 23.1.1 ?

9 The operations in Table 6 are provided only for the containers for which they take constant time:
...
a[n] T&; const T& *(a.begin() + n) vector, deque

Здравствуйте, Alexander G, Вы писали:

AG>Т.е. дек из студии нарушает 23.1.1 ?

Дек — это двухъярусный контейнер: вектор указателей на массивы фиксированной длины (вырождающихся до одиночных элементов).
В общем, не list, конечно, но мозгожор точно.

Здравствуйте, Alexander G, Вы писали:

AG>Как делать выбор навскидку (без профилирования):

AG>Между stdext::hash_map, boost::unordered_map и std::map ?
AG>Между CAtlMap и CRBMap, CSimpleMap ?

AG>допустим, мэпы типа int на int или указатель на указатель.
Дык напиши код, который будет слабо зависить от типа контейнера. Потом,
на стресс тестах поменяешь что-нибудь типа
typedef std::map container; на что-нибудь типа
typedef std::hash_map container;
В зависимости от производительности. Я бы так сделал

Здравствуйте, Кодт, Вы писали:

К>Дек — это двухъярусный контейнер: вектор указателей на массивы фиксированной длины (вырождающихся до одиночных элементов).

Тогда чем это дефолтнее вектора ?

Здравствуйте, Alexander G, Вы писали:

AG>Как делать выбор навскидку (без профилирования):

Навскидку без профилирования — значит надо учитывать асимптотики.

Абстрактный тип данных «Ассоциативный массив» обычно реализуют на основе одной из трёх структур данных:
1) Двоичное дерево, которое надо поддерживать более-менее сбалансированным (например, красно-чёрное).
2) Хэш-таблица.
3) Отсортированный список пар.

В C++ этим реализациям соответствуют std::map<K, V>, boost::unordered_map<K, V> и Loki::AssocVector<K, V>. В .NET им соответсвуют реализации интерфейса IDictionary<K, V>: SortedDictionary<K, V>, просто Dictionary<K, V>, SortedList<K, V>.

Асимптотики (если кратко и приблизительно, хотя в каждом случае нужны оговорки):
1) Двоичное дерево: доступ логарифмический, вставка константная, удаление константное.
2) Хэш-таблица: доступ константный, вставка константная (но иногда приводит к перестройке контейнера аж за линейное время), удаление константное.
3) Сортированный список: доступ логарифмический (бинарный поиск в отсортированном массиве), вставка линейная, удаление линейное.

Когда и что предпочесть? Если размер контейнера меняется редко (задаётся при инициализации и дальше не меняется), то выгодно использовать реализацию на базе хэш-таблицы (boost::unordered_map<K, V> или stdext::hash_map<K, V>). Если контейнер предполагается не особо большим, то, возможно, стоит предпочесть Loki::AssocVector<K, V>. Асимптотики у него похуже, чем у std::map<K, V>, зато он будет занимать меньше места в памяти: ведь массив устроен гораздо проще, чем древовидная струтура. К тому же, для небольших размеров константа, входящая в определение О-большого, может «забивать» асимптотику.

Кроме того, надо учитывать requirements, налагаемые на типы ключей: в случае хэш-таблицы требуется, чтобы для типа ключа была реализована хэш-функция (в случае int'а с этим всё нормально). В остальных случаях требуется наличие линейного порядка на множестве ключей (operator <).

Плюс ещё надо учитывать, что в std::map<K, V> нет метода at(), а семантика оператора operator [] исключительно ущербна. В частности, нельзя хранить объекты классов, не имеющих ктор-по-умолчанию. Не говоря уже о том, что в случае ненахождения элемента создаётся новый — это сводит к нулю случаи, в которых operator [] употребим.

Здравствуйте, Alexander G, Вы писали:

AG>Тогда чем это дефолтнее вектора ?

У Мейерса, кажись, об этом написано. По памяти не приведу...

Здравствуйте, Qbit86, Вы писали:

Q>в случае ненахождения элемента создаётся новый — это сводит к нулю случаи, в которых operator [] употребим.
При ситуации отсутстыия по какой либо причине исключений сколь либо вменяемый fail для operator[] реализовать не представляется возможным. Поэтому ИМХО по другому никак.

CC>При ситуации отсутстыия по какой либо причине исключений сколь либо вменяемый fail для operator[] реализовать не представляется возможным. Поэтому ИМХО по другому никак.

Вот и приходится для доступа использовать метод find(), а для вставки — insert(). Operator [] вообще могли бы не делать.
А по другому реализовать можно, например, вернуть из оператора «опцион», специальное размеченное объединение (в терминологии ФП, а не C++). В .NET'е можно было бы вернуть null, в плюсах, быть может, boost::optional<V>:

boost::optional<V> v = my_map[key];
if (!v) {
  // Обработать отсутствие.
}
else {
  V const value = v.get();
}

Здравствуйте, Qbit86, Вы писали:


Q>Асимптотики (если кратко и приблизительно, хотя в каждом случае нужны оговорки):
Q>1) Двоичное дерево: доступ логарифмический, вставка константная, удаление константное.
Вставка логарифмическая, удаление логарифмическое.

Q>2) Хэш-таблица: доступ константный, вставка константная (но иногда приводит к перестройке контейнера аж за линейное время), удаление константное.
тут сильно зависит от реализации, наиболее простой вариант со списочным разрешением коллизий дает O(n) в худшем случае. Впрочем, если подобрать хорошую хэш — функцию, то с практической точки зрения можно действительно считать O(1)

Здравствуйте, Sergey Chadov, Вы писали:

Q>>1) Двоичное дерево: доступ логарифмический, вставка константная, удаление константное.
SC>Вставка логарифмическая, удаление логарифмическое.

Виноват, зарапортовался. Конечно же, вставка и удаление логарифмические, я это и имел в виду :) Спасибо внимательным читателям :)

Q>>2) Хэш-таблица: доступ константный, вставка константная (но иногда приводит к перестройке контейнера аж за линейное время), удаление константное.
SC>тут сильно зависит от реализации, наиболее простой вариант со списочным разрешением коллизий дает O(n) в худшем случае. Впрочем, если подобрать хорошую хэш — функцию, то с практической точки зрения можно действительно считать O(1)

Зависит не только от хэш-функции, но и от отношения число_элементов/число_корзин. В стандартных реализациях следят за тем, чтобы это отношение не превышало некоторой величины, а при превышении происходит упомянутая перестройка контейнера за линейное время (увеличивается число корзин). В таких условиях даже при списочном разрешении коллизий можно говорить об O(1) как о среднем времени доступа (в худшем — O(n)).

Здравствуйте, Qbit86, Вы писали:

Q>Operator [] вообще могли бы не делать.

Для мапы с интами вполне работает []
std::map<int, int> m;
++m[3]; // m[3] теперь == 1

Здравствуйте, Alexander G, Вы писали:

AG>Для мапы с интами вполне работает []

Я где-то утверждал, что не работает?

AG>std::map<int, int> m;
AG>++m[3]; // m[3] теперь == 1

Вы считаете такое поведение нормальным?

Здравствуйте, Qbit86, Вы писали:


Q>Зависит не только от хэш-функции, но и от отношения число_элементов/число_корзин. В стандартных реализациях следят за тем, чтобы это отношение не превышало некоторой величины, а при превышении происходит упомянутая перестройка контейнера за линейное время (увеличивается число корзин). В таких условиях даже при списочном разрешении коллизий можно говорить об O(1) как о среднем времени доступа (в худшем — O(n)).

Ну я и говорю, что зависит от реализации. Например, если использовать cuckoo hashing, то доступ бужет гарантированно O(1), но вставка может привести к ребилду всей таблицы.

Здравствуйте, Qbit86, Вы писали:

AG>>std::map<int, int> m;
AG>>++m[3]; // m[3] теперь == 1

Q>Вы считаете такое поведение нормальным?
Иногда очень удобно, например при построении небольших разреженных гистограмм.