Лекция 10. Стандартная библиотека (продолжение)

1 Итераторы и алгоритмы

1.1 Итераторы

Итератор - объект, предназначенный для перебора элементов контейнера STL (всех или некоторого подмножества).

Итератор представляет некоторую позицию в контейнере.

Основные операторы, работу с которыми поддерживает итератор:

• * - получение элемента в текущей позиции итератора.
• -> - Если элемент состоит из отдельных членов, для обращения к ним неносредственно через итератор используется оператор ->.
• ++ - перемещение итератора к следующему элементу. Многие итераторы также поддерживают перемещение в обратном направлении, для чего используется оператор --.
• == и != - проверка совпадений позиций, представленных двумя итераторами.
• = - присваивание итератора (позиции элемента, на которую он ссылается).

Методы begin и end

Все контейнеры поддерживаются базовые функции, применяемые для перебора элементов при помощи итераторов:

• begin() - возвращает итератор, установленный в начало последовательности элементов контейнера. Началом считается позиция первого элемента (если он есть).
• end() - возвращает итератор, установленный в конец последовательности элементов контейнера. Концом считается позиция за последним элементом.

Функции begin() и end() определяют полуоткрытый интервал [b, e), который содержит первый элемент, но выходит за пределы последнего элемента.

Полуоткрытый интервал обладает двумя достоинствами:

• появляется простое условие завершения перебора в контейнере: цикл продолжается до тех пор, пока не будет достигнута позиция end()
• предотвращается специальная обработка пустых интервалов, поскольку в пустом интервале begin() совпадает с end()

Пример

using namespace std;
int main()
{
    list<char> coll;      // Список с символьными элементами
    // Присоединение элементов от 'a' до 'z'
    for (char c='a'; c<='z'; ++c) {
        coll.push_back(c);
    }
    // Вывод содержимого списка
    // - перебор всех элементов.
    list<char>::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << *pos << ' ';
    }
}

Константный итератор

В каждом контейнере определены два типа итераторов:

• контейнер::iterator – используется для перебора элементов в режиме чтения/записи (аналог T*)
• контейнер::const_iterator – используется для перебора элементов в режиме чтения (аналог const T*)

Инкремент

// Префиксный инкремент итератора (ХОРОШО!)
for (pos = coll.begin(); pos != coll.end(); ++pos) {...}  

// Постфиксный инкремент итератора (ПЛОХО!)
for (pos = coll.begin(); pos != coll.end(); pos++) {...} 

Категории итераторов

Двунаправленный итератор - может перемещаться в двух направлениях: в прямом (оператор ++) и обратном (оператор --).

Итераторы контейнерных классов list, set, multiset, map и multimap являются двунаправленными.

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

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

Итераторы контейнерных классов vector и deque, а также итераторы строк являются итераторами произвольного доступа.

1.2 Алгоритмы

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

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

Такой подход сокращает объем программного кода, делая библиотеку более мощной и гибкой.

Пример

using namespace std;

int main()
{
    vector<int> coll;

    // Вставка элементов от 1 до 6 в произвольном порядке
    coll.push_back(2);     coll.push_back(5);     coll.push_back(4);
    coll.push_back(1);     coll.push_back(6);     coll.push_back(3);

    // Поиск и вывод минимального и максимального элементов
    vector<int>::iterator pos;
    pos = min_element (coll.begin(), coll.end());
    cout << "min: " << *pos << endl;
    pos = max_element (coll.begin(), coll.end());
    cout << "max: " << *pos << endl;
    ...

...
    // Сортировка всех элементов
    sort (coll.begin(), coll.end());

    // Поиск первого элемента со значением, равным 3
    pos = find (coll.begin(), coll.end(),  // Интервал
                3);                        // Значение

    // Перестановка найденного элемента со значением 3
    // и всех последующих элементов в обратном порядке.
    reverse (pos, coll.end());

    // Вывод всех элементов
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << *pos << ' ';
    }
    cout << endl;
}

1.3 Работа с интервалами

Интервалы

Все алгоритмы работают с полуоткрытыми интервалами.

Т.е., интервал включает заданную начальную позицию,

но конечная позиция в него не включается:

[начало, конец)

Вызывающая сторона должна проследить за тем, чтобы первый и

второй аргументы определяли действительный интервал,

то есть итератор мог перейти от начала к концу интервала в процессе перебора элементов.

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

Некоторые алгоритмы работают сразу с несколькими интервалами.

Обычно в таких случаях задаются

• начало и конец только одного интервала
• для остальных интервалов задается только начало

Т.о. конечная позиция других интервалов определяется по количеству элементов в первом интервале.

Например, следующий вызов equal() поэлементно сравнивает все содержимое

коллекции coll1 с элементами соll2, начиная с первого:

// Вызов equal() поэлементно сравнивает все содержимое
// коллекции coll1 с элементами соll2, начиная с первого элемента: 

if (  equal (coll1.begin(), coll1.end(),
             coll2.begin())              )
{
    ...
}

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

содержат не меньше элементов, чем первый интервал.

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

