Лекция 9. Стандартная библиотека (1)

1 Состав

Стандартная библиотека С++ включает в себя следующие компоненты:

• Стандартная библиотека языка С (С89-90);
• Строки;
• Контейнеры;
• Итераторы;
• Алгоритмы;
• Функторы;
• Потоки;
• Утилиты;
• Механизмы исключений;

Все компонеты стандартной билиотеки находятся в пространстве имен std

• Строки - замена неудобного массива символов (строки С). Являются, по сути, - контейнером символов.
• Контейнеры - структуры для хранения данных. Реализованы на шаблонах.
• Итераторы - разновидность указателей для доступа и перебора данных в контейнерах.
• Алгоритмы - реализации широко известных алгоритмов.
• Потоки - объекты для ввода/вывода.
• Функторы - объекты, ведущие себя как функции (или наоборот).

2 Строки

Тип string

Классические строки Си (char*) неудобны в том смысле, что с ними приходится обращаться как с массивами.

В состав С++ включен тип данных string, который позволяет обращаться со строками как с объектами.

Для работы с типом string нужно подключить одноименный заголовочный файл без расширения:

using namespace std;
...
string str1="Hello",s2="world!",s3;
s3=s1+s2;
cout<<s3<<endl;
..

Строки strings

Способы создания объекта string:

string();
string( const string& s );
string( size_type length, Char ch );
string( const Char* str );
string( const Char* str, size_type length );
string( const string& str, size_type index, size_type length );
string( input_iterator start, input_iterator end );
~string();

Примеры создания строк:

string str1( 5, 'c' );
string str2( "Now is the time..." );
string str3( str2, 11, 4 ); // берем 4 символа, начиная с 11
cout << str1 << endl;
cout << str2 << endl;
cout << str3 << endl;

Перегруженные операции для string

bool operator==(const string& c1, const string& c2);
bool operator!=(const string& c1, const string& c2);
bool operator<(const string& c1, const string& c2);
bool operator>(const string& c1, const string& c2);
bool operator<=(const string& c1, const string& c2);
bool operator>=(const string& c1, const string& c2);
string operator+(const string& s1, const string& s2 );
string operator+(const Char* s, const string& s2 );
string operator+( Char c, const string& s2 );
string operator+( const string& s1, const Char* s );
string operator+( const string& s1, Char c );
string& operator+=(const string& append);
string& operator+=(const Char* append);
string& operator+=(const Char  append);
ostream& operator<<( ostream& os, const string& s );
istream& operator>>( istream& is, string& s );
string& operator=( const string& s );
string& operator=( const Char* s );
string& operator=( Char ch );
Char& operator[]( size_type index );
const Char& operator[]( size_type index ) const;

Методы string

Примеры работы со строками

string a("abcd efg");
string b("xyz ijk");
string c;

cout<<"String empty:"<<c.empty()<<endl; // строка пустая: 1
c = a + b;                              // конкатенация
cout<<"String length: "<< c.length()<< endl;// Длина : 15
cout<<"String size: "  << c.size()<< endl;// Размер: 15
cout<<"String capacity:"<< c.capacity()<< endl;// Емкость: 15
cout<<"String empty: " << c.empty()<< endl;// 0

string g("abc abc abd abc");
cout<<"String g: "<<g<<endl;        // g: abc abc abd abc
cout<<g.replace(12,1,"xyz",3)<<endl;// g: abc abc abd xyzbc
cout<<g.replace(0,3,"xyz",3)<<endl; // xyz abc abd xyzbc
cout<<g.replace(4,3,"xyz",3)<<endl; // xyz xyz abd xyzbc
cout<<g.replace(4,3,"ijk",1)<<endl; // xyz i abd xyzbc
cout<<"Find: "<<g.find("abd",1)<<endl; // Find: 6
cout<<g.find("qrs",1) << endl;

string h("abc abc abd abc");
cout<<h<<endl;
cout<<h.find("abc",0)<<endl; // 0
cout<<h.find("abc",1)<<endl; // 4
cout<<h.find_first_of("abc",0)<<endl;// 0
cout<<h.find_last_of("abc",0)<<endl; // 0
cout<<h.find_first_not_of("abc",0)<<endl;// 3
cout<<h.find_first_not_of(" ")<<endl;    // 0
cout<<h.substr(5,9) << endl;             // bc abd ab
cout<<h.compare(0,3,"abc") << endl;      // 0
cout<<h.compare(0,3,"abd") << endl;      // -1
cout<<h.assign("xyz",0,3) << endl;       // xyz
cout<<h[0] << endl; 

