#include
#include
2 : #include
#include
using namespace std;
6 : template ctypename T>
7: void DisplayContents (const T& Input)
8 :
9:
1 0 :
1 1 :
1 2 :
13:
14:
15:
16:
17:
18:
{
for(auto iElement
|
= Input.cbegin ()
|
// auto и cbegin(): C++11
|
; iElement
|
!= Input.cend()
|
// cend(): C++11
|
; ++
|
iElement )
|
" « iElement->second
|
cout «
|
iElement->first « " ->
|
endl;
cout « endl;
}
struct PredlgnoreCase
{
19: bool operator()(const strings strl, const strings str2) const
2 0 :
2 1 :
2 2 :
23:
24:
25:
26:
27:
28:
29:
30:
31:
{
string strlNoCase(strl), str2NoCase(str2);
std: transform (strl .begin () , strl.endO,
|
strlNoCase .begin () ,
|
|
tolower);
|
str2NoCase.begin(),
|
std::transform(str2.begin(), str2.end(),
|
|
tolower);
|
|
return(strlNoCase<
|
str2NoCase);
|
|
};
|
|
|
|
};
|
|
|
|
typedef map
|
string>
|
DIRECTORY_WITHCASE;
|
|
typedef map
|
string,
|
PredIgnoreCase> DIRECTORY_NOCASE;
|
474 ЗАНЯТИЕ 20. Классы карт библиотеки STL
i n t m ain()
{
34:
|
// Не
|
зависящий от регистра каталог: регистр
|
строкового ключа
|
35:
|
//не
|
имеет значения
|
|
DIRECTORY NOCASE d ir C a s e ln s e n s itiv e ;
|
|
36:
|
|
|
"2345764"));
|
37:
|
d i r C a s e l n s e n s i t i v e . in s e r t( m a k e _ p a ir ("John",
|
38:
|
d i r C a s e l n s e n s i t i v e . in s e r t( m a k e _ p a ir ("JOHN",
|
"2345764"));
|
39:
|
d i r C a s e l n s e n s i t i v e . in s e r t( m a k e _ p a ir ("S a ra " ,
|
"42367236"));
|
40:
|
d i r C a s e l n s e n s i t i v e . in s e r t( m a k e _ p a ir (" J a c k ",
|
"32435348"));
|
41:
|
|
|
|
42:
|
cout «
|
"D isplaying c o n te n ts of th e c a s e - i n s e n s i t i v e map:"
|
endl;
D is p la y C o n te n ts ( d ir C a s e ln s e n s itiv e ) ;
45: / / Зависящая от регистра карта: регистр строкового ключа
/ / влияет на вставку и поиск
DIRECTORY_WIТНСASЕ dirCaseSensitive(dirCaselnsensitive.begin()
47:
|
,
|
d i r C a s e l n s e n s i t i v e . e n d ( )) ;
|
48:
|
|
|
49:
|
cout « "D isplaying co n te n ts of th e
|
c a s e - s e n s i t i v e m a p :" « endl
|
D is p la y C o n te n ts (d irC a s e S e n s itiv e );
52:
|
/ / Поиск
|
по имени в двух картах и отображение результата
|
53:
|
cout «
|
"P lease e n t e r a name to se arch : " « e n d l « "> ";
|
s t r i n g strNameInput;
55:
|
c in
|
»
|
strN am elnput;
|
|
56:
|
|
|
|
|
57:
|
/ /
|
поиск в карте...
|
|
58:
|
auto
|
iPairlnN oC aseD ir
|
= d i r C a s e l n s e n s i t i v e . f in d (s trN a m e ln p u t);
|
59:
|
if(iP a irln N o C a s e D ir !=
|
d ir C a s e l n s e n s i t i v e . e n d ())
|
{
61:
|
cout
|
«
|
iP a irIn N o C a se D ir
|
- > firs t
|
62:
|
|
«
|
" ' s number
|
in th e
|
c a s e - i n s e n s i t i v e " ;
|
cout
|
«
|
" d ir e c t o r y
|
i s : " « iP airIn N o C aseD ir -> seco n d « endl
|
}
e l s e
{
6 6 :
|
cout
|
«
|
strN a m e In p u t«
|
" ' s number
|
not found ";
|
67:
|
cout
|
«
|
"in th e c a s e - i n s e n s i t i v e
|
d i r e c t o r y " « en d l;
|
6 8 :
|
}
|
|
|
|
|
|
|
69:
|
|
|
|
|
|
|
|
70:
|
/ / поиск
|
в
|
зависящей
|
от
|
регистра к ар те...
|
71:
|
auto iP airln C aseS en sD ir
|
=
|
d ir C a s e S e n s itiv e . f in d ( s tr N a m e ln p u t) ;
|
72:
|
if(iP a irln C a s e S e n s D ir
|
!=
|
d ir C a s e S e n s itiv e . e n d ())
|
{
74:
|
cout
|
< < iP a irIn C a se S e n sD ir - > first
|
75:
|
|
« " ' s
|
number in
|
th e
|
c a s e - s e n s i t i v e " ;
|
cout
|
« "
|
d ir e c t o r y
|
i s :
|
" « iP airInC aseS ensD ir->second
|
endl;
}
e l s e
{
|
Предоставление специального предиката сортировки
|
475
|
79:
|
cout « strNameInput«
|
s number was not found ";
|
|
cout « "in the case-sensitive directory"« endl;
}
82:
return 0;
84:}
Результат
Displaying contents of the case-insensitive map:
Jack -> 32435348
John -> 2345764
Sara -> 42367236
Displaying contents of the case-sensitive map:
Jack -> 32435348
John -> 2345764
Sara -> 42367236
Please enter a name to search:
> sara
Sara's number in the case-insensitive directory is: 42367236 sara's number was not found in the case-sensitive directory
Анализ
Рассматриваемый код содержит два каталога с одинаковым содержимым: один был создан с заданным по умолчанию предикатом сортировки s t d : : le ss< T > и зависящим от регистра оператором s t d : : s t r i n g : :o p e r a to r < , а другой — со структурой предиката P re d lg n o re C a s e (строки 17-27), сравнивающего две строки после преобразования их символов в нижний регистр. Вывод указывает, что при поиске в двух картах слова *s a r a '
независящей от регистра карте будет найдена запись S a ra , тогда как карта с предикатом по умолчанию неспособна найти эту запись.
ПРИМЕЧАНИЕ
В листинге 20.5 структура PredlgnoreCase может также быть классом, если для оператора operator () вы добавите ключевое слово public. Для компи лятора C++ структура родственна классу с открытыми по умолчанию членами и открытым наследованием.
Этот пример демонстрирует возможность использования предикатов для настройки поведения карты, а также то, что потенциально ключ может иметь любой тип, а програм мист способен предоставить предикат, определяющий поведение карты для этого типа. Обратите внимание на то, что предикат был структурой, реализовавшей оператор o p e r a t o r (). Но это вполне может быть класс. Такие объекты называются также объектами функций (function object) или функторами (functor). Более подробная информация по этой теме приведена на занятии 21, “Понятие объектов функций”.
476
|
ЗАНЯТИЕ 20. Классы карт библиотеки STL
|
|
ПРИМЕЧАНИЕ
|
Контейнер std: :map хорошо подходит для хранения пар “ключ-значение”,
|
;
|
|
|
позволяя искать значение, заданное по ключу. Карта действительно гаранти
|
|
|
|
рует лучшую производительность, чем вектор или список, когда дело доходит
|
|
|
|
|
до поиска. Но все же он замедляется при увеличении количества элементов.
|
I
|
|
|
Оперативная производительность карты, как говорят, имеет логарифмический
|
|
|
|
характер, т.е. она пропорциональна логарифму количества помещенных в карту
|
|
|
|
элементов.
|
|
|
|
Проще говоря, логарифмическая сложность означает, что при 10 ООО элемен-
|
j
|
|
|
тах поиск в таком контейнере, как std : :map или std: :set, осуществляется
|
j
|
|
|
вдвое медленней, чем при 100 элементах.
|
|
Несортированный вектор имеет линейную сложность при поиске, т.е. для 10 000 элементов он в 100 раз медленнее, чем для 100.
Do'stlaringiz bilan baham: |