вівторок, 15 березня 2011 р.

Функтори та функціональні адаптери STL

Функтором називається об'єкт, для якого перевизначений оператор () дужки.

Переваги:

  • Веде себе більш розумно, тому що має стан
  • Має певний тип і об'єкт можна передати функції шаблону
  • Зазвичай працює швидше вказівника на функцію.
Предикат - функція, або об'єкт функції, що повертає логічне значення. Хоча не кожна функція, що повертає логічну величину є предикатом по правилам STL.

Стандартні об'єкти функцій:

  • negate
  • plus
  • minus
  • multiplies
  • divides
  • modulus
  • (not)equal_to
  • less
  • greater
  • logical_not/and/or

Функціональний адаптер
- об'єкт, що дозволяє комбінувати об'єкти функцій один з одним або з спеціальними функціями. Теж оголошуються в файлі functional.

Стандартні функціональні адаптери:

  • bind1st(op, value)
  • bind2nd(op, value)
  • not1(op)
  • not2(op)
Детальний опис алгоритмів можна знайти в книзі Nicolai M.Josuttis The C++ Standard, Chapter 8. STL Function Objects.

неділю, 15 березня 2009 р.

Класифікація алгоритмів STL

Класифікація алгоритмів:

Cуфікс _if - використовується при наявності двох схожих форм алгоритму з однаковою кількітю параметрів. Версія без суфіксу використовується при передачі значення, аверсія з суфіксом _if при передачі функції, або об'єкту функції. Якщо ж версія алгоритму відрізняється додатковим параметром - вона зберігає за собою попереднє ім'я, тобто вживається без суфіксу.

Cуфікс _сopy означає, що алгоритм не тільки обробляє елементи, а й копіює їх в інтервал, який приймає. Наприклав reverse() переставляє елементи в зворотньому порядку, а reverse_sopy() копіює елементи в інтервал в зворотньому напрямку.

Алгоритми поділяються на групи:

  • не модифікуючі: for_each, count, max/min_element, search, find
  • модифікуючі: for_each, copy, merge, fill, replace
  • алгоритми видалення: remove, remove_if, remove_copy_if, unique
  • алгоритми перестановки: reverse, rotate, random_shuffle, partition, stable_partition
  • алгоритми сортування: sort, stable_sort, partial_sort, partition, stable_partition, make_heap, push/pop_heap, sort_heap
  • алгоритми впорядкованих інтервалів: binary_search, lower/upper_bound, equal_range, merge, set_difference
  • числові алгоритми: accumulate, inner_product, adjacent_difference, partial_sum

Детальний опис алгоритмів можна знайти в книзі Nicolai M.Josuttis The C++ Standard, Chapter 9 Algorithms STL.

вівторок, 3 березня 2009 р.

Оператори ->* , .*

Якось я захотів створити вказівник на функцію класу, і в залежності від певних обставин присвоювати йому вказівники на інші функції цього ж класу, для того, щоб при звернені до цього вказівника викликалась потрібна мені (залежно від обставин) функція. Звісно ж без знання цих операторів у мене нічого не вийшло. Дивно, що у багатьох авторитетних книжках по C++ про це не написано. Хочу звернути увагу, що ->* це не два окремих оператори, а один, так само як і .* Стрілочка-зірочка та крапочка-зірочка - окремі визначені оператори C++.

Ось простенький приклад:



#include < iostream>
using namespace std;
class MyClass
{
public:
MyClass(){}
~MyClass(){}

typedef void (MyClass:: *MY_FUNC_PTR)(int val);
// екземпляр вказівника на функцію класу
MY_FUNC_PTR stateFuncPtr;

void stateWaitFunc(int val)
{
cout < < val < < ". State WAITING function()" < < endl;
}
void stateDoFunc(int val)
{
cout < < val < < ". State DOING function()" < < endl;
}
void someFunk()
{
// присвоюємо вказівник на stateDoFunc функцію
stateFuncPtr = &MyClass::stateDoFunc;
// виклик функції stateDoFunc шляхом звертання до нашого вказівника
(this->*stateFuncPtr)(1);
// присвоюємо вказівник на stateWaitFunc функцію
stateFuncPtr = &MyClass::stateWaitFunc;
// виклик функції stateWaitFunc шляхом звертання до вказівника
(this->*stateFuncPtr)(2);
}
};