string g("abc abc abd abc");
cout << g.replace(4,1,"ijk",3) << endl;

string h("abc abc abd abc");
cout << h.replace(4,6,"ijk",3) << endl;

string k("abc abc abd abc");
cout << k.replace(4,3,"ijk",3) << endl;
 
string l("abc abc abd abc");
cout << k.replace(12,1,"xyz",3) << endl;

3 Концепция STL

Основы STL

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

Центральное место в STL занимают:

• Контейнеры предназначены для управления коллекциями объектов определенного типа. У каждой разновидности контейнеров имеются свои достоинства и недостатки.
• Итераторы предназначены для перебора элементов в коллекциях объектов (контейнерах или их подмножествах). Главное достоинство итераторов - они предоставляют небольшой, но стандартный интерфейс, подходящий для любого типа контейнера.
• Алгоритмы предназначены для обработки элементов коллекций. (Поиск, сортировку, модификацию и т.д.). В работе алгоритмов используются итераторы. Алгоритм достаточно запрограммировать только один раз для обобщенного контейнера, потому что интерфейс итераторов является общим для всех контейнеров.

Концепция STL

Концепция STL основана на разделении данных и операций.

Данные находятся под управлением контейнерных классов, а операции определяются адаптируемыми алгоритмами.

Итераторы выполняют функции «клея», связывающего эти два компонента.

Благодаря им любой алгоритм может работать с любым контейнером:

Концепция STL противоречит исходным принципам ООП: STL отделяет друг от друга данные и алгоритмы.

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

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

STL - хороший пример концепции унифицированного (обобщенного) программирования.

4 Контейнеры STL

4.1 Общие сведения

Концепция контейнеров

Контейнеры – управляют коллекциями элементов.

Наиболее популярные контейнеры:

• Вектор
• Список
• Дек
• Отображение
• Множество

Стандарт не определяет реализацию контейнеров,

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

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

• Контейнеры должны поддерживать семантику значений вместо ссылочной семантики. При вставке элемента контейнер создает его внутреннюю копию, вместо того чтобы сохранять ссылку на внешний объект. Следовательно, элементы контейнера STL должны поддерживать копирование.
• Элементы в контейнере располагаются в определенном порядке. Это означает, что при повторном переборе с применением итератора порядок перебора элементов должен остаться прежним. В каждом типе контейнера определены операции, возвращающие итераторы для перебора элементов.
• В общем случае операции с элементами контейнеров небезопасны. Вызывающая сторона должна проследить за тем, чтобы параметры операции соответствовали требованиям. Нарушение правил (например, использование недействительного индекса) приводит к непредсказуемым последствиям.

Типы контейнеров

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

Общие операции

Последовательные контейнеры

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

Позиция зависит от времени и места вставки, но не связана со значением элемента.

STL содержит три стандартных класса последовательных контейнеров:

• vector (вектор)
• deque (дек)
• list (список)

Строки и обычные массивы тоже можно рассматривать как особые разновидности последовательных контейнеров.

4.2 Вектор

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

using namespace std;
int main()
{
    vector<int> coll;    // Вектор с целыми элементами
    // Присоединение элементов со значениями от 1 до 6
    for (int i=1; i< = 6; ++i) {
        coll.push_back(i);
    }
    // Вывод элементов, разделенных пробелами
    for (int i=0; i < coll.size(); ++i) {
        cout << coll[i] << ' ';
    }
}

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

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

Возможности вектора

• Векторы поддерживаютsize(), empty() и max_size().
• Функция capacity() возвращет максимальное количество элементов, которые могут храниться в текущей выделенной памяти. Если количество элементов больше, происходит перераспределение.
• В результате перераспределения памяти становятся недействительными все ссылки, указатели и итераторы элементов вектора;
• На перераспределение памяти требуется время.
• Чтобы предотвратить перераспределение памяти, можно заранее зарезервировать некоторую емкость функцией reserve().
• Либо можно проинициализировать вектор достаточным количеством элементов, для чего конструктору передается начальный размер вектора.

