Обработка сложных типов данных

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

Нет нужды перечислять все достоинства стандартной библиотеки STL, ставшей фактически очень важным расширением языка С++. Нельзя сказать, что STL является простой для понимания и использования, но тот программист, кто ее освоил и понял все возможности STL уже никогда не откажется от ее использования, разве только в пользу более мощного ее аналога. Если Вы еще чувствуете себя недостаточно уверенно в применении STL, воспользуйтесь книгой Николая Джосьютиса "С++ Стандартная библиотека". Одной этой книги будет достаточно для всестороннего изучения стандартной библиотеки STL.

Очень часто в примерах и описаниях стандартной библиотеки используются только простые типы данных. В реальных задачах простые типы данных скорее исключение, чем правило. Программист, начинающий работать с STL, зачастую испытывает трудности при переходе от простых примеров, приводимых в учебниках, к реальным задачам. Сложные типы данных также хорошо обрабатываются в STL, как и простые типы, однако в этом случае требуется их дополнительная организация, обусловленная требованиями контейнеров STL. Таких требований три:
1. Элемент контейнера должен точно и предсказуемо копироваться. Класс данных должен иметь копирующий конструктор. Контейнеры копируют объекты на входе и выходе, при занесении объекта в контейнер и при его выдаче из контейнера. Копирующий конструктор вызывается часто и от него зависит эффективность работы контейнера.
2. Элементы контейнера используют оператор присваивания при замене элементов. Класс данных должен иметь оператор присваивания.
3. Класс данных должен иметь деструктор для правильного уничтожения элементов контейнера.

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

Кроме указанных требований к объектам класса сложных типов данных почти всегда потребуется определить оператор < (меньше) для выполнения сортировки по одному из элементов данных, так как стандартный объект функции less<> не способен выполнить сортировку для не встроенных типов данных. То же самое касается оператора проверки на равенство. И в заключение, для некоторых контейнеров может потребоваться конструктор по умолчанию.

Обработка сложных типов данных алгоритмами STL может вызвать значительные временные издержки, в особенности при обработке больших массивов. В то же время возможности, заложенные в STL, позволяют простыми средствами добиться существенной экономии времени обработки, о чем будет рассказано далее.

В этой статье я хочу поделиться опытом организации сложных типов данных для их обработки с помощью STL, что поможет начинающим быстрей изучить библиотеку и избежать часто встречающихся ошибок.

В зависимости от конкретной задачи класс данных может содержать больше или меньше членов класса, все зависит от того, какие алгоритмы будут использоваться для решения задачи. Написать класс, который будет удовлетворять требованиям всех алгоритмов одинаково хорошо, сложно, он может оказаться перегруженным редко используемыми членами класса, например если в программе алгоритм поиска, то и оператор равенства в классе данных не нужен. Кроме того, сложные типы данных каждый раз содержат различный набор типов, что вообще делает написание такого класса практически неразрешимой задачей. Поэтому удачным оказался опыт использования некоторой заготовки класса данных, которая подгоняется под реальную задачу. В классе должны присутствовать некоторые обязательные элементы и необязательные, но часто используемые алгоритмами, например конструктор-копировщик это обязательный элемент, а перегруженный оператор "меньше" необязательный, однако он используется столь часто, что его включение в класс становиться почти обязательным.
Рассмотрим вполне реальный набор разнородных данных, которые в зависимости от вида графика следует сортировать по определенному параметру.

DWORD64 serial; //серийный номер датчика
double temperature; //измеренная температура
CTime time; //время измерения
Color clr; //цвет графика
long err; //код ошибки, признак правильного измерения - TRUE

В этом примере набор данных может сортироваться по времени измерения, по номеру датчика и по измеренным температурам, также может понадобиться сортировка одновременно по нескольким параметрам, по номеру датчика и температуре измерений этого датчика, например. Пример наглядно иллюстрирует, сказанное выше.

Для наборов подобных данных, проще создать класс-заготовку подходящий для большинства алгоритмов, используемых в программе, а для особых случаев или одноразового применения какого-либо алгоритма написать предикат или объект функции(функтор) вне класса. Здесь следует внести ясность в понимание, что такое предикат и что такое объект функции, что между ними общего и в чем их различие.

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

