C++ за 21 день седьмое издание

8:	cout	«	"Number of pairs,	size():
" « Input.size() « endl;
9:	cout	«	"Max bucket count	= " «	Input.max_bucket_count()

1. 
   endl;
   

0. 
   cout « "Load factor: " « Input.load_factor() « endl;
   

0. 
   cout « "Max load factor = " « Input.max_load_factor() « endl;
   

0. 
   cout « "Unordered Map contains: " « endl;
   

13:

0. 
   for(auto iElement = Input.cbegin() // auto, cbegin: C++11
   

15: ; iElement != Input.cend() // cend(): C++11

0. 
   ; ++ iElement )
   

0. 
   cout« iElement->first« " -> " « iElement->second« endl;
   

0. 
   }
   

19:

0. 
   int main()
   

21: {

0. 
   unordered_map umapIntToString;
   

0. 
   umapIntToString.insert(make_pair(1, "One"));
   

0. 
   umapIntToString.insert(make_pair(45, "Forty Five"));
   

0. 
   umapIntToString.insert(make_pair(1001, "Thousand One"));
   

0. 
   umapIntToString.insert(make_pair(-2, "Minus Two"));
   

0. 
   umapIntToString.insert(make_pair(-1000, "Minus One Thousand"));
   

0. 
   umapIntToString.insert(make_pair(100, "OneHundred"));
   

0. 
   umapIntToString.insert(make_pair(12, "Twelve"));
   

0. 
   umapIntToString.insert(make_pair(-100, "Minus One Hundred"));
   

0. 
   

0. 
   DisplayUnorderedMapcint, string>(umapIntToString);
   

33:

0. 
   cout « "Inserting one more element" « endl;
   

0. 
   umapIntToString.insert(make_pair(300, "Three Hundred"));
   

0. 
   DisplayUnorderedMap(umapIntToString);
   

37:

0. 
   cout « "Enter key to find for: ";
   

0. 
   int Key = 0;
   

0. 
   cin » Key;
   

41:

0. 
   auto iElementFound = umapIntToString.find(Key);
   

0. 
   if (iElementFound != umapIntToString.end())
   

0. 
   {
   

45: cout « "Found! Key " « iElementFound->first

1. 
   " points to value ";
   

0. 
   cout « iElementFound->second « endl;
   

0. 
   }
   

Предоставление специального предиката сортировки

479

0. 
   else
   

0. 
   cout « "Key has no corresponding value in unordered map!"
   

0. 
   endl;
   

50:

0. 
   return 0;
   

0. 
   }
   

Результат


Number of pairs, size(): 8


Max bucket count = 8


Load factor: 1


Max load factor = 1


Unordered Map contains:


-1000 -> Minus One Thousand


1001 -> Thousand One


1 -> One


-100 -> Minus One Hundred


45 -> Forty Five


-2 -> Minus Two


12 -> Twelve


100 -> One Hundred


Inserting one more element


Number of pairs, size(): 9


Max bucket count = 64


Load factor: 0.140625


Max load factor = 1


Unordered Map contains:


1 -> One


-1000 -> Minus One Thousand


1001 -> Thousand One


-100 -> Minus One Hundred


45 -> Forty Five


-2 -> Minus Two


300 -> Three Hundred


12 -> Twelve


100 -> One Hundred


100 -> One Hundred


Enter key to find for: 300


Found! Key 300 points to value Three Hundred


Анализ

Просмотрите вывод и обратите внимание на то, как контейнер u n o rd ered _ m a p , изна­ чально насчитывающий восемь ячеек и заполненный восьмью парами, изменяет свои раз­ меры при вставке девяти пар. Вот когда количество ячеек увеличивается до 64. Обратите внимание на применение методов m a x _ b u c k e t_ c o u n t (), lo a d _ f a c t o r () и m a x _ lo ad _ f a c t o r () в строках 9-11, а также на то, что остальная часть кода почти не отличается от такового по сравнению с контейнером s t d : :map. Это же относится и к применению метода f i n d () в строке 42, который возвращает итератор, как и у контейнера s t d : :map, его также следует сравнить с результатом метода e n d (), чтобы удостовериться в успехе операции.

0. 
   ЗАНЯТИЕ 20. Классы карт библиотеки STL
   

