Стандартная библиотека шаблонов

Использование STL в C++

Библиотека стандартных шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

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

· vector - коллекция элементов Т, сохраненных в массиве, увеличиваемом по мере необходимости. Для того, чтобы начать использование данной коллекции, включите #include <vector>.

· list - коллекция элементов Т, сохраненных, как двунаправленный связанный список. Для того, чтобы начать использование данной коллекции, включите #include <list>.

· map - это коллекция, сохраняющая пары значений pair<const Key, T>. Эта коллекция предназначена для быстрого поиска значения T по ключу const Key. В качестве ключа может быть использовано все, что угодно, например, строка или int но при этом необходимо помнить, что главной особенностью ключа является возможность применить к нему операцию сравнения. Быстрый поиск значения по ключу осуществляется благодаря тому, что пары хранятся в отсортированном виде. Эта коллекция имеет соответственно и недостаток - скорость вставки новой пары обратно пропорциональна количеству элементов, сохраненных в коллекции, поскольку просто добавить новое значение в конец коллекции не получится. Еще одна важная вещь, которую необходимо помнить при использовании данной коллекции - ключ должен быть уникальным. Для того, чтобы начать использование данной коллекции, включите #include <map>. Если вы хотите использовать данную коллекцию, чтобы избежать дубликатов, то вы избежите их только по ключу.

· set - это коллекция уникальных значений const Key - каждое из которых является также и ключом - то есть, проще говоря, это отсортированная коллекция, предназначенная для быстрого поиска необходимого значения. К ключу предъявляются те же требования, что и в случае ключа для map. Естественно, использовать ее для этой цели нет смысла, если вы хотите сохранить в ней простые типы данных, по меньшей мере вам необходимо определить свой класс, хранящий пару ключ - значение и определяющий операцию сравнения по ключу. Очень удобно использовать данную коллекцию, если вы хотите избежать повторного сохранения одного и того же значения. Для того, чтобы начать использование данной коллекции, включите #include <set>.

· multimap - это модифицированный map, в котором отсутствует требования уникальности ключа - то есть, если вы произведете поиск по ключу, то вам вернется не одно значение, а набор значений, сохраненных с данным ключом. Для того, чтобы начать использование данной коллекции включите #include <map>.

· multiset - то же самое относится и к этой коллекции, требования уникальности ключа в ней не существует, что приводит к возможности хранения дубликатов значений. Тем не менее, существует возможность быстрого нахождения значений по ключу в случае, если вы определили свой класс. Поскольку все значения в map и set хранятся в отсортированном виде, то получается, что в этих коллекциях мы можем очень быстро отыскать необходимое нам значение по ключу, но при этом операция вставки нового элемента T будет стоить нам несколько дороже, чем например в vector. Для того, чтобы начать использование данной коллекции, включите #include <set>.

STL Строки

Не существует серьезной библиотеки, которая бы не включала в себя свой класс для представления строк или даже несколько подобных классов. STL - строки поддерживают как формат ASCII, так и формат Unicode.

· string - представляет из себя коллекцию, хранящую символы char в формате ASCII. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include <string>.

· wstring - это коллекция для хранения двухбайтных символов wchar_t, которые используются для представления всего набора символов в формате Unicode. Для того, чтобы использовать данную коллекцию, вам необходимо включить #include <xstring>.

Строковые потоки

Используются для организации сохранения простых типов данных в STL строки в стиле C++. Практическое знакомство с STL мы начнем именно с этого класса. Ниже приведена простая программа, демонстрирующая возможности использования строковых потоков:

//stl.cpp: Defines the entry point for the console application

#include <iostream>

#include <strstream>

#include <string>

using namespace std;

 

int main()

{

strstream xstr;

for (int i = 0; i < 10; i++)

{

xstr << "Demo " << i << endl;

}

cout << xstr.str();

string str;

str.assign(xstr.str(), xstr.pcount());

cout << str.c_str();

return 0;

}