int main()
{
MyClass m;
m.someFunk();
// присвоюємо вказівник на stateDoFunc функцію (зовні класу)
m.stateFuncPtr = &MyClass::stateDoFunc;
// виклик функції stateDoFunc шляхом звертання до вказівника
(m.*m.stateFuncPtr)(3);
return 0;
}

Матеріал взято з власного наступання на граблі.

Узагальнення ітераторів

Категорії ітераторів:

Категорія - Можливості - Підтримка

Ітератор вводу - читання в прямому напрямку - Потоковий Ітератор вводу.

Ітератор виводу - Запис в прямому напрямку - Потоковий Ітератор виводу, ітератор вставки.

Прямий ітератор  - Читання і запис в прямому напрямку

Двонаправлений ітератор - Читання і запис в оберненому напрямках -list, map, mulimap, set, multiset.

Ітератордовільного доступу - Читання і запис з довільним доступом - vector, deque, string, array

Ітераторні адаптери:

Обернені ітератори - адаптери, що перевизначають оператори ++ та -- так щоб пошук виконувався в оберненому порядку.

Ітератори вставки - адаптер, що перетворює присвоєння нового значення у вставку нового значення. Бувають: Кінцеві (додає нове значення в кінець контейнера викликом функції push_back()), Початкові (вставляє нове значення в початок контейнера викликом функції push_front()), Загальні (на основі функції insert()).

Потокові ітератори - адаптер, що використовує поток в якості джерела або приймача алгоритму. Потокові ітератопи виводу записують значення що присвоюється у вихідний потік даних. Потокові ітератопи вводу читають елементи з вхідного потоку даних.

Цікавий приклад потокових ітераторів:

Програма читає слова із стандартного потоку вводу і виводить їх у відсортованому порядку виключаючи дублікати.



#include < iostream>
#include < vector>
#include < string>
#include < algorithm>

using namespace std;

int main()
{
vector < string> coll;

// читання слів з вхідного потоку даних
copy (istream_iterator < string> (cin), // початок джерела
istream_iterator < string> (), // кінець джерела
back_inserter(coll)); // приймач

sort (coll.begin(), coll.end());

unique_copy(coll.begin(), coll.end(), // джерело
ostream_iterator < string> (cout, "\n"));// приймач
}


Матеріал взято із книги Nicolai M.Josuttis The C++ Standard Library

четвер, 19 лютого 2009 р.

Трошки про Шаблони

Шаблони - це сімейство з однаковою поведінкою без конкретизації типу. При використанні шаблонів цей тип передається у вигляді аргументу або проміжно.
Ось типовий приклад:

template < typename T>
inline const T& max(const T& a, const T& b)
{
return a < b : b ? a;
}

Нетипізовані параметри шаблонів
Нетипізований параметр вважається частиною визначення типу.
Наприклад шаблон стандартного класу bitset < > отримує кількість бітів. Зверніть увагу, що ці бітові поля відносяться до різних типів і їх не можна присвоювати один одному:
bitset < 32> flags32;
bitset < 50> flags50;
Параметри по замовчуванню
Наступний фрагмент дозволяє оголосити об'єкти класу MyClass з одним, або двома параметрами:

template < typename T, typename Container = vector< T> >
class MyClass;

MyClass < int> myClass;
MyClass < int, vector< int> > myClass2;

Ключове слово typename
Слово означає, що наступний за ним ідентифікатор означає тип:

template < class T>
class MyClass {
typename T::SubType* ptr;
...
};

В даному випадку слово typename означає, що SubType є підтипом класу T, відповідно ptr - показчик на тип T::SubType. Без typename ідентифікатор SubType інтерпритується як статичний член класу і рядок сприймається як операція множення значення SubType класу T на значення ptr; Але в даному випадку любий тип який буде підставлений шаблону повинен мати внутрішній тип SubType. SubType може бути як класом оголошеним в середині іншого, так і простом typedef-ом.

Шаблонні функції класів
Такі функції не можуть бути віртуальними і мати параметри по замовчуванню!

class MyClass {
...
template < class T>
void f(T);
};

Шаблон MyClass::f оголошує набір функцій з параметром довільного типу, при умові що цей тип підтримує всі операції, які використовуються в f();
Дана можливість часто використовується для автоматичного приведення типів в класах шаблонів. Наприклад в наступному визначенні аргумент x функції assign() повинен точно відповідати типу об"єкта, для якого він викликається:

template < class T>
class MyClass {
private:
T value;
public:
void assign(const MyClass< T>& x) {
value = x.value; // тип x повинен відповідати типові *this
}
};

Зверніть увагу, використання шаблону з іншим типом при виклику assign() являється помилкою навіть в тому випадку якщо між типами виконується автоматичне приведення:

void f()
{
MyClass < double> b;
MyClass < int> i;
d.assign(b); // OK
d.assign(i); // Помилка: i відноситься до до типу MyClass
// в даному випадку обов"язковим є MyClass
}

Оголошення іншого шаблону у функції дозволяє обійти вимогу співпадіння типів:

template < class T>
class MyClass {
private:
T value;
public:
template < class X>
void assign(const MyClass< X>& x) {
value = x.getValue();
}
T getValue() const {
return value;
}
...
};

тепер функція f() є вірною.
Оскільки тип аргументу x не є типом *this, нам довелося додати функцію getValue() для доступу до приватної змінної.

Шаблонний конструктор використовуються для забезпечення неявних приведень типів при копіюванні об"єктів, але майте на увазі, шаблонний конструктор не заміняє стандартний конструктор копіювання. При точному співпадінні типів буде викликаний стандартний конструктор копіювання:

template < class T>
class MyClass {
public:
// Шаблонний конструктор з автоматичним приведенням тиу
template < class X>
MyClass(const MyClass< X>& x);
};
void f()
{
MyClass < double> xd;
...
MyClass < double> xd2(xd); // Стандартний конструктор копії
MyClass < int> xi(xd); // Шаблонний конструктор
}

Явна ініціалізація базових типів була реалізована для того, щоб ви могли написати код шаблону в якому величині любого типу буде попередньо присвоєне значення по замовчуванню.
Виклик конструктора гарантує, що для всіх базових типів змінна x буде ініціалізована нулем.

template < class T>
void f()
{
T x = T();
...
int i = int(); // ініціалізація змінної i нулем
}

Явна спеціалізація шаблонів.

Хочу звернути увагу на одну особливість використання явної спеціалізації з компілятором майкрософт візуал студіо та компілятором gcc.

#include < iostream>
using namespace std;

class MyClass
{
public:
MyClass() {}
~MyClass() {}
enum State { NoneState = 0x0,
Edited = 0x1,
Inserted = 0x2,
Removed = 0x4,
Saved = 0x8 };
State m_state;
template < State state> void setState() {
cout < < "Usual setState template!!!!" < < endl;
}
///////////// Explicid Specialization for State::Saved
template < > void setState< Saved>() {
cout < < "Explicid Specialication for Saved!!!!" < < endl;
}
};
int main()
{
MyClass m;
m.setState< MyClass::Removed>();
m.setState< MyClass::Saved>();
return 0;
}

Зверніть увагу на рядок

template < > void setState< Saved>() {
cout < < "Explicid Specialication for Saved!!!!" < < endl;
}

Компілятор візуал студіо 2005 без будть яких проблем допускає оголошення явної спеціалізації в середині класу, а от gcc (у мому випадку версії 4.3.0) видає наступну помилку:
error: explicit specialization in non-namespace scope ‘class MyClass’
Тому краще оголосити явну спеціалізацію за межами класу, як це потрібно:

class MyClass
{...
};
///////////// Explicid Specialization for State::Saved
template < > void MyClass::setState< MyClass::Saved>() {
cout < < "Explicid Specialication for Saved!!!!" < < endl;
}

Матеріал взято із книги Nicolai M.Josuttis The C++ Standard Library

Прихильники