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

21.7.4. Алгоритм copy_if

Алгоритм copy выполняет копирование без каких-либо условий. Алгоритм unique_copy отбрасывает повторяющиеся соседние элементы, имеющие одинаковые значения. Третий алгоритм копирует только элементы, для которых заданный предикат является истинным.

 template<class In,class Out,class Pred>
 Out copy_if(In first,In last,Out res,Pred p)
  // копирует элементы, удовлетворяющие предикату
 {
  while (first!=last) {
  if (p(*first)) *res++ = *first;
  ++first;
  }
  return res;
 }

Используя наш объект-функцию Larger_than из раздела 21.4, можем найти все элементы последовательности, которые больше шести.

 void f(const vector<int>& v)
  // копируем все элементы, которые больше шести
 {
  vector<int> v2(v.size);
  copy_if(v.begin,v.end,v2.begin,Larger_than(6));
  // ...
 }

Из-за моей ошибки этот алгоритм выпал из стандарта 1998 ISO Standard. В настоящее время эта ошибка исправлена, но до сих пор встречаются реализации языка С++, в которых нет алгоритма copy_if. В таком случае просто воспользуйтесь определением, данным в этом разделе.

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(log₂N) (см. раздел 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). Как правило, это необходимо, когда элементы контейнера представляют собой объекты, содержащие больше информации, чем просто ключ, когда в контейнере содержатся несколько элементов с одинаковыми ключами или когда нас интересует, какой именно элемент удовлетворяет критерию поиска.