ВНИМАНИЕ!	Не следует полагаться на порядок элементов в контейнере unordered_map
	независимо от ключа. Порядок элементов относительно других элементов в
	карте зависит от многих факторов, включая их ключ, порядок вставки, количе­
	ство ячеек и т.д.
	Эти контейнеры оптимизированы для производительности поиска, поэтому не	;
	стоит полагаться на порядок элементов при их переборе.	|
ПРИМЕЧАНИЕ	Продолжительность вставки и поиска в контейнере std: :unordered_map
	практически постоянна (при отсутствии конфликтов) и не зависит от количе­
	ства содержащихся в нем элементов. Но это не обязательно делает контейнер	|
	std: :unordered_map предпочтительней контейнера std: :map, который	i
	обеспечивает логарифмическую сложность во всех ситуациях. Постоянная про-	'
	должительность может оказаться намного больше логарифмической, когда ко-	j
	личество содержащихся элементов не слишком велико.

При выборе типа контейнера имеет смысл провести испытания, моделирующие их применение в реальном сценарии.

РЕКОМЕНДУЕТСЯ

Используйте карту, если необходимо хранить пары “ключ-значение" с уникальными ключами

Используйте мультикарту, если необходимо хранить пары “ключ-значение”, ключи кото­ рых могут повторяться (например, телефонный справочник)

Помните, что и карта, и мультикарта, как и дру­ гие контейнеры библиотеки STL, предоставляют метод size (), сообщающий количество храни­ мых пар

Используйте контейнеры unorderedjmap или unordeгed_mu 11imap, когда абсолютно необходима постоянная продолжительность вставки и поиска (обычно, когда количество элементов очень высоко)

Резюме
НЕ РЕКОМЕНДУЕТСЯ

Не забывайте, что метод multimap::count {Ключ) сообщает количество доступных в кон­ тейнере пар, индексированных при помощи ключа Ключ

Не забывайте проверять результат метода find (), сравнив его с результатом метода end ()

На сегодняшнем занятии рассматривались шаблоны классов тар и m ultim ap би­ блиотеки STL, их важнейшие функции-члены и характеристики. Вы также узнали, что

0. 
   этих контейнеров логарифмическая сложность и что библиотека STL предоставляет хеш-таблицы в форме контейнеров unordered_map и unordered_m ultim ap. Они демон­ стрируют высокую производительность операций вставки и поиска, которая не зависит от размера контейнера. Вы также узнали о важности возможности настройки критериев со­ ртировки с использованием предиката, как представлено в приложении из листинга 20.5.
   

Вопросы и ответы

48 1

Вопросы и ответы

0. 
   Как мне объявить контейнер тар для хранения целых чисел, отсортированных в порядке убывания?
   

Карту целых чисел определяет шаблон класса m ap< int> . Он имеет заданный по умол­ чанию предикат сортировки s t d : : le ss< T > , располагающий элементы в порядке воз­ растания. Его можно выразить как m a p < in t, l e s s < in t> > . Для сортировки в порядке убывания определите карту как m a p c in t, g r e a te r < in t> > .

0. 
   Что будет при вставке в карту для строк строки "Jack" дважды?
   

Карта не предназначена для хранения повторяющихся значений. Поэтому реализация класса s t d : :map не позволит вставить второе значение.

0. 
   Что нужно изменить в предыдущем примере, чтобы все-таки вставить две строки "Jack"?
   

Реализация класса т а р позволяет хранить только уникальные значения. Смените вы­ бранный контейнер на m u ltim ap .

0. 
   Какая функция-член класса multimap возвращает количество элементов с опреде­ ленным значением в контейнере?
   

Функция c o u n t (зн а ч е н и е) .

0. 
   Используя функцию fin d (), я нашел элемент в карте и имею теперь указываю­ щий на него итератор. Как мне использовать этот итератор для изменения значе­ ния, на которое он указывает?
   

Никак. Некоторые реализации библиотеки STL могли бы позволить пользователю из­ менить значение элемента карты при помощи итератора, возвращенного, например, функцией f i n d (). Но так поступать неправильно. Итератор на элемент карты должен использоваться как константный, даже когда реализация библиотеки STL не препят­ ствует этому.

0.