этом разделе.
21.8. Сортировка и поиск
Часто мы хотим упорядочить данные. Мы можем добиться этого, используя структуры, поддерживающие порядок, такие как map и set, или выполняя сортировку. Наиболее распространенной и полезной операцией сортировки в библиотеке STL является функция sort(), которую мы уже несколько раз использовали. По умолчанию функция sort() в качестве критерия сортировки использует оператор <, но мы можем задавать свои собственные критерии.
template<class Ran> void sort(Ran first, Ran last);
template<class Ran,class Cmp> void sort(Ran first,Ran last,Cmp cmp);
В качестве примера сортировки, основанной на критерии, определенном пользователем, покажем, как упорядочить строки без учета регистра.
struct No_case { // lowercase(x) < lowercase(y)
bool operator()(const string& x, const string& y) const
{
for (int i = 0; i<x.length(); ++i) {
if (i == y.length()) return false; // y<x
char xx = tolower(x[i]);
char yy = tolower(y[i]);
if (xx<yy) return true; // x<y
if (yy<xx) return false; // y<x
}
if (x.length()==y.length()) return false; // x==y
return true; // x<y (в строке x меньше символов)
}
};
void sort_and_print(vector<string>& vc)
{
sort(vc.begin(),vc.end(),No_case());
for (vector<string>::const_iterator p = vc.begin();
p!=vc.end(); ++p)
cout << *p << 'n';
}
Как только последовательность отсортирована, нам больше не обязательно перебирать все элементы с самого начала контейнера с помощью функции find(); вместо этого можно использовать бинарный поиск, учитывающий порядок следования элементов. По существу, бинарный поиск сводится к следующему.
Предположим, что мы ищем значение x; посмотрим на средний элемент.
• Если значение этого элемента равно x, мы нашли его!
• Если значение этого элемента меньше x, то любой элемент со значением х находится справа, поэтому мы просматриваем правую половину (применяя бинарный поиск к правой половине).
• Если значение этого элемента больше x, то любой элемент со значением х находится слева, поэтому мы просматриваем левую половину (применяя бинарный поиск к левой половине).
• Если мы достигли последнего элемента (перемещаясь влево или вправо) и не нашли значение x, то в контейнере нет такого элемента.
Для длинных последовательностей бинарный поиск выполняется намного быстрее, чем алгоритм find() (представляющий собой линейный поиск). Алгоритмы бинарного поиска в стандартной библиотеке называются binary_search() и equal_range(). Что мы понимаем под словом “длинные”? Это зависит от обстоятельств, но десяти элементов обычно уже достаточно, чтобы продемонстрировать преимущество алгоритма binary_search() над алгоритмом find(). На последовательности, состоящей из тысячи элементов, алгоритм binary_search() работает примерно в 200 раз быстрее, чем алгоритм find(), потому что он имеет сложность O(log2N) (см. раздел 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 пары (