Строковый поток - это просто буфер, в конце которого установлен нуль терминатор, поэтому мы наблюдаем в конце строки мусор при первой распечатке, то есть реальный конец строки определен не посредством нуль терминатора, а с помощью счетчика, и его размер мы можем получить с помощью метода: pcount ().

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

Основные методы, которые присутствуют почти во всех STL коллекциях, приведены ниже.

· empty - определяет, является ли коллекция пустой.

· size - определяет размер коллекции.

· begin - возвращает прямой итератор, указывающий на начало коллекции.

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

· rbegin - возвращает обратный итератор, указывающий на начало коллекции.

· rend - возвращает обратный итератор, указывающий на конец коллекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следующий за последним.

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

· erase - удаляет элемент или несколько элементов из коллекции.

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

#include <iostream>

#include <vector>

using namespace std;

 

int main()

{

vector<int> vec;

cout << "Real size of array in vector: " << vec.capacity()

<< endl;

for (int j = 0; j < 10; j++)

{

vec.push_back(10);

}

cout << "Real size of array in vector: " << vec.capacity()

<< endl;

return 0;

}

При использовании микрософтовской реализации STL библиотеки (Visual C++ 7.0) у автора получилось 0 и 13 соответственно до и после заполнения вектора.

Vector

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

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

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

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

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

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

#include <iostream>

#include <strstream>

#include <string>

#include <vector>

#include <algorithm>

 

using namespace std;

 

class MyMessage

{

private:

string from;

string to;

string message;

int id;

public:

MyMessage(string from, string to, string message)

{

this ->from = from;

this ->to = to;

this ->message = message;

}

int GetId()

{

return this ->id;

}

void SetId(int id)

{

this ->id = id;

}

string GetMessage()

{

return this ->message;

}

string GetFrom()

{

return this ->from;

}

string GetTo()

{

return this ->to;

}

};

 

int main()

{

vector<MyMessage> common;

// create pool of messages for 3 users:

for (int user = 0; user < 3; user++)

{

for (int i = 0; i < 10; i++)

{

strstream messagex;

messagex << "Message " << i;

string smessage;

smessage.assign(messagex.str(), messagex.pcount());

strstream userx;

userx << "User " << user;

string suser;

suser.assign(userx.str(), userx.pcount());

MyMessage message("Administrator", suser, smessage);

message.SetId(user * 10 + i);

common.push_back(message);

}

}

 

// create vector for each user:

vector<MyMessage> user0;

vector<MyMessage> user1;

vector<MyMessage> user2;

for (int x = 0; x < (int)common.size(); x++)

{

MyMessage message = common[x];

if (message.GetTo() == "User 0")

{

user0.push_back(message);

}

else

if (message.GetTo() == "User 1")

{

user1.push_back(message);

}

else

if (message.GetTo() == "User 2")

{

user2.push_back(message);

}

}

 

cout << "Messages for user 2: " << endl;

for (int i = 0; i < (int)user2.size(); i++)

{

MyMessage message = user2[i];

cout << message.GetTo() << endl;

}

cout << "Messages for user 1: " << endl;

for (int i = 0; i < (int)user1.size(); i++)

{

MyMessage message = user1[i];

cout << message.GetTo() << endl;

}

cout << "Messages for user 0: " << endl;

for (int i = 0; i < (int)user0.size(); i++)

{

MyMessage message = user0[i];

cout << message.GetTo() << endl;

}

 

cout << "Size of common vector: " << (int)common.size()

<< endl;

return 0;

}

Теперь у вас есть некоторое представление о том, каким образом писать бизнес - логику приложений с использованием STL. Из этого приложения видно, что кроме перечисленных выше методов, у вектора есть оператор operator [], который позволяет нам пользоваться вектором так же, как обычным массивом. Этот оператор используется также в map, deque, string и wstring.

Итераторы

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

class Iterator

{

T* pointer;

public:

T* GetPointer ()

{

return this - >pointer;

}

void SetPointer (T* pointer)

{

this - >pointer = pointer;

}

:

};

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