std::vector<T> v(5);
v.reserve(80);  

• Вызов reserve() с аргументом, меньшим текущей емкости вектора, игнорируется.
• Способы оптимизации по скорости и затратам памяти определяются реализацией.
• Емкость вектора напрямую никогда не уменьшается. Поэтому ссылки, указатели и итераторы заведомо остаются действительными даже при удалении элементов. Однако вставка может привести к тому, что ссылки, указатели и итераторы станут недействительными.
• После вызова функции swap() все ссылки, указатели и итераторы продолжают ссылаться на первоначально выделенную память. Т.е. все ссылки, указатели и итераторы становятся недействительными

template <class T>
void shrinkCapacity(std::vector<T>& v)
{
    std::vector<T> tmp(v); // Копирование элементов в новый вектор
    v.swap(tmp);           // Перестановка внутренних данных векторов
} 

Обращения к элементам:

4.3 Дек

Дек (deque) = «double-ended queue» – двусторонняя очередь.

Дек – динамический массив, который может расти в обоих направлениях.

Таким образом, операции вставки (и удаления) элементов в конец и в начало коллекции выполняются очень быстро, а вставка в середину занимает больше времени, потому что требует перемещения элементов.

Заголовочный файл:

using namespace std;

int main()
{
    deque<float> coll;    // Дек с вещественными элементами

    // Вставка в начало элементов со значениями от 1.1 до 6.6
    for (int i=1; i <= 6; ++i) {
        coll.push_front(i*1.1);      // Вставка в начало дека
    }
    // Вывод элементов, разделенных пробелами
    for (int i=0; i < coll.size(); ++i) {
        cout << coll[i] << ' ';
    }
}

Возможности дека

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

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

4.4 Список

Список (list) реализуется в виде двусвязного списка элементов. Каждый элемент списка занимает отдельный блок памяти и содержит ссылки на предыдущий и следующий элементы.

Список не поддерживает произвольный доступ к элементам.

Переход к следующему или предыдущему элементу выполняется быстро.

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

Заголовочный файл:

using namespace std;
int main()
{
    list<char> coll;      // Список с символьными элементами
    // Присоединение элементов от 'a' до 'z'
    for (char c='a'; c <= 'z'; ++c) {
        coll.push_back(c);
    }
    // Вывод содержимого списка
    // - пока в списке остаются элементы,
    // - вывести и удалить первый элемент.
    while (! coll.empty()) {
        cout << coll.front() << ' ';
        coll.pop_front();
    }
}

Возможности списков

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

• Эти принципиальные различия отражены в функциях списков, что делает их непохожими на функции векторов и деков:
• В списках не определены ни оператор индексирования, ни метод at().
• Списки не поддерживают операции, связанные с емкостью и перераспределением памяти.
• Списки поддерживают много специальных методов для перемещения элементов.
• Эти методы представляют собой оптимизированные версии одноименных универсальных алгоритмов. Оптимизация основана на замене указателей вместо копирования и перемещения значений.

4.5 Ассоциативные контейнеры

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

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

STL содержит четыре стандартных класса ассоциативных контейнеров:

1. Множества (set) - коллекции, в которых элементы сортируются в соответствии с их значениями. Каждый элемент присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
2. Мультимножества (multiset) - то же, что и множества, но с возможностью хранения дубликатов. Т.е., мультимножество может содержать несколько элементов с одинаковыми значениями.
3. Отображения (map) - коллекции, состоящие из пар «ключ/значение». У каждого элемента имеется ключ, определяющий порядок сортировки, и значение. Каждый ключ присутствует в коллекции только в одном экземпляре, дубликаты не разрешаются.
4. Мультиотображения (multimap) - то же, что и отображения, но с возможностью дублирования ключей. Это означает, что мультиотображение может содержать несколько элементов с одинаковыми ключами.

Множество

int main()
{
    // Тип коллекции
    typedef std::set<int> IntSet;
    IntSet coll;        // Контейнер для целых чисел
    // Вставка элементов со значениями от 1 до 6
    // - значение 1 вставляется дважды
    coll.insert(3);    coll.insert(1);    coll.insert(5);
    coll.insert(4);    coll.insert(1);    coll.insert(6);
    coll.insert(2);
    // Вывод содержимого множества
    // - перебор всех элементов.
    IntSet::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
}

