Программирование. Принципы и практика использования C++ Исправленное издание, стр. 301

Для длинных последовательностей бинарный поиск выполняется намного быстрее, чем алгоритм

find()

(представляющий собой линейный поиск). Алгоритмы бинарного поиска в стандартной библиотеке называются

binary_search()

equal_range()

. Что мы понимаем под словом “длинные”? Это зависит от обстоятельств, но десяти элементов обычно уже достаточно, чтобы продемонстрировать преимущество алгоритма

binary_search()

над алгоритмом

find()

. На последовательности, состоящей из тысячи элементов, алгоритм

binary_search()

работает примерно в 200 раз быстрее, чем алгоритм

find()

, потому что он имеет сложность O(log₂N) (см. раздел 21.6.4).

Алгоритм

binary_search

имеет два варианта.

template<class Ran, class T>

bool binary_search(Ran first,Ran last,const T& val);

template<class Ran,class T,class Cmp>

bool binary_search(Ran first,Ran last,const T& val,Cmp cmp);

Эти алгоритмы требуют, чтобы их входные последовательности были упорядочены. Если это условие не выполняется, то могут возникнуть такие интересные вещи, как бесконечные циклы. Алгоритм

binary_search()

просто сообщает, содержит ли контейнер заданное значение.

void f(vector<string>& vs) // vs упорядочено

{

if (binary_search(vs.begin(),vs.end(),"starfruit")) {

// в контейнере есть строка "starfruit"

}

// ...

}

Итак, алгоритм

binary_search()

— идеальное средство, если нас интересует, есть заданное значение в контейнере или нет. Если нам нужно найти этот элемент, мы можем использовать функции

lower_bound()

upper_bound()

или

equal_range()

(разделы 23.4 и Б.5.4). Как правило, это необходимо, когда элементы контейнера представляют собой объекты, содержащие больше информации, чем просто ключ, когда в контейнере содержатся несколько элементов с одинаковыми ключами или когда нас интересует, какой именно элемент удовлетворяет критерию поиска.

Задание

После выполнения каждой операции выведите содержание вектора на экран.

1. Определите структуру

struct Item { string name; int iid; double value; /* ... */ };

, создайте контейнер

vector<Item> vi

и заполните его десятью строками из файла.

2. Отсортируйте контейнер

vi

по полю

name

3. Отсортируйте контейнер

vi

по полю

iid

4. Отсортируйте контейнер

vi

по полю

value

; выведите его содержание на печать в порядке убывания значений (т.е. самое большое значение должно быть выведено первым).

5. Вставьте в контейнер элементы

Item("horse shoe",99,12.34)

Item("Canon S400",9988,499.95)

6. Удалите два элемента Item из контейнера

vi

, задав поля

name

7. Удалите два элемента Item из контейнера

vi

, задав поля

iid

8. Повторите упражнение с контейнером типа

list<Item>

, а не

vector<Item>

Теперь поработайте с контейнером

map

1. Определите контейнер

map<string,int>

с именем

msi

2. Вставьте в него десять пар (имя, значение), например

msi["lecture"]=21

3. Выведите пары (имя, значение) в поток

cout

в удобном для вас виде.

4. Удалите пары (имя, значение) из контейнера

msi

5. Напишите функцию, считывающую пары из потока

cin

и помещающую их в контейнер

msi

6. Прочитайте десять пар из потока ввода и поместите их в контейнер

msi

7. Запишите элементы контейнера

msi

в поток

cout

8. Выведите сумму (целых) значений из контейнера

msi

9. Определите контейнер

map<int,string>

с именем

mis

10. Введите значения из контейнера

msi

в контейнер

mis

; иначе говоря, если в контейнере

msi

есть элемент

("lecture",21

), то контейнер mis также должен содержать элемент (

21,"lecture"

11. Выведите элементы контейнера

mis

в поток

cout

Несколько заданий, касающихся контейнера

vector

1. Прочитайте несколько чисел с плавающей точкой (не меньше 16 значений) из файла в контейнер

vector<double>

с именем

vd

2. Выведите элементы контейнера

vd

в поток

cout

3. Создайте вектор

vi

типа

vector<int>

с таким же количеством элементов, как в контейнере

vd

; скопируйте элементы из контейнера

vd

в контейнер

vi

4. Выведите в поток

cout

пары (

vd[i]

vi[i]

) по одной в строке.