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

Между 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>Вы считаете такое поведение нормальным?
Иногда очень удобно, например при построении небольших разреженных гистограмм.

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

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

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

Хм. Это гарантируется Стандартом?

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

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

Q>Вот и приходится для доступа использовать метод find(), а для вставки — insert(). Operator [] вообще могли бы не делать.
+1. И для полного счастья нет константной реализации.

void foo(const std::map<int, int> &m)
{
    cout<<m[1]<<endl; // error: passing `const std::map<int, int ... skipped ... discards qualifiers|
}

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

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

Да. Тоже вариант.

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

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

M>Хм. Это гарантируется Стандартом?

http://ra.dkuug.dk/jtc1/sc22/open/n2356/lib-containers.html#lib.map.access

  (*((insert(make_pair(x, T()))).first)).second.

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

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

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

M>>Хм. Это гарантируется Стандартом?

AG>http://ra.dkuug.dk/jtc1/sc22/open/n2356/lib-containers.html#lib.map.access
AG>

AG>  (*((insert(make_pair(x, T()))).first)).second.
AG>

Это понятно. Пришлось самому лезть в Стандарт:

8.5 Initializers [dcl.init]
...................
To zero-initialize an object of type T means:
— if T is a scalar type (3.9), the object is set to the value of 0 (zero) converted to T;
...................
To value-initialize an object of type T means:
— if T is a class type (clause 9) with a user-declared constructor (12.1), then the default constructor for T is
called (and the initialization is ill-formed if T has no accessible default constructor);
— if T is a non-union class type without a user-declared constructor, then every non-static data member
and base-class component of T is value-initialized;
— if T is an array type, then each element is value-initialized;
— otherwise, the object is zero-initialized
...................
An object whose initializer is an empty set of parentheses, i.e., (), shall be value-initialized.

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

  (*((insert(make_pair(x, DefaultFactory()))).first)).second.

, где DefaultFactory — параметр тип для map.