int main()
{
    // Тип коллекции
    typedef std::multiset<int> IntSet;
    IntSet coll;        // Контейнер для целых чисел
    // Вставка элементов со значениями от 1 до 6
    // - значение 1 вставляется дважды
    coll.insert(3);    coll.insert(1);    coll.insert(5);
    coll.insert(4);    coll.insert(1);    coll.insert(6);
    coll.insert(2);
    // Вывод содержимого множества
    // - перебор всех элементов.
    IntSet::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
}

Различия

Элементами отображений и мультиотображений являются пары «ключ/значение».

• Для вставки элемента в коллекцию необходимо создать объект pair. Задача может решаться с помощью вспомогательной функции make_pair().
• Итератор ссылается на пару «ключ/значение», поэтому мы не можем просто направить его в выходной поток данных. Вместо этого приходится работать с отдельными членами структуры pair, которым присвоены имена first и second:
• выражение pos->first определяет первый компонент пары «ключ/значение», то есть ключ элемента мультиотображения.
• выражение pos->second определяет второй компонент пары «ключ/значение», то есть значение элемента мультиотображения.
• (Как и в случае с обычными указателями, это выражение представляет собой сокращенную запись для (*pos).second.)

Мультиотображение

using namespace std;
int main() {
    // Тип коллекции
    typedef multimap<int, string> IntStringMMap;
    IntStringMMap coll;  // Контейнер для хранения пар int/string
    // Вставка элементов в произвольном порядке
    // - значение с ключом 1 вставляется дважды.
    coll.insert(make_pair(5,"tagged"));   coll.insert(make_pair(2,"a"));
    coll.insert(make_pair(1,"this"));     coll.insert(make_pair(4,"of"));
    coll.insert(make_pair(6,"strings"));  coll.insert(make_pair(1,"is"));
    coll.insert(make_pair(3,"multimap"));
    // Вывод содержимого контейнера
    // - перебор всех элементов
    // - переменная second содержит значение.
    IntStringMMap::iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << pos->second << ' ';
    }
}

Отображение

using namespace std;
int main() {
    // Тип коллекции
    typedef map<int, string> IntStringMMap;
    IntStringMMap coll;  // Контейнер для хранения пар int/string
    // Вставка элементов в произвольном порядке
    // - значение с ключом 1 вставляется дважды.
    coll.insert(make_pair(5,"tagged"));   coll.insert(make_pair(2,"a"));
    coll.insert(make_pair(1,"this"));     coll.insert(make_pair(4,"of"));
    coll.insert(make_pair(6,"strings"));  coll.insert(make_pair(1,"is"));
    coll.insert(make_pair(3,"multimap"));
    // Вывод содержимого контейнера
    // - перебор всех элементов
    // - переменная second содержит значение.
    IntStringMMap::iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << pos->second << ' ';
    }
}

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

Набор пар «ключ/значение» с уникальными ключами (контейнер map) можно рассматривать как ассоциативный массив.

При работе с отображениями операция вставки может осуществляться оператором индексирования []:

std::map<string, float> coll;
coll["Pi"] = 3.1415;
coll["Null"] = 0;

• Индекс используется в качестве ключа и может иметь произвольный тип.
• Оператор индексирования в данном случае работает не так, как обычный оператор индексирования массивов. Отсутствие элемента, связанного с индексом, не является ошибкой. При появлении нового индекса (или ключа) создается и вставляется в контейнер новый элемент, ключом которого является указанный индекс. Таким образом, в ассоциативных массивах индекс в принципе не может принимать недопустимое значение. Следовательно, в приведенном коде создаются новые элементы. А оператор присваивания связывает ключи со значениями, преобразованными к типу float.

using namespace std;

int main()
{
    // Тип контейнера: map
    // - элементами являются пары "ключ/значение" типов string / float
    typedef map<string,float> StringFloatMap;
    StringFloatMap coll;
    // Вставка элементов в коллекцию
    coll["VAT"] = 0.15;                       coll["Pi"] = 3.1415;
    coll["an arbitrary number"] = 4983.223;   coll["Null"] = 0;
    // Вывод содержимого коллекции - перебор всех элементов
    // - first содержит ключ, second содержит значение
    StringFloatMap::iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        cout << "key: \"" << pos->first << "\" "
             << "value: " << pos->second << endl;
    }
}