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

  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.

7. Удалите два элемента Item из контейнера vi, задав поля iid.

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

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

1. Определите контейнер map с именем msi.

2. Вставьте в него десять пар (имя, значение), например msi["lecture"]=21.

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

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