copy (coll1.begin(), coll1.end(), coll2.begin());

Плохой пример

using namespace std;

int main()
{
    list<int>   coll1;
    vector<int> coll2; // пустая коллекция!

    // Вставка элементов со значениями от 1 до 9
    for (int i = 1; i <= 9; ++i) {
        coll1.push_back(i);
    }
    // ОШИБКА ВРЕМЕНИ ВЫПОЛНЕНИЯ:
    // - перезапись несуществующих элементов в приемнике
    copy (coll1.begin(), coll1.end(),     // Источник
          coll2.begin());                 // Приемник
    //...

Исправленный пример

// Вставка элементов со значениями от 1 до 9
    for (int i = 1; i <= 9; ++i) {
        coll1.push_back(i);
    }
    // Изменение размера приемного интервала, чтобы он 
    // были достаточен для работы алгоритма с перезаписью.
    coll2.resize (coll1.size());

    copy (coll1.begin(), coll1.end(),     // Источник
          coll2.begin());                 // Приемник

    deque<int> coll3(coll1.size());

    copy (coll1.begin(), coll1.end(),     // Источник
          coll3.begin());                 // Приемник
}

1.4 Итераторные адаптеры

Итераторные адаптеры - несколько специализированных итераторов, содержащихся в стандартной библиотеке С++.

Итераторы, в данном контексте, являются чистыми абстракциями. Иначе говоря, любой объект, который ведет себя как итератор, является итератором.

Итераторные адаптеры - классы, которые обладают интерфейсом итератора, но делают нечто совершенно иное. (По сравнению с обычными итераторами, которые предназначены лишь для перебора элементов коллекций.)

Итераторные адаптеры наделяют саму концепцию итераторов рядом новых возможностей.

Три стандартные разновидности итераторных адаптеров:

• итераторы вставки
• потоковые итераторы
• обратные итераторы

Итераторы вставки

Итераторы вставки - позволяют использовать алгоритмы в режиме вставки (вместо режима перезаписи).

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

list<int> coll1;
    // Вставка элементов со значениями от 1 до 9 в первую коллекцию
    // в первую коллекцию
    for (int i = 1; i <= 9; ++i) {    coll1.push_back(i);    }

    // Копирование элементов из coll1 в coll2 с присоединением в конец
    vector<int> coll2;
    copy (coll1.begin(), coll1.end(),      // Источник
          back_inserter(coll2));           // Приемник
    

    // Копирование элементов coll1 в coll3 со вставкой в начало
    // - порядок следования элементов заменяется на противоположный
    deque<int> coll3;
    copy (coll1.begin(), coll1.end(),      // Источник
          front_inserter(coll3));          // Приемник

    // Копирование элементов coll1 в coll4
    // - единственный итератор вставки, работающий
    //   с ассоциативными контейнерами
    set<int> coll4;
    copy (coll1.begin(), coll1.end(),      // Источник
          inserter(coll4, coll4.begin())); 

1.5 Удаление элементов

  list<int> coll;
    // Вставка элементов со значениями от 6 до 1 и от 1 до 6
    for (int i = 1; i <= 6; ++i) { coll.push_front(i);
                                   coll.push_back(i);  }
    // Вывод всех элементов коллекции
    cout << "pre:  ";
    copy (coll.begin(), coll.end(),           // Источник
          ostream_iterator<int>(cout," "));   // Приемник
    // «Удаление» всех элементов со значением 3
    remove (coll.begin(), coll.end(),         // Интервал
            3);                               // Значение
    // Вывод всех элементов коллекции
    cout << "post: ";
    copy (coll.begin(), coll.end(),           // Источник
          ostream_iterator<int>(cout," "));   // Приемник
}

Результат:

pre: 6 5 4 3 2 1 1 2 3 4 5 6

post: 6 5 4 2 1 1 2 4 5 6 5 6

Алгоритм remove() не изменяет количество элементов в коллекции, для которой он вызывался.

После вызова remove() функция end() возвращает прежнее значение,

а функция size() - прежнее количество элементов.

Алгоритм remove() изменяет порядок следования элементов таким образом,

каким он должен стать после удаления.

На место «удаленных» элементов записаваются следующие элементы.

Прежние элементы в конце коллекции, не перезаписанные алгоритмом,

остаются без изменений. (На логическом уровне эти конечные элементы уже не принадлежат коллекции.)

remove() возвращает итератор, указывающий на логический новый конец коллекции.

Это значение позволяет прочитать

полученный интервал, уменьшить размер коллекции или узнать количество удаленных элементов

// Удаление всех элементов со значением 3
    // - сохранение нового логического конца коллекции
    list<int>::iterator end = remove (coll.begin(), coll.end(),
                                      3);

    // Вывод элементов полученной коллекции
    copy (coll.begin(), end,
          ostream_iterator<int>(cout," "));
    cout << endl;

    // Вывод количества "удаленных" элементов
    cout << "number of removed elements: "
         << distance(end, coll.end()) << endl;

    // Стирание "удаленных" элементов
    coll.erase (end, coll.end());

    // Вывод всех элементов модифицированной коллекции
    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout," "));
}

