Чтение онлайн

на главную - закладки

Жанры

C++. Сборник рецептов

Когсуэлл Джефф

Шрифт:

Пример 6.7. Использование собственного функтора сортировки

#include <iostream>

#include <map>

#include <string>

using namespace std;

class Person {

 friend class PersonLessThan;

public:

 Person(const string& first, const string& last) :

lastName_(last), firstName_(first) {}

 // ...

 string getFirstName const {return(firstName_);}

 string getLastName const {return(lastName_);}

private:

 string lastName_;

 string firstName_;

};

class PersonLessThan {

public:

 bool operator(const Person& per1,

const Person& per2) const {

if (per1.lastName_ < per2. lastName_) //
Сравнить фамилии,

return(true); // а затем

else if (per1.lastName_ == per2.lastName_) // имена

return(per1.firstName_ < per2.firstName_);

else

return(false);

 }

};

int main {

 map<Person, string, PersonLessThan> personMap;

 Person per1("Billy", "Silly"),

per2("Johnny", "Goofball"),

per3("Frank", "Stank"),

реr4("Albert", "Goofball");

 personMap[per1] = "cool";

 personMap[per2] = "not cool";

 personMap[per3] = "not cool";

 personMap[per4] = "cool";

 for (map<Person, string, PersonLessThan>::const_iterator p =

personMap.begin; p != personMap.end; ++p) {

cout << p->first.getFirstName << " " << p->first.getLastName

<< " is " << p->second << endl;

 }

}

map
это прекрасный способ хранить пары ключ/значение. После того как вы поймете поведение его частей, таких как
operator[]
и хранение данных (в виде объектов
pair<Key, Value>
),
map
предоставит простоту в использовании и высокую производительность.

Смотри также

Рецепт 6.7.

6.7. Использование хеш-контейнеров

Проблема

Требуется сохранить ключи и значения, обеспечив постоянное время доступа к элементам, и не требуется хранения элементов в упорядоченном виде.

Решение

Используйте один из связанных с хешами контейнеров —

hash_map
или
hash_set
.
Однако помните, что они не входят в число стандартных контейнеров, определяемых стандартом С++, а представляют собой расширения, включаемые большинством реализаций стандартной библиотеки. Пример 6.8 показывает, как использовать
hash_set
.

Пример 6.8. Хранение строк в hash_set

#include <iostream>

#include <string>

#include <hash_set>

int main {

 hash_set<std::string> hsString;

 string s = "bravo";

 hsString.insert(s);

 s = "alpha";

 hsString.insert(s);

 s = "charlie";

 hsString.insert(s);

 for (hash set<string>::const_iterator p = hsString.begin;

p != hsString.end; ++p)

cout << *p << endl; // заметьте, что здесь не гарантируется хранение

// в упорядоченном виде

}

Обсуждение

Контейнеры, основанные на хешах, — это популярные во всех языках структуры данных, и прискорбно, что стандарт C++ не требует их реализации. Однако если требуется использовать хеш-контейнер, то не все потеряно: высока вероятность, что используемая вами реализация стандартной библиотеки содержит

hash_map
и
hash_set
, но тот факт, что они не стандартизованы, означает, что их интерфейсы могут отличаться от одной реализации стандартной библиотеки к другой. Я опишу хеш-контейнеры, которые поставляются в составе реализации стандартной библиотеки STLPort.

STLPort — это свободно распространяемая переносимая реализация стандартной библиотеки, существующая уже довольно длительное время и предоставляющая хеш-контейнеры. При использовании другой библиотеки интерфейс может быть другим, но общая идея будет той же самой.

Главной особенностью хеш-контейнеров (называемых во многих книгах по ассоциативными хеш-контейнерами) является то, что они в общем случае предоставляют постоянное время поиска, вставки и удаления элементов, а в худшем случае эти операции имеют линейное время. Ценой постоянного времени выполнения этих операций является то, что в хеш-контейнере они хранятся в неупорядоченном виде, как в

map
.

Посмотрите на пример 6.8. Использование хеш-контейнера (в данном случае

hash_set
) довольно просто — объявите его как большинство других контейнеров и начните вставлять в него элементы.

hash_set<string> hsString; // hash_set строк

string s = "bravo";

hsString.insert(s); // Вставка копии s

Использование

hash_map
аналогично, за исключением того, что требуется, как минимум, указать типы данных используемых ключей и значений. Это аналогично
map
.

Поделиться:
Популярные книги

Идеальный мир для Лекаря 27

Сапфир Олег
27. Лекарь
Фантастика:
аниме
фэнтези
5.00
рейтинг книги
Идеальный мир для Лекаря 27

Идеальный мир для Лекаря 15

Сапфир Олег
15. Лекарь
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Лекаря 15

Князь Мещерский

Дроздов Анатолий Федорович
3. Зауряд-врач
Фантастика:
альтернативная история
8.35
рейтинг книги
Князь Мещерский

Ты нас предал

Безрукова Елена
1. Измены. Кантемировы
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Ты нас предал

Бракованная невеста. Академия драконов

Милославская Анастасия
Фантастика:
фэнтези
сказочная фантастика
5.00
рейтинг книги
Бракованная невеста. Академия драконов

Чужая семья генерала драконов

Лунёва Мария
6. Генералы драконов
Фантастика:
фэнтези
5.00
рейтинг книги
Чужая семья генерала драконов

Истребители. Трилогия

Поселягин Владимир Геннадьевич
Фантастика:
альтернативная история
7.30
рейтинг книги
Истребители. Трилогия

Любовь Носорога

Зайцева Мария
Любовные романы:
современные любовные романы
9.11
рейтинг книги
Любовь Носорога

Курсант: Назад в СССР 10

Дамиров Рафаэль
10. Курсант
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Курсант: Назад в СССР 10

Прорвемся, опера! Книга 2

Киров Никита
2. Опер
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Прорвемся, опера! Книга 2

Газлайтер. Том 2

Володин Григорий
2. История Телепата
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Газлайтер. Том 2

Камень. Книга пятая

Минин Станислав
5. Камень
Фантастика:
боевая фантастика
6.43
рейтинг книги
Камень. Книга пятая

Попаданка в академии драконов 2

Свадьбина Любовь
2. Попаданка в академии драконов
Любовные романы:
любовно-фантастические романы
6.95
рейтинг книги
Попаданка в академии драконов 2

Камень. Книга 4

Минин Станислав
4. Камень
Фантастика:
боевая фантастика
7.77
рейтинг книги
Камень. Книга 4