Объекты функций STL. Предикаты и объекты функций

   
На этом шаге мы рассмотрим особенности предикатов и объектов функций.

   
Предикатом называется функция или объект функции, возвращающий логическое значение (или значение, преобразуемое
к bool). Однако не каждая функция, возвращающая логическую величину, является предикатом по правилам
STL. Иногда это приводит к весьма странным последствиям. Рассмотрим следующий пример:

//---------------------------------------------------------------------------

#include <vcl.h>
#include <iostream>
#include <iterator>
#include <list>
#include <algorithm>

#include <conio.h> //необходимо для getch()

#pragma hdrstop

//---------------------------------------------------------------------------

#pragma argsused
using namespace std;


std::string ToRus(const std::string &in)
{
  char *buff = new char [in.length()+1];
  CharToOem(in.c_str(),buff);
  std::string out(buff);
  delete [] buff;
  return out;
}

template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
  typename T::const_iterator pos;
  std::cout << ToRus(optcstr);
  for (pos=coll.begin(); pos!=coll.end(); ++pos) {
    std::cout <<*pos <<' ';
  }
  std::cout << std::endl;
}

class Nth {        // Объект функции возвращает true для n-го вызова
  private:
    int nth;       // Номер вызова, для которого следует вернуть true
    int count;     // Счетчик вызовов
  public:
    Nth (int n) : nth(n), count(0) {
    }
    bool operator() (int) {
        return ++count == nth;
    }
};


int main(int argc, char* argv[])
{
  list<int> coll;

  // Вставка элементов со значениями от 1 до 9
  for (int i=1; i<=9; ++i) {
      coll.push_back(i);
  }
  PRINT_ELEMENTS(coll,"Исходный список:\n");

  // Удаление третьего элемента
  list<int>::iterator pos;
  pos = remove_if(coll.begin(),coll.end(),  // Интервал
                  Nth(3));                  // Критерий удаления
  coll.erase(pos,coll.end());

  PRINT_ELEMENTS(coll,"Преобразованный список:\n");

  getch();
  return 0;
}

//---------------------------------------------------------------------------

Текст этого примера можно взять здесь.

   
Программа определяет объект функции Nth, который возвращает true для каждого n-го вызова.
Но если передать этот объект алгоритму remove_if(), выполняющему удаление всех элементов, для которых
унарный предикат возвращает true, вас ждет сюрприз:


Рис.1. Результат работы приложения

   
Из коллекции удаляются два элемента, третий и шестой. Дело в том, что обычная реализация алгоритма создает
внутреннюю копию предиката:

  template <class ForwIter, class Predicate> 
  Forwlter std::remove_if(ForwIter beg, ForwIter end, Predicate op)
  {
    beg = find_if(beg, end, op); 
    if (beg == end) { return beg;
    } else {
      ForwIter next = beg;
      return remove_copy_if(++next, end, beg, op);
    }
  }

   
Для поиска первого удаляемого элемента алгоритм использует find_if(), но затем для обработки оставшихся
элементов используется копия переданного предиката ор. Объект функции Nth возвращается к
прежнему состоянию и удаляет третий элемент из оставшихся (то есть шестой элемент коллекции),

   
Такое поведение не является ошибкой. Стандарт не ограничивает внутреннее копирование предиката в алгоритме.
Таким образом, для надежной работы алгоритмов стандартной библиотеки C++ не следует передавать объект
функции, поведение которого зависит от частоты его копирования или вызова. Иначе говоря, если унарный предикат
вызывается с одинаковыми аргументами, то он всегда должен возвращать один и тот же результат. Вызов не должен
изменять внутреннее состояние предиката, а копия предиката должна иметь точно такое же состояние, как оригинал.
Чтобы состояние предиката не изменялось при вызове функции, оператор () рекомендуется объявлять в виде
константной функции.

   
В принципе это странное поведение можно обойти и обеспечить нормальную работу алгоритма даже с такими
объектами функций, как Nth, без снижения быстродействия. Для этого достаточно исключить из реализации
remove_if() вызов find_if():

  template <class ForwIter, class Predicate> 
  Forwlter std::remove_if (ForwIter beg, ForwIter end, Predicate op)
  {
    while (beg != end && !op(*beg)) { 
      ++beg;
    } 
    if (beg == end) { return beg;
    } else {
      ForwIter next = beg;
      return remove_copy_if(++next, end, beg, op); 
    }
  }

   
Вероятно, реализацию remove_if() стоило бы изменить. В текущих реализациях эта проблема возникает
только с алгоритмом remove_if(). Если использовать алгоритм remove_copy_if(), все работает
нормально. Но если вы хотите, чтобы программа была действительно переносимой, никогда ие полагайтесь
на особенности реализации. Всегда объявляйте оператор вызова функции и предикаты как константные функции
классов.

   
На следующем шаге мы рассмотрим стандартные объекты функций.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий