Реализация паттерна Visitor по шагам

1. Добавьте метод accept(Visitor) иерархию "элемент".

2. Создайте базовый класс Visitor и определите методы visit() для каждого типа "элемента".

3. Создайте производные классы Visitor для каждой "операции", исполняемой над "элементами".

4. Клиент создает объект Visitor и передает его в вызываемый метод accept().

#include <iostream> #include <string> using namespace std;   // 1. Добавьте метод accept(Visitor) иерархию "элемент" class Element { public: virtual void accept(class Visitor &v) = 0; };   class This: public Element { public: /*virtual*/void accept(Visitor &v); string thiss() { return "This"; } };   class That: public Element { public: /*virtual*/void accept(Visitor &v); string that() { return "That"; } };   class TheOther: public Element { public: /*virtual*/void accept(Visitor &v); string theOther() { return "TheOther"; } };   // 2. Создайте базовый класс Visitor и определите // методы visit()для каждого типа "элемента" class Visitor { public: virtual void visit(This *e) = 0; virtual void visit(That *e) = 0; virtual void visit(TheOther *e) = 0; };   /*virtual*/void This::accept(Visitor &v) { v.visit(this); }   /*virtual*/void That::accept(Visitor &v) { v.visit(this); }   /*virtual*/void TheOther::accept(Visitor &v) { v.visit(this); }   // 3. Создайте производные классы Visitor для каждой // "операции", исполняемой над "элементами" class UpVisitor: public Visitor { /*virtual*/void visit(This *e) { cout << "do Up on " + e->thiss() << '\n'; } /*virtual*/void visit(That *e) { cout << "do Up on " + e->that() << '\n'; } /*virtual*/void visit(TheOther *e) { cout << "do Up on " + e->theOther() << '\n'; } };   class DownVisitor: public Visitor { /*virtual*/void visit(This *e) { cout << "do Down on " + e->thiss() << '\n'; } /*virtual*/void visit(That *e) { cout << "do Down on " + e->that() << '\n'; } /*virtual*/void visit(TheOther *e) { cout << "do Down on " + e->theOther() << '\n'; } };   int main() { Element *list[] = { new This(), new That(), new TheOther() };   UpVisitor up; // 4. Клиент создает DownVisitor down; // объекты Visitor for (int i = 0; i < 3; i++) // и передает каждый list[i]->accept(up); for (i = 0; i < 3; i++) // в вызываемый метод accept() list[i]->accept(down); }

Вывод программы:

do Up on This do Down on This do Up on That do Down on That do Up on TheOther do Down on TheOther

Реализация паттерна Visitor: до и после

До

Интерфейс для "операций" определяется в базовом классе Color и реализуется в его подклассах.

class Color { public: virtual void count() = 0; virtual void call() = 0; static void report_num() { cout << "Reds " << s_num_red << ", Blus " << s_num_blu << '\n'; } protected: static int s_num_red, s_num_blu; }; int Color::s_num_red = 0; int Color::s_num_blu = 0;   class Red: public Color { public: void count() { ++s_num_red; } void call() { eye(); } void eye() { cout << "Red::eye\n"; } };   class Blu: public Color { public: void count() { ++s_num_blu; } void call() { sky(); } void sky() { cout << "Blu::sky\n"; } };   int main() { Color *set[] = { new Red, new Blu, new Blu, new Red, new Red, 0 }; for (int i = 0; set[i]; ++i) { set[i]->count(); set[i]->call(); } Color::report_num(); }

Вывод программы:

Red::eye Blu::sky Blu::sky Red::eye Red::eye Reds 3, Blus 2

Заключение

Несколько фактов о каждом контейнере:

o std::list очень медленно осуществляет обход элементов из-за особенностей размещения данных;

o std::vector и std::deque всегда работают быстрее с типами данных небольших размеров;

o std::list хорошо обрабатывает большие элементы;

o std::deque показывает лучшую производительность при вставке элементов в случайные позиции, в особенности - в начало очереди;

o std::deque и std::vectorплохо справляются с данными с высокой стоимостью копирующих конструкторов и операторов присваивания.

Соответственно, заключение о том, где использовать контейнеры:

o Сложные вычисления: std::vector или std::deque;

o Линейный поиск: std::vector или std::deque;

o Случайная вставка или удаление: std::deque или std::list. Если размер данных мал, то лучше использовать std::deque;

o Работа с данными больших размеров: std::list;

o Нетривиальные типы данных: std::list;

o Вставка в начало: std::deque или std::list.

Алгоритмы STL

Итераторы

Итераторы предназначены для перебора элементов контейнеров. Их универсальность позволяет писать код, не зависящий от типа контейнера.
Итераторы имеют семантику указателей:

• Поддерживают операции ++, --, *, ->.
• Полседовательность задается двумя итераторами:
  
  Итератор p указывает на первый элемент контейнера, итератор q - на элемент, следующий за последним. На первый взгляд такой способ задания последовательности может показаться неестественным. Казалось бы, разумнее задавать последовательность таким образом, при котором итератор q указывает на ее последний элемент, то есть представлять последовательность в виде отрезка [p, q]. Но тогда у нас не было бы возможности задать пустую последовательность: если оба итератора p и qуказывают на один и тот же элемент, то это означало бы, что в контейнере содержится один элемент. В то время как представление последовательности в виде полуинтервала [p, q) позволяет задать пустой контейнер: если p и q указывают на один и тот же элемент, то последовательность пуста.

Итераторы можно разделить на категории:

• Random access iterator (RA)
  Повторяет полностью синтаксис и семантику указателя (самый сильный итератор): поддерживает ++, --, [], арифметические операции.
• Bidirectional iterator (BiDi)
  Поддерживает только ++, --. Это более слабый итератор.
• Forward iterator (Fwd)
  Поддерживает только ++.
  Forward итераторы делятся на две подкатегории:
• Output iterator
  ++, write (только запись)
• Input iterator
  ++, read (только чтение)

RA ⊂ BiDi ⊂ Fwd
У std::vector и std::deque RA итераторы, у остальных контейнеров - BiDi.

Также существует Reverse Iterator (rev), у которого операции ++ и -- инвертированы (действуют в обратные стороны к таким же операциям у обычного итератора). Получение из reverse итератора обычного итератора (original) производится с помощью функции base(). Получение из обычного итератора reverse итератора - с помощью конструктора.
Например:

using namespace std;list<int> l;for (list<int>::iterator i = l.begin(); i != l.end(); ++i){ ...}for (list<int>::reverse_iterator i = l.rbegin(); i != l.rend(); ++i){ list<int>::iterator j = i.base(); ...}

rbegin эквивалентен end, rend эквивалентен begin:

Если reverse итератор указывает на 3 (третий элемент на рисунке), то обычный будет указывать на 4 (четвертый элемент на рисунке). Об этом важно помнить.
base() - это функция, которая выполняет неявное преобразование.

Из любого BiDi итератора можно получить rev итератор. Например, это можно сделать самим, написав класс, который содержит обычный итератор, и в котором перегружены операторы ++ и --. Но это уже написано:

#include <iterator> std::reverse_iterator<It> rev_it(it); // сконструировали rev итератор от BiDi

Это бывает нужно, если, например, требуется написать шаблонную функцию, внутри которой должны выполняться какие-то операции с контейнером в обратном порядке, и которая не должна зависеть от типа контейнера (reverse итераторы есть у всех контейнеров). Например:

template<class It>void f (It p, It q){ copy(std::reverse_iterator<It>(p), std::reverse_iterator<It>(q), out);}

Примеры STL алгоритмов для итераторов:

• std::advance(it, n)
  Продвигает итератор на n позиций вперед (аналогично p += n для указателей). Для RA итераторов использует [], для BiDi - ++. Если происходит выход за границы контейнера, то undefined behaviour.
• std::distance(it1, it2)
  Возвращает расстояние между итераторами (аналогично q - p для указателей) при условии, что it1 ≤ it2 В противном случае undefined behaviour, так как этот алгоритм фактически вычисляет, сколько раз нужно продвинуть итератор it1 на одну позицию, чтобы получить итератор it2.

Кроме того, существует класс iterator_traits<It>. Он предназначен для получения информации о связанных с данным итератором типах. Этот класс не создает данных, а просто содержит typedef'ы:

 

• iterator_traits<It>::value_type - тип элемента, на который может указывать итератор.
• iterator_traits<It>::reference - тип ссылки на элемент, на которую может указывать итератор.
• iterator_traits<It>::pointer - тип указателя на элемент, на который может указывать итератор.
• iterator_traits<It>::difference_type - тип значения, которое получается при вычитании одного итератора из другого.

Алгоритмы

#include <algorithm>

В STL более 100 алгоритмов. Мы будем рассматривать не все.
Мы не будем рассматривать:

• Операции с неинициализированными данными.
• Алгоритмы для работы с кучей.
• Операции над множествами.
• Операции с перестановками.

Мы будем рассматривать следующие алгоритмы:

• Микро-алгоритмы
• Алгоритмы, не модифицирующие последовательности
• Алгоритмы типа find
• Модифицирующие алгоритмы

1. Микро-алгоритмы
• swap(T &a, T &b)
  Меняет местами значения двух элементов.
• iter_swap(It p, It q)
  Меняет местами значения элементов, на которые указывают итераторы.
• max(const T &a,const T &b )
  Возвращает максимальный элемент.
• min(const T &a,const T &b )
  Возвращает минимальный элемент.

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

1. Алгоритмы, не модифицирующие последовательности
• size_t count(It p, It q, const T &x)
  Возвращает, сколько раз элемент со значением x входит в последовательность, заданную итераторами p и q.
• size_t count_if(It p, It q, Pr pred)
  Возвращает, сколько раз предикат pred возвращает значение true.
  Например, count_if(p, q, divides_by(8)) вернет, сколько элементов кратно 8;
2. Алгоритмы типа find
• find(It p, It q, const T &x)
  Возвращает итератор на первое вхождение элемента x в последовательность, заданную итераторами p и q.
• find_if(It p, It q, Pr pred)
  Возвращает итератор на первый элемент, для которого предикат pred вернул значение true.
• find_first_of(It p, It q, Itr i, Itr j)
  Возвращает итератор на первое вхождение любого элемента из последовательности, заданной итераторами i и j, в последовательность, заданную итераторами pи q. Последовательности могут быть разных типов (например std::vector и std::list).
• min_element(It p, It q)
  Возвращает итератор на минимальный элемент последовательности.
• max_element(It p, It q)
  Возвращает итератор на максимальный элемент последовательности.
• equal(It p, It q, Itr i)
  Сравнивает две последовательности на эквивалентность. Вторая последовательность задается одним итератором, так как последовательности должны быть одинаковой длины. Если вторая короче, то undefined behaviour.
• pair <It, Itr> mismach(It p, It q, Itr i)
  Возвращает пару итераторов, указывающую на первое несовпадение последовательностей.
• F for_each(It p, It q, F func)
  Для каждого элемента последовательности применяет функтор func. Возвращаемое значение функтора после каждого применения игнорируется. Возвращает функтор func после его применения ко всем элементам.
• bool binary_search(It p, It q, const T &x)
  Возвращает true, если в упорядоченной последовательности есть элемент, значение которого равно x, false в противном случае.
  Если хотим получить итератор на элемент со значением x, то нужно использовать алгоритмы lower_bound(It p, It q, const T &x), upper_bound(It p, It q, const T &x), equal_range(It p, It q, const T &x), которые выполняют то же, что и одноименные методы для контейнера std::set. Эти алгоритмы работают за линейное время на BiDi итераторах и за логарифмическое время на RA итераторах.

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

1. Модифицирующие алгоритмы
• fill(It p, It q, const T &x), fill_n(It p, Size n, const T &x)
  Заполняют последовательность значениями, равными значению x.
• generate(It p, It q, F gen), generate_n(It p, Size n, F gen)
  Заполняют последовательность значениями, сгенерированными функтором gen (например, генератором случайных чисел).
• random_shuffle(It p, It q), random_shuffle(It p, It q, F &rand)
  Перемешивает элементы в случайном порядке: меняет местами каждый элемент с элементом, номер которого выбирается случайно. Третьим параметром можно задать функтор, который будет выбирать этот случайный номер. Можно передавать генератор случайных чисел, но распределение должно быть равномерным (каждая перестановка должна генерироваться с вероятностью 1/n!, а это совсем не то же самое, что каждый элемент окажется на i-м месте с вероятностью 1/n). Требует RA итераторов.
• copy(It p, It q, Itr out)
  Копирует значения элементов последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out.
  copy_backward(It p, It q, Itr out) Копирует элементы последовательности, заданной итераторами p и q, в последовательность, заканчивающуюся итератором out. Итераторы должны быть BiDi.
• remove_copy(It p, It q, Itr out, const T &x)
  Копирует значения элементов из последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out, за исключением элементов, значения которых равны значению x.
  remove_copy_if(It p, It q, Itr out, Pr pred)
  Копирует значения элементов из последовательности, заданной итераторами p и q, в последовательность, начинающуюся с итератора out, за исключением элементов, для которых предикат pred возвращает значение true.
• reverse(It p, It q)
  Переставляет элементы в обратном порядке.
  reverse_copy(It p, It q, Itr out)
  Копирует значения элементов в обратном порядке.
• rotate(It p, It middle, It q)
  Сдвигает элементы последовательности так, что элемент, на который указывает итератор middle становится первым.
  
  Этот алгоритм реализован по-разному для разных категорий итераторов (RA, BiDi, Fwd).
• swap_ranges(It p, It q, Itr i)
  Меняет местами элементы последовательности, заданной итераторами p и q, с соответствующими элементами последовательности, начинающейся с и итератораout.
  
• remove(It p, It q, const T &x)
  Удаляет из последовательности элементы, значения которых совпадают по значению с x. Возвращает итератор на новый конец последовательности.
  Например:

o using namespace std;o vector<int> v;o ...o vector<int>::iterator new_end = std::remove(v.begin(), v.end(), 3); // хотим удалить все тройки

В действительности remove ничего не удаляет, так как ему не передается контейнер.

remove внутри себя как бы вызывает remove_copy_if. Поэтому последние два элемента в примере на рисунке останутся без изменений.
Правильный вариант удаления:

v.erase(std::remove(v.begin(), v.end(), 3), v.end());

Удаляем все, что находится между итератором, который вернул remove, и концом последовательности. Это называется remove-erase-idiom.
remove_if(It p, It q, Pr pred)
Удаляет из последовательности элементы, для которых предикат pred возвращает true. Возвращает итератор на новый конец последовательности.

• unique(It p, It q), unique(It p, It q, Pr pred)
  Удаляет одинаковые подряд идущие элементы, оставляя только по одному элементу для каждого значения. Элементы последовательности должны быть отсортированы. Работает аналогично алгоритмам remove и remove_if, оставляя в начале только уникальные элементы, а в конце - то, что осталось. В качестве третьего параметра можно передавать предикат, сравнивающий два элемента и возвращающий true, если элементы равны, и false в противном случае.
  unique_copy(It p, It q, Itr out), unique_copy(It p, It q, Itr out, Pr pred)
  Копирует уникальные элементы в последовательность, начинающуюся с итератора out.
• transform(It p, It q, Itr out, F func)
  К каждому элементу входящей последовательности применяет функтор func и записывает результат в последовательность, начинающуюся с итератора out.
  transform(It p, It q, Itr i, Iter out, F func)
  Применяет бинарный функтор func к каждой паре элементов из двух входящих последовательностей и записывает результат в результирующую последовательность.
• accimulate(It p, It q, T i, F func)
  Последовательно применяет бинарный функтор func к парам (i, *p++), где i - некоторое начальное значение, которое затем каждый раз заменяется значением, которое возвращает функтор. Функтор должен возвращать значение типа T.
  Реализация этого алгоритма выглядит примерно следующим образом:

o while (p != q)o {o i = func(i, *(p++));o }o return i;

Например, если в качестве i передать 0, а в качестве func - функтор, вычисляющий сумму, то посчитаем сумму элементов последовательности. Если в качестве iпередать 1, а в качестве func - функтор, вычисляющий произведение, то получим произведение элементов и т.д.

• sort(It p, It q), sort(It p, It q, Pr pred)
  Сортирует элементы последовательности в порядке возрастания. stable_sort(It p, It q), stable_sort(It p, It q, Pr pred)
  Сортирует элементы, сохраняя порядок элементов с одинаковыми значениями относительно друг друга. Эти алгоритмы требуют RA итераторов, поэтому на списке работать не будут. Но у списка есть собственные функции члены sort, stable_sort.
• void nth_element(It p, It nth, It q), void nth_element(It p, It q, It nth, Pr pred)
  Позволяет получить n-й по порядку элемент (n-й по счету, как если бы массив был отсортирован), переставляя элементы таким образом, что все элементы до него меньше, либо равны ему, а элементы после - больше, либо равны ему.
• partition(It p, It q, Pr pred)
  Переставляет элементы последовательности таким образом, что все элементы, для которых предикат вернул true, предшествуют тем, для которых он вернулfalse. Возвращает итератор на первый элемент из второй группы.
• void partial_sort(It p, It middle, It q), void partial_sort(It p, It middle, It q, Pr pred)
  Переставляет элементы последовательности так, что элементы межу итераторами p и q располагаются в том порядке, как если бы последовательность была отсортирована, а элементы в оставшейся части - в произвольном порядке. То есть получаем часть отсортированной последовательности (не то же самое, что отсортированную часть).
• merge(It p, It q, Itr i, Itr j, Iter out), merge(It p, It q, Itr i, Itr j, Iter out, Pr pred)
  Сортирует две последовательности слиянием.

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

Функторы и предикаты - это классы, объекты которых похожи на функцию (в них перегружен оператор () ). Например:

struct cmp{ bool operator ()(int a, int b) const { return a < b; // а можно, например, return a % 7 < b % 7 }}

Требование для предиката - оператор () должен возвращать значение типа bool. Требование для функтора - у оператора () тип возвращаемого значения должен быть отличным от bool.

struct sum2{ int operator ()(int a, int b) const { return (a + b) * (a + b); }}

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

bool operator ()(int a) const{ return a > 0;}

Но если понадобится сравнивать с произвольным числом, то стоит хранить это число внутри предиката.

bool operator ()(int a) const{ return a > k;}

Передавать число k через параметр не стоит, так как, например, может быть поставлено требование, чтобы сигнатура содержала только один параметр.

Предикаты с одним параметром называются унарными, с двумя - бинарными.

АЛЛОКАТОРЫ

#include <memory>#include <iostream>#include <string> int main(){ std::allocator<int> a1; // default allocator for ints int* a = a1.allocate(10); // space for 10 ints a[9] = 7; std::cout << a[9] << '\n'; a1.deallocate(a, 10); // default allocator for strings std::allocator<std::string> a2; // same, but obtained by rebinding from the type of a1 decltype(a1)::rebind<std::string>::other a2_1; // same, but obtained by rebinding from the type of a1 via allocator_traits std::allocator_traits<decltype(a1)>::rebind_alloc<std::string> a2_2; std::string* s = a2.allocate(2); // space for 2 strings a2.construct(s, "foo"); a2.construct(s + 1, "bar"); std::cout << s[0] << ' ' << s[1] << '\n'; a2.destroy(s); a2.destroy(s + 1); a2.deallocate(s, 2);}

Как именно управляет - это надо смотреть в реализации.
Зачем это нужно: рассмотрим два случая: 1) вы редко создаёте объекты, и у них долгое время жизни. Тогда вы вполне можете позволить себе выделять память для каждого объекта отдельно. 2) вы часто создаёте и уничтожаете объекты. Тогда вам может быть невыгодно постоянно обращаться к системе за выделением/освобождением памяти - вы можете выделить сразу большую область памяти, и отводить части этой памяти для свежесозданных объектов. При уничтожении вы просто помечаете адрес памяти как неиспользуемый, и не возвращаете память системе до конца работы приложения. Тут можно поуправлять тем, как расширяется, как уплотняется эта область памяти (например, для увеличения вероятности попадания в кэш процессора).

 

C++ частичная специализация шаблонов функций есть!!!

0

0

bash-2.05b$ cat test1.cpp

#include <iostream>

using namespace std;

template<class R, class A>

A z(R r, A a)

{

cerr << "0" << endl;

return a;

};

template<class R>

Int z(R r, int a)

{

cerr << "1" << endl;

return a;

};

Main()

{

z("zzz","zzz");

z("zzz",1);

}