// Удаление и стирание всех элементов со значением 3
    coll.erase (remove(coll.begin(), coll.end(),
                       3),
                coll.end()); 

    // Вывод всех элементов модифицированной коллекции
    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout," "));
}

Почему remove() сам не вызывает erase() ?

Ответ – в гибкой архитектуре STL:

• remove() – алгоритм, работающий через итераторы
• erase() – метод контейнера
• Алгоритм не может (и не должен) вызывать напрямую методы контейнера.
• Некоторые контейнеры не поддерживают функцию erase() (например, обычный массив).
• «Физическое» стирание не всегда нужно.

Работа с ассоциативными контейнерами

Нельзя использовать модифицирующие алгоритмы с ассоциативными контейнерами.

Для сохранения упорядоченности все итераторы ассоциативных контейнеров объявляются

итераторами константных значений (или ключей).

Работа с ассоциативными контеинерами

Как же удалить элементы из ассоциативных контейнеров?

• Для удаления элементов из ассоциативных контейнеров используются собственные методы контейнера.
• В каждом ассоциативном контейнере предусмотрены методы удаления элементов. Например, элементы можно удалить функцией erase().
• Контейнеры поддерживают несколько версий функции erase().
• Только та версия, единственным аргументом которой является значение удаляемого элемента (или элементов), возвращает количество удаленных элементов.

Работа с ассоциативными контейнерами

  set<int> coll;
  for (int i = 1; i <= 9; ++i) { coll.insert(i); }

    // Вывод всех элементов коллекции
    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout," "));
    cout << endl;

    // Удаление (физическое) всех элементов со значением 3
    int num = coll.erase(3);

    // Вывод количества удаленных элементов
    cout << "number of removed elements: " << num << endl;

    copy (coll.begin(), coll.end(),
          ostream_iterator<int>(cout," "));
}

2 Функторы

Функтор – объект, который ведет себя как функция. (объект-функция)

Класс в С++ с перегруженным оператором () является функтором:

class X {
  public:    // или без const
    bool operator () (int) const;
};

Функциональный аргумент – аргумент, который «ведет себя как функция».

В качестве функциональных аргументов часто используются предикаты и функторы.

namespace std {
  template <class T, class Compare>
  inline const T& max (const T& a, const T& b, Compare comp) {
    return comp(a, b) ? b : a;
  }
} 

Функторы

// Вывод всех элементов
for_each (coll.begin(), coll.end(),    // Интервал
          print);                      // Операция - функция

...// Вывод всех элементов
for_each (coll.begin(), coll.end(),    // Интервал
         PrintInt());                 // Операция - функтор

Функторы

Функтор - это «умная функция», поскольку их возможности не ограничиваются

вызовом оператора (). Функторы могут представлять другие функции и иметь другие атрибуты,

т.е. функторы обладают состоянием. У обычных функций такая возможность отсутствует.

Одно из главных достоинств функторов - возможность их инициализации на стадии выполнения перед

вызовом/использованием.

Каждому функтору соответствует свой тип. Функциональное поведение может передаваться при

конструировании экземпляра функтора, или даже как параметр шаблона (если функтор – шаблон).

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

качестве критерия сортировки. Тем самым предотвращается возможное присваивание, слияние и

сравнение коллекций, использующих разные критерии сортировки.

Функторы обычно работают быстрее функций, т.к. шаблоны обычно лучше оптимизируются.

// Функтор прибавляет к значению элемента приращение,
// заданное при его инициализации
class AddValue {
    int theValue;    // Приращение
  public:
    // Конструктор инициализирует приращение
    AddValue(int v) : theValue(v) { }

    // Суммирование выполняется "вызовом функции" для элемента 
    void operator() (int& elem) const {  elem += theValue;  }
};
int main() {
    list<int> coll;
      ...
    // Прибавить к каждому элементу 10
    for_each (coll.begin(), coll.end(),    // Интервал
              AddValue(10));               // Операция

    // Прибавить к каждому элементу значение первого элемента
    for_each (coll.begin(), coll.end(),    // Интервал
              AddValue(*coll.begin()));    // Операция
}

3 Умные указатели

void f()
{
  // Создание и инициализация auto_ptr
  std::auto_ptr<ClassA> ptr(new ClassA);

  // Работа с «умным» указателем
  ptr->f();
  ptr->m_val = 0;
  otherObjA = *ptr;

  // Удаление автоматически при разрушении
  // локального экземпляра ‘ptr’ (при выходе
  // из блока).
}

При копировании auto_ptr (при помощи конструктора копирования, либо оператора =)

происходит передача «права владения» тем объектом, на который ссылается auto_ptr.

// Инициализация auto_ptr новым объектом
std::auto_ptr<ClassA> ptr1(new ClassA);

// Копирование auto_ptr 
// - право владения объектом передается от ptr1 к ptr2
std::auto_ptr<ClassA> ptr2(ptr1);

// Объект будет удален только один раз – при уничтожении ptr2.