Предикат – функция возвращающая логическое значение (bool). Возвращаемое значение предиката должно зависеть только от значения параметров. Такие функции еще называют чистыми.
Предикаты бывают унарные и бинарные. Унарный предикат проверяет свойство одного параметра, бинарный сравнивает свойство двух параметров.

Объектом функции или функтором называется объект класса для которого определен оператор "круглые скобки". Все, что должен выполнять объект функции заключается в тело оператора "круглые скобки". Объект функции – чистая абстракция. В соответствии с концепцией унифицированного программирования все, что ведет себя как функция, является функцией. Определив для объекта оператор "круглые скобки", получаем возможность его вызова как функции, потому, что объект имеет круглые скобки и ему можно передавать параметры. Для компилятора вид объекта функции ничем не отличается от вида функции.
Например, имеем класс:

Class A
{
 .........
 BOOL operator () (ar1,ar2……) const;
};

Теперь объекты этого класса ведут себя как функции, их можно вызывать как функцию:

A obj;
obj(ar1,ar2,…);

Каковы преимущества объекта функции по сравнению с обычной функцией? Объект функции обладает весьма существенными свойствами по сравнению с функцией:

• Объект функции перед вызовом можно инициализировать, задавая исходное состояние, таким образом один и тот же объект функции может в разные моменты времени находится в разных исходных состояниях. Исходное состояние объекта функции можно изменять и после создания объекта класса, вызывая функции класса, или присваивая значения открытым членам класса, которые будут использоваться объектом функции.
• Каждому объекту функции соответствует свой тип. Объект функции можно передавать как параметр шаблона, тем самым, передавая функциональное поведение.
• Объекты функций часто работают быстрей обычной функции.

 

Библиотека STL содержит два шаблонных класса, unary_function и binary_function, которые предназначены для создания объектов функции, соответственно унарных и бинарных. Объекты функций используются в алгоритмах вместо предикатов, значительно расширяя их возможности и во многих случаях ускоряя их работу. Производные классы и операторы "круглые скобки" для этих классов строятся по определенному шаблону:

Унарный класс и оператор:

struct unary_function{typedef Arg argument_type; typedef Result result_type; };
result_type operator()(const argument_type&) const;

 

struct unary_function{typedef Arg argument_type; typedef Result result_type; };
result_type operator()(const argument_type&) const;

 

Бинарный класс и оператор:

struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };
result_type operator()( const first_argument_type&,const second_argument_type& ) const;

 

Реальный пример бинарного объекта функции выглядит так:

 

struct DataCompSerial : public std::binary_function <CData,CData, BOOL>
{

    BOOL operator () (const CData& dt1, const CData& dt2) const
   {
      return dt1.serial == dt2.serial;
   }

};

 

Структура может быть пребразована в полноценный класс содержащий конструктор для инициализации переменных:

class DataCompSerial : public std::binary_function <CData,CData, BOOL>
{
  private:
    int value;

 public:
    DataCompSerial(int v):value(v) {} //конструктор

    BOOL operator () (const CData& dt1, const CData& dt2) const
    {
       if (value == 100)
       …что-то делаем
       return dt1.serial == dt2.serial;
    }

};

 

Теперь объект функции может быть передан в алгоритм с инициализацией переменной value в конструкторе, например для поиска величины равной dt.serial:

CData dt = {0}; //константа сравнения
dt.serial = 0x1234abcd;

find_if(v.begin(),v.end(),bind2nd(DataCompSerial(10),dt));

 

Примечание
bind2nd() – функциональный адаптер.

Функциональные адаптеры

Функциональные адаптеры – объекты, изменяющие функционирование объектов функций. Функциональные адаптеры сами являются объектами функций. Существует четыре функциональных адаптера:

Функциональные адаптеры – объекты, изменяющие функционирование объектов функций. Функциональные адаптеры сами являются объектами функций. Существует четыре функциональных адаптера:

bind1st(op, value) – преобразует бинарный предикат op в унарный, передавая value в качестве первого параметра в бинарный предикат op.

bind2nd(op, value) – преобразует бинарный предикат op в унарный, передавая value в качестве второго параметра в бинарный предикат op.

not1(op) – выполняет над кодом возврата унарного предиката операцию логического отрицания.

not2(op) – выполняет над кодом возврата бинарного предиката операцию логического отрицания.

Когда они нужны? Например, имеется бинарный предикат проверяющий две величины на равенство, где-то он использовался в программе раньше. Возникла потребность использовать алгоритм find_if для поиска определенной величины. Алгоритм требует унарного предиката, но его можно не создавать, а использовать тот же бинарный предикат с функциональным адаптером, как было показано в примере выше.

