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

21.8. Сортировка и поиск

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';

}

Предположим, что мы ищем значение x; посмотрим на средний элемент.

• Если значение этого элемента равно x, мы нашли его!

• Если значение этого элемента меньше x, то любой элемент со значением х находится справа, поэтому мы просматриваем правую половину (применяя бинарный поиск к правой половине).

• Если значение этого элемента больше x, то любой элемент со значением х находится слева, поэтому мы просматриваем левую половину (применяя бинарный поиск к левой половине).

• Если мы достигли последнего элемента (перемещаясь влево или вправо) и не нашли значение x, то в контейнере нет такого элемента.

Алгоритм 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);

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

{

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

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

  }

  // ...

}

Задание

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

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 пары (