Читаем Программирование полностью

template void sort(Ran first, Ran last);

template 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

      if (i == y.length()) return false;      // y

      char xx = tolower(x[i]);

      char yy = tolower(y[i]);

      if (xx

      if (yy

    }

    if (x.length()==y.length()) return false; // x==y

    return true;   // x

  }

};

void sort_and_print(vector& vc)

{

  sort(vc.begin(),vc.end(),No_case());

  for (vector::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(log₂N) (см. раздел 21.6.4).

Алгоритм binary_search имеет два варианта.

template

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

template

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

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

void f(vector& 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 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.