Пример класса данных

Ниже приведен пример класса данных, который содержит кроме данных еще и два оператора для часто выполняющихся алгоритмов сортировки и поиска по времени измерения. Для обработки по другим элементам данных написаны несколько простых объектов функций не требующих пояснений. Пример поиска данных по номеру датчика.

CData dt;
dt.serial = getSerial(n); //инициализация константы поиска
pos = find_if(v.begin(), v.end(),bind2nd(DataCompSerial(),dt));

#pragma once
using namespace std;
using namespace Gdiplus; 

 

class CData

{

   public:

   //конструктор

   CData():serial(0),err(0),temperature(0.0)

   {

      time = CTime::GetCurrentTime();

      clr.SetValue(0xff000000);

    } 

 

   ~CData() {};

 

//конструктор копировщик

CData(const CData & data) { *this = data; }

 

//данные

DWORD64 serial; //серийный номер датчика

double temperature; //измеренная температура

CTime time; //время измерения

Color clr; //цвет графика

long err; //признак правильного измерения - TRUE

 

//оператор присваивания

const CData & operator = (const CData & data)

{

  if(this != &data)

  {

    serial = data.serial ; 

    temperature = data.temperature ; 

    time = data.time ; 

    clr = data.clr ; 

    err = data.err ; 

  } 

  return *this;

} 

 

//оператор меньше

bool operator < (const CData& data) const

{

   return time < data.time ;

}

 

//оператор сравнения по времени измерения

bool operator == (const CData& data) const

{

   return time == data.time ;

}

 

};

 

struct DataCompSerial : public std::binary_function <CData,CData, BOOL>

{

  BOOL operator () (const CData& dt1, const CData& dt2) const

  {

     return dt1.serial == dt2.serial;

  }

};

 

struct DataCompColor : public std::binary_function <CData,CData, BOOL>

{

  BOOL operator () (const CData& dt1, const CData& dt2) const

  {

    return dt1.clr.GetValue() == dt2.clr.GetValue();

  }

};

 

struct DataSortSerial : public std::binary_function <CData,CData, BOOL>

{

  BOOL operator () (const CData& dt1, const CData& dt2) const

  {

    return dt1.serial < dt2.serial;

  }

};

 

//удаление дубликатов с точностью 0,5 градуса

struct DeleteDubl : public std::binary_function <CData,CData, BOOL>

{

  BOOL operator () (const CData& dt1, const CData& dt2) const

  {

    return abs(dt1.temperature - dt2.temperature) < 0.5;

  }

};

 

Пример поиска данных по номеру датчика.

 

CData dt;

dt.serial = getSerial(n); //инициализация константы поиска

pos = find_if(v.begin(), v.end(),bind2nd(DataCompSerial(),dt));

 

Уменьшения времени выполнения алгоритма при обработке сложных типов данных

Все прекрасно, пока в классе количество данных измеряется единицами и число элементов контейнера невелико. Но, как только данных становиться много, десятки элементов и размер контейнера увеличивается до тысяч и сотен тысяч элементов начинает сказываться и весьма сильно время, затрачиваемое на работу копирующего конструктора. Во многих источниках отмечается влияние копирующего конструктора, но нигде не удалось найти какого-либо решения для снижения этого влияния. Хотя простое решение лежит на поверхности, например можно сделать так:

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

 

Что это дает?

Должно уменьшиться время копирования, поскольку память, отводимая на один указатель существенно меньше всего набора данных. Никаких побочных эффектов возникать не должно, поскольку вектор указателей формируется из уже заполненного исходного контейнера.

Какие издержки?

Дополнительная память под вектор указателей, равная числу элементов исходного вектора. Однако в процентном отношении к исходному контейнеру ее объем может быть не слишком велик, все зависит от размера элемента исходного вектора.

Простая проверка на алгоритме сортировки для данных из десяти элементов показала 35% уменьшение времени обработки. Результат впечатляющий. Желающие проверить и попробовать разные варианты могут скачать тестовый проект.

Предупреждение.
Измерения проводить в режиме realease, в debug результат измерений искажается. 

Литература.

Николай Джосьютис "С++ Стандартная библиотека"
Скот Мейерс "Эффектвное использование STL"

 

Главная

В раздел