Для длинных последовательностей бинарный поиск выполняется намного быстрее, чем алгоритм
find()
(представляющий собой линейный поиск). Алгоритмы бинарного поиска в стандартной библиотеке называются
binary_search()
и
equal_range()
. Что мы понимаем под словом “длинные”? Это зависит от обстоятельств, но десяти элементов обычно уже достаточно, чтобы продемонстрировать преимущество алгоритма
binary_search()
над алгоритмом
find()
. На последовательности, состоящей из тысячи элементов, алгоритм
binary_search()
работает примерно в 200 раз быстрее, чем алгоритм
find()
, потому что он имеет сложность O(log
2N) (см. раздел 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]
) по одной в строке.
