map, vector, list
В чем состоит суть и отличие контейеров map,vector?
В чем состоит суть и отличие контейеров map, vector?
map представляет собой множество пар ключ/значение, отсортированных по ключу. (словарь)
vector - это аналог привычного массива
map представляет собой множество пар ключ/значение, отсортированных по ключу. (словарь)
vector - это аналог привычного массива
Если вдаваться в алгоритм контейнера map, то какой механизм используется для поиска - хэширование,AVL-дерево или что-либо другое?
Стоит ли делать свой механизм на основе хэширования, AVL-дерева. Или это уже есть в STL
Если вдаваться в алгоритм контейнера map, то какой механизм используется для поиска - хэширование,AVL-дерево или что-либо другое?
Используется двоичный поиск
В PERL'e аналог std::map называется hash.
Стоит ли делать свой механизм на основе хэширования, AVL-дерева. Или это уже есть в STL
А строить ли самому AVL? Нужно оценить что эффективнее: двоичный поиск в линейном массива или поиск в винарном дереве.
Количество шагов ведь одинаковое.
Используется двоичный поиск
В PERL'e аналог std::map называется hash.
А строить ли самому AVL? Нужно оценить что эффективнее: двоичный поиск в линейном массива или поиск в винарном дереве.
Количество шагов ведь одинаковое.
важно уточнить, что понимать под поиском в бинарном дереве - метод хэширования или AVL-дерево. Ведь это совсем разные подходы.
Ссылка
http://www.rsdn.ru/article/alg/bintree.xml
важно уточнить, что понимать под поиском в бинарном дереве - метод хэширования или AVL-дерево. Ведь это совсем разные подходы.
Ссылка
http://www.rsdn.ru/article/alg/bintree.xml
На сколько мне известно в стандарте не описана реализация класса map, поэтому говорить можно лишь о конкретных реализациях.
Опять же на сколько мне известно, в том STL, что поставляется с MSVS класс map реализован через сбаллансированные деревья (т.е. AVL), через хеш реализован другой класс - hash_map, которого, кстати, нет в стандарте :)
На сколько мне известно в стандарте не описана реализация класса map, поэтому говорить можно лишь о конкретных реализациях.
Опять же на сколько мне известно, в том STL, что поставляется с MSVS класс map реализован через сбаллансированные деревья (т.е. AVL), через хеш реализован другой класс - hash_map, которого, кстати, нет в стандарте :)
Значит реализовывать свой класс AVL-деревьев не имеет смысла, если в STL который в MSVS это уже сделано.
STL в конкретных реализациях использует разные методы? Вроде ведь HP разрабатывает STL.
STL в конкретных реализациях использует разные методы? Вроде ведь HP разрабатывает STL.
Есть множество реализаций STL.
К примеру, STLport.