std:: unordered_map::find
Searches the container for an element with k as key and returns an iterator to it if found, otherwise it returns an iterator to unordered_map::end (the element past the end of the container).
Another member function, unordered_map::count, can be used to just check whether a particular key exists.
The mapped value can also be accessed directly by using member functions at or operator[].
Parameters
k Key to be searched for.
Member type key_type is the type of the keys for the elements in the container, defined in unordered_map as an alias of its first template parameter (Key).
Return value
An iterator to the element, if the specified key value is found, or unordered_map::end if the specified key is not found in the container.
Member types iterator and const_iterator are forward iterator types.
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// unordered_map::find int main () < std::unordered_mapdouble> mymap = < "mom",5.4>, "dad",6.1>, "bro",5.9> >; std::string input; std::cout "who? "; getline (std::cin,input); std::unordered_mapdouble>::const_iterator got = mymap.find (input); if ( got == mymap.end() ) std::cout "not found"; else std::cout first " is " second; std::cout return 0; >Possible output:
who? dad dad is 6.1
Complexity
Average case: constant.
Worst case: linear in container size.
Iterator validity
No changes.
See also
unordered_map::count Count elements with a specific key (public member function) unordered_map::operator[] Access element (public member function) unordered_map::at Access element (public member function)
Когда map быстрее чем unordered (3 стр)
И да, сравнение алгоритмов вы делаете неправильно. Мы говорим что некий хэш будет быстрее R-B дерева при поиске ключа при увеличении N. Никто не говорит, что на малых N R-B дерево не может быть быстрее хэша.
#31
11:21, 25 мар 2015
neumond
Оптимизацию было бы неплохо включить.
#32
11:34, 25 мар 2015
g++ -std=c++11 -O2 test.cpp; A=0; for I in ; do A="$(( A + `./a.out` ))" ; done ; echo $A
2949339 — unordered
1769809 — map
g++ -std=c++11 -O2 -march=athlon64-sse3 -O2 -mmmx -msse -msse2 -m3dnow -msse3 -mcx16 test.cpp; A=0; for I in ; do A="$(( A + `./a.out` ))" ; done ; echo $A
2939051 — unordered
1745114 — map
clang++ -std=c++11 -O2 test.cpp; A=0; for I in ; do A="$(( A + `./a.out` ))" ; done ; echo $A
112 — unordered
107 — map
clang похоже вообще срезал все циклы.
#33
12:39, 25 мар 2015
Что ж, действительно, если увеличить количество данных, unordered_map начинает выигрывать. Причём неслабо так увеличить надо, до 2500. И даже тогда перевес не такой уж большой: 24433267 (map) против 17060605 (unordered). Сильный выигрыш даёт замена хэша на x.first + x.second: 12062029, тогда оно в 2 раза быстрее map на наборе в 2500.
#34
13:21, 25 мар 2015
f1ufx_
> Я привёл тебе пример в котором map быстрее чем unordered_map. Но твоё сознание
> считает написанное за опечатку и отрицает действительность, пытаясь убереч
> сознание.
Ды что ты такое несёшь? Я помимо этого сказал ещё что тестить на 50 элементах производительность не имеет смысла, уже бы сделал несколько тысяч.
#35
15:08, 25 мар 2015
Smouking
У тебя есть инвентарь персонажа, в который заведомо влезает не так уж много предметов.
Игрок кастует заклинание «ржавый кинжал», чтобы у всех персонажей в зоне заклинания все кинжалы поржавели (в том числе и те, которые в рюкзаке).
Т.е. поиск кинжала будет выглядеть так:
foreach( Entity ent : AffectCollector.getEntity() ) < tuple(Kinzhal) tk = ent->getInventory->find(Kinzhal); foreach( kinzhal k : tk ) k->doRust(); >
Как будешь хранить инвентарь персонажа? unordered_map-ой?
#36
15:23, 25 мар 2015
f1ufx_
> Как будешь хранить инвентарь персонажа?
vector items
#37
15:41, 25 мар 2015
-Eugene-
Верно. Об этом и топик.
#38
3:33, 28 мар 2015
На VS.
map обычно быстрее unordered.
Я всегда думал, нафига нужен в таком случае unordered? Не вижу смысла его использовать.
#39
4:29, 28 мар 2015
Чтобы лучше сравнивалось приведу ключевые отличия map от unordered_map:
1.
map — это сортированный массив по ключу, в котором содержится pair
unordered_map — это набор сортированных массивов, в котором содержится pair.
Замечание: Сортировка массивов в unordered_map может и не выполняться, а честно проходит по элементам и искать нужный ключ.
Но здесь сказано, что массивы сортированы. Короче зависит от реализации.
2.
map — Операции поиска, удаления и вставки имеют логарифмическую сложность. Реализуется как массив с бинарным поиском или как красно-черное дерево (в STL RBTree).
unordered_map (С++11) — Поиск, вставка и удаление имеют средний постоянной временной сложности (условно).
Выводы:
map — удобно применять при небольшом количестве элементов. Надо учитывать, что пробегая по map от начала и до конца вы пробегаете уже по сортированному набору.
Хотя я не сравнивал, работу vector> + qsort c map.
у unordered_map важно помнить, что любая операция имеет сложность O(1). Данный контейнер работает очень эффективно при большом наборе элементов и особенно если массивы сбалансированы.
#40
8:12, 28 мар 2015
asvp
Ты не сказал важную штуку в конце. map значительно быстрее работает с группами элементов.
Каким образом unordered_map выдает правильное значение для ключа, если его хеш функция допускает коллизии?
Неупорядоченные контейнеры обычно реализуются в виде хеш-таблицы(рис. 6.3). Таким образом, по существу, контейнер — это массив связанных списков. Позиция элемента в массиве вычисляется с помощью хеш-функции. Цель заключается в том, что бы каждый
элемент имел свою позицию, обеспечивающую к нему быстрый доступ, при условии быстрого вычисления хеш-функции. Однако, поскольку быстрые идеальныехеш-функциине не всегда возможны или могут потребовать огромный объем памяти для массива, разрешается хранить в одной и той же позиции несколько элементов. По этой причине элементами массива являются связанные списки, позволяющие хранить в одной позиции массива несколько элементов контейнера.
Раз уж каждый элемент массива внутри unordered_map является связанным списком и допускаются коллизии, то правильно ли я понимаю как это работает(добавление элемента в unordered_map, приблизительная реализация):
1. По хеш функции вычисляется индекс
2. В связанный список индекса сохраняется значение
3. В случае коллизии в next уже существующего значения для этого ключа добавляется новый элемент
4. В списке дополнительно хранится ключ-оригинал для каждого элемента (что бы при поиске с ним можно было сравнить тот ключ который попросил программист)
Т.е хочу узнать, в случае коллизий происходит ли итерация по списку в поисках соответствующего значения для ключа который попросил программист? А если элемент один — сразу он и возвращается. Я правильно понимаю?
Добавлено через 4 минуты
И ещё вот что интересно:
Зачем может понадобится повторное хеширование всей таблицы? Какой в этом смысл?
В книге сказано что если после удаления элемента происходит добавление — это может привести к повторному хешированию всей таблицы — это может произойти даже если занять через reserve много места? Или только если в таблице осталось всего 1 свободное место для вставляемого элемента после удаления?
C++ Unordered Map
In C++, the STL unordered_map is an unordered associative container that provides the functionality of an unordered map or dictionary data structure.
In contrast to a regular map, the order of keys in an unordered map is undefined.
Also, the unordered map is implemented as a hash table data structure whereas the regular map is a binary search tree data structure.
Create C++ STL unordered_map
In order to create an unordered map in C++, we first need to include the unordered_map header file.
#include
Once we import this file, we can create an unordered map using the following syntax:
unordered_map ump;- key_type indicates the data type for the key
- value_type indicates the data type for the value
// create an unordered_map with integer key and value unordered_map ump_integer; // create an unordered_map with string key and int value unordered_map ump_string;Initialize an Unordered Map
We can initialize a C++ unordered map in the following ways:
// Initializer List unordered_map unordered_map1 = < , , >; // Uniform Initialization unordered_map unordered_map2 < , , >;Here, we have initialized the unordered map by providing values directly to them.
Now, both unordered_map1 and unordered_map2 are initialized with , , > .
Example: C++ unordered_map
#include #include using namespace std; int main() < // uniform initialization unordered_map unordered_map1 < , , >; cout return 0; >Output
Key - Value Three - 3 Two - 2 One - 1
In the above example, we have declared and initialized an unordered map named unordered_map1 using uniform initialization.
unordered_map unordered_map1 < , , >;Then, we have displayed the unordered map content using a ranged for loop.
for(const auto& key_value: unordered_map1)
In the above code, each element (key-value pair) of the unordered map is stored in variable key_value .
Then, we get the key and value using:
- key_value.first — gives the key
- key_value.second — gives the value
Notice that we have created the unordered map in order of the keys: «One» , «Two» , «Three» . However, the output is in undefined order.
This is because the elements are not stored in any particular order based on key, or the values.
Note: Starting from C++17, you can use structure bindings to simplify this code further:
for(const auto& [key, value]: unordered_map1)
Other Ways to Initialize a C++ Unordered Map
Copy one unordered map to another.
We can copy one unordered map to another using range method initialization.
unordered_map unordered_map_1 < , , >; unordered_map unordered_map_2(unordered_map_1.begin(), unordered_map_1.end());Here, we have first created an unordered map named unordered_map_1 . Then, we created another unordered map called unordered_map_2 by copying all the elements of unordered_map_1 .
C++ Unordered Map Methods
In C++, the unordered_map class provides various methods to perform different operations on an unordered map.
| Methods | Description |
|---|---|
| insert() | insert one or more key-value pairs |
| count() | returns 1 if key exists and 0 if not |
| find() | returns the iterator to the element with the specified key |
| at() | returns the element at the specified key |
| size() | returns the number of elements |
| empty() | returns true if the unordered map is empty |
| erase() | removes elements with specified key |
| clear() | removes all elements |
Insert Key-Value Pairs to an Unordered Map
We can insert a key-value pair in an unordered map using :
- insert() — insert key-value pairs
- [] — insert a key and value
#include #include using namespace std; int main() < unordered_mapunordered_map1; // insert key-value pair unordered_map1["One"] = 1; // insert a pair unordered_map1.insert(); // insert two pairs , unordered_map1.insert(<, >); cout return 0; >Output
Key - Value Four - 4 Two - 2 Three - 3 One - 1
In the above example, we have initialized an empty unordered map to store the key-value pairs of a string and an integer.
Then, we have inserted the pair using [] .
unordered_map1["One"] = 1;We have then inserted another pair using the insert() method.
unordered_map1.insert();Finally, we inserted two pairs using insert() .
unordered_map1.insert(, >);Access Values of Unordered Maps
We can use the following methods to access the values of the specified key of an unordered map:
- at() — returns value for the specified key
- [] — returns value for the specified key
#include #include using namespace std; int main() < unordered_mapcapital_city < , , >; cout return 0; >
Output
Capital of Nepal is Kathmandu Capital of Australia is Canberra
In the above example,
- capital_city[«Nepal»] — returns the element with key «Nepal»
- capital_city.at(«Australia») — returns the element with key «Australia»
Note: While we can use the [] operator to access the elements, it is preferable to use the at() method.
This is because at() throws an exception whenever the specified key doesn’t exist, while [] pairs the key with a garbage value.
// key "Japan" doesn't exist // so the key "Japan" is paired with a garbage value cout
Change Values of an Unordered Map
We can use the at() method or the [] operator to change the value of the unordered map. For example,
#include #include using namespace std; int main() < unordered_mapcapital_city < , , >; cout // change value for "India" using [] capital_city["India"] = "New Delhi"; // change value for "Pakistan" using at() capital_city.at("Pakistan") = "Islamabad"; coutOutput
Old Capitals: India : Calcutta Pakistan : Karachi New Capitals: India : New Delhi Pakistan : Islamabad
In the above example, the initial key-value pairs for capital_city are and .
Then, we have used the [] operator to change the value for key "India" using:
capital_city["India"] = "New Delhi";Similarly, we have used the at() method to change the value for the key "Pakistan" using:
capital_city.at("Pakistan") = "Islamabad";Remove Elements From an Unordered Map
We can remove the element with the specified key of an unordered map using the erase() method. For example,
#include #include using namespace std; // function prototype for display_unordered_map() void display_unordered_map(const unordered_map &); int main() < unordered_mapstudent < , , >; cout // remove element with key: 143 student.erase(143);