• Главная
• Контакты
• Нашёл ошибку
• Прислать материал
• Добавить в избранное

Все контейнеры STL по-своему полезны, однако большинство программистов C++ работает с

vector

vector

string

В этой главе контейнеры

vector

string

vector

string

string

string

vector

vector<bool>

Принимая решение о динамическом выделении памяти оператором

new

1. Выделенная память в дальнейшем должна быть освобождена оператором

delete

new

delete

2. Освобождение должно выполняться соответствующей формой оператора

delete

delete

delete[]

delete

3. Оператор

delete

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

vector

string

Каждый раз, когда вы готовы прибегнуть к динамическому выделению памяти под массив (то есть собираетесь включить в программу строку вида «

new T[…]

vector

string

string

T

vector

vector<char>

vector

string

vector

string

Кроме того,

vector

string

begin

end

size

iterator, reverse_iterator, value_type

char*

string

Если вас беспокоит судьба унаследованного кода, работающего с массивами, не волнуйтесь и смело используйте

vector

string

vector

string

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

vector/string

string

string

string

Впрочем, оптимизация нередко оборачивается «пессимизацией». При использовании

string

string

Чтобы узнать, используется ли подсчет ссылок в вашей реализации

string

string

string

basic_string<char>

wstring

basic_string<wchar_t>

basic_string

string

Если доступная реализация

string

string

vector<char>

string

vector

vector<char>

string

Из всего сказанного можно сделать простой вывод — массивы с динамическим выделением памяти часто требуют лишней работы. Чтобы упростить себе жизнь, используйте

vector

string

Одной из самых замечательных особенностей контейнеров STL является автоматическое наращивание памяти в соответствии с объемом внесенных данных (при условии, что при этом не превышается максимальный размер контейнера — его можно узнать при помощи функции

max_size

vector

string

realloc

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

vector

string

2. Копирование всех элементов из старой памяти контейнера в новую память.

3. Уничтожение объектов в старой памяти.

4. Освобождение старой памяти.

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

vector

string

vector/string

Функция

reserve

vector

string

• Функция

size()

• Функция

capacity()

vector

string

size()

capacity()

size()

capacity()

insert

push_back

• Функция

resize(size_t n)

resize

size

n

n

n

n

•Функция

reserve(size_t n)

n

n

n

vector

string

size(), n

string

string

reserve

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

reserve

Предположим, вы хотите создать

vector<int>

reserve

vector<int> v;

for (int i=1; i<=1000; ++i) v.push_back(i):

В большинстве реализаций STL при выполнении этого фрагмента произойдет от 2 до 10 расширений контейнера. Кстати, число 10 объясняется очень просто. Вспомните, что при каждом перераспределении емкость

vector

1000

vector<int> v;

v.reserve(1000);

for (int i=1; i<=1000; ++i) v.push_back(i);

В этом случае количество расширений будет равно нулю.

Взаимосвязь между

size

capacity

vector

string

string s;

if (s.size() < s.capacity()) {

 s.push_back('x');

}

В этом фрагменте вызов

push_back

string

push_back

insert

string

Вернемся к основной теме настоящего совета. Существуют два основных способа применения функции

reserve

vector

reserve

Бьерн Страуструп однажды написал статью с интригующим названием «Sixteen Ways to Stack a Cat» [27], в которой были представлены разные варианты реализации стеков. Оказывается, по количеству возможных реализаций контейнеры

string

Например, сколько памяти занимает объект

string

sizeof(string)

char*

string

Оказывается, результат

sizeof(string)

string

char*

string

string

Практически каждая реализация

string

• размер строки, то есть количество символов;

• емкость блока памяти, содержащего символы строки (различия между размером и емкостью описаны в совете 14);

• содержимое строки, то есть символы, непосредственно входящие в строку.

Кроме того, в контейнере string может храниться:

• копия распределителя памяти. В совете 10 рассказано, почему это поле не является обязательным. Там же описаны странные правила, по которым работают распределители памяти.

Реализации

string

• счетчик ссылок для текущего содержимого.

В разных реализациях

string

string

В реализации A каждый объект

string

RefCnt

string

string

В реализации B объекты

string

string

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

Блок «Прочее» оказался больше остальных блоков, поскольку я постарался выдержать масштаб изображения. Если один блок вдвое больше другого, значит, он занимает вдвое больше памяти. В реализации B размер данных синхронизации примерно в шесть раз превышает размер указателя.

В реализации C размер объекта

string

В реализации D объекты

string

string

string

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

string

string s("Perse"); // Имя нашей собаки - Персефона, но мы

                   // обычно зовем ее просто "Перси"

в реализации D обходится без динамического выделения памяти, обходится одним выделением в реализациях A и C и двумя — в реализации B (для объекта, на который ссылается указатель

string

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

string

string

string

string

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

string s ("Perse"); // Строка s состоит из 5 символов

В реализации A минимальный размер выделяемого буфера равен 32 символам. Таким образом, хотя размер s во всех реализациях равен 5 символам, емкость этого контейнера в реализации A равна 31 (видимо, 32-й символ зарезервирован для завершающего нуль-символа, упрощающего реализацию функции

c_str

s

string

Из сказанного очевидно следует, что стратегия выделения памяти для малых строк может сыграть важную роль, если вы собираетесь работать с большим количеством коротких строк и (1) в вашей рабочей среде не хватает памяти или (2) вы стремитесь по возможности локализовать ссылки и пытаетесь сгруппировать строки в минимальном количестве страниц памяти.

Конечно, в выборе реализации

string

• По отношению к содержимому

string

• Объекты

string

char*

• Создание нового объекта

string

• Объекты

string

• Объекты

string

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

Только не поймите меня превратно. Я считаю, что контейнер

string

string

string

Кроме того, на концептуальном уровне контейнер

string

С момента стандартизации C++ в 1998 году элита C++ настойчиво подталкивает программистов к переходу с массивов на vector. Столь же открыто пропагандируется переход от указателей

char*

string

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

char*

vector

string

К счастью, задача решается просто. Если у вас имеется

vector v

v

&v[0]

string s

s.c_str()

Рассмотрим следующее объявление:

vector<int> v;

Выражение

v[0]

&v[0]

vector

void doSomething(const int* pInts, size_t numlnts);

Передача данных должна происходить так:

doSomething(&v[0], v.size());

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

v

v.size()

&v[0]

if (!v.empty()) {

 doSomething(&v[0], v.size());

}

Отдельные подозрительные личности утверждают, что

&v[0]

v.begin()

begin

vector

begin

vector

v.begin()

&*v.begin()

&v[0]

v.begin()

&v[0]

Способ получения указателя на данные контейнера, хорошо работающий для

vector

string

string

c_str

s

void doSomething(const char *pString);

происходит так:

doSomething(s.c_str());

Данное решение подходит и для строк нулевой длины. В этом случае

c_str

doSomething

string

char*

Вернемся к объявлениям doSomething:

void doSomething(const int* pints, size_t numInts);

void doSomething(const char *pString);

В обоих случаях передаются указатели на

const

vector

string

string

c_str

Vector предоставляет программисту чуть большую свободу действий. Передача

v

v

vector

v

v.size()

Вы обратили внимание на формулировку «обычно обходится без проблем» в предыдущем абзаце? Конечно, обратили. Некоторые векторы устанавливают для своих данных дополнительные ограничения, и при передаче вектора функции API, изменяющей его содержимое, вы должны проследить за тем, чтобы эти ограничения не были нарушены. Например, как объясняется в совете 23, сортируемые векторы часто могут рассматриваться в качестве разумной альтернативы для ассоциативных контейнеров, но при этом содержимое таких векторов должно оставаться правильно отсортированным. При передаче сортируемого вектора функции, способной изменить его содержимое, вам придется учитывать, что при возвращении из функции сортировка элементов может быть нарушена.

Если у вас имеется

vector

vector

// Функция fillArray получает указатель на массив.

// содержащий не более arraySize чисел типа double.

// и записывает в него данные. Возвращаемое количество записанных

// чисел заведомо не превышает maxNumDoubles.

size_t fillArray(double *pArray, size_t arraySize);

vector<double> vd(maxNumDoubles); // Создать vector, емкость которого

                                  // равна maxNumDoubles

vd.resize(fillArray(&vd[0], vd.size())); // Заполнить vd вызовом

                                         // функции fillArray, после чего

                                         // изменить размер по количеству

                                         // записанных элементов

Данный способ подходит только для

vector

string

vector<char>

string

// Функция получает указатель на массив, содержащий не более

// arraySize символов, и записывает в него данные.

// Возвращаемое количество записанных чисел заведомо не превышает

// maxNumChars

size_t fillString(char *pArray, sizet arraySize);

vector<char> vc(maxNumChars); // Создать vector, емкость которого

                              // равна maxNumChars

size_t charsWritten = fillString(&vc[0],vc.size()); // Заполнить vc

                                                    // вызовом fillString

string s(vc.begin(), vc.begin()+charsWritten); // Скопировать данные

                                               // из vc в s интервальным

                                               // конструктором (совет 5)

Собственно, сам принцип сохранения данных функцией API в

vector

size_t fillArray(double *pArray, size_t arraySize); // См. ранее

vector<double> vd(maxNumDoubles);// Также см. ранее

vd.resize(fillArray(&vd[0], vd.size());

deque<double> d(vd.begin(), vd.end()); // Копирование в deque

list<double> l(vd.begin(), vd.end()); // Копирование в list

set<double> s(vd.begin(), vd.end()); // Копирование в set

Более того, этот фрагмент подсказывает, как организовать передачу данных из других контейнеров STL, кроме

vector

string

vector

void doSomething(const int* pints, size_t numInts); // Функция C (см. ранее)

set<int> intSet; // Множество, в котором

…                // хранятся передаваемые

                 // данные

vector<int> v(intSet.begin(), intSet.end());// Скопировать данные

                                            // из set в vector

if (!v.empty()) doSomething(&v[0], v.size()); // Передать данные

                                              // функции С

Вообще говоря, данные также можно скопировать в массив и передать их функции C, но зачем это нужно? Если размер контейнера не известен на стадии компиляции, память придется выделять динамически, а в совете 13 объясняется, почему вместо динамических массивов следует использовать

vector

Предположим, вы пишете программу для нового телешоу «Бешеные деньги». Информация о потенциальных участниках хранится в векторе:

class Contestant {…};

vector<Contestant> contestants;

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

partial_sort

partition

erase

Чтобы вектор не удерживал ненужную память, необходимы средства, которые бы позволяли сократить емкость от максимальной до используемой в настоящий момент. Подобное сокращение емкости обычно называется «сжатием по размеру». Сжатие по размеру легко программируется, однако код — как бы выразиться поделикатнее? — выглядит недостаточно интуитивно. Давайте разберемся, как он работает.

Усечение лишней емкости в векторе contestants производится следующим образом:

vector<Contestant>(contestants).swap(contestants);

Выражение

vector<Contestant>(contestants)

contestants

vector

vector

contestants

swap

contestants

contestants

contestants

Аналогичный прием применяется и по отношению к строкам:

string s; // Создать большую строку и удалить из нее

…         // большую часть символов

string(s).swap(s); // Выполнить "сжатие по размеру" с объектом s

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

vector

string

vector/string

string

vector

vector

string

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

vector

string

vector<Contestant> v;

string s;

… // Использовать v и s

vector<Contestant>().swap(v); // Очистить v с уменьшением емкости

string().swap(s); // Очистить s с уменьшением емкости

Остается сделать последнее замечание, относящееся к функции

swap

swap

Vector<bool> как контейнер STL обладает лишь двумя недостатками. Во-первых, это вообще не контейнер STL. Во-вторых, он не содержит

bool

Объект не становится контейнером STL только потому, что кто-то назвал его таковым — он становится контейнером STL лишь при соблюдении всех требований, изложенных в разделе 23.1 Стандарта C++. В частности, в этих требованиях говорится, что если 

c

T

[]

T *р = &с[0];// Инициализировать T* адресом данных,

             // возвращаемых оператором []

Иначе говоря, если оператор

[]

T

Container<T>

&

T

vector<bool>

vector<bool> v;

bool *pb = &v[0]; // Инициализировать bool* адресом результата,

                  // возвращаемого оператором vector<bool>::operator[]

Однако приведенный фрагмент компилироваться не будет. Дело в том, что

vector<bool>

bool

bool

bool

vector<bool>

Битовые поля, как и

bool

bool

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

vector<bool>

vector<T>::operator[]

T&

vector<bool>

bool

vector<T>::operator[]

Чтобы справиться с этим затруднением, функция

vector<T>::operator[]

vector<bool>

template <typename Allocator>

vector<bool, Allocator> {

public:

 class reference {…};// Класс, генерирующий промежуточные

                     // объекты для ссылок на отдельные биты

 reference operator[](size_type n); // operator[] возвращает

 …                                  // промежуточный объект

};

Теперь понятно, почему следующий фрагмент не компилируется:

vector<bool> v;

bool *pb=&v[0]; // Ошибка! Выражение в правой части относится к типу

                // vector<bool>::reference*, а не bool*

А раз фрагмент не компилируется,

vector<bool>

vector<bool>

Спрашивается, почему же

vector<bool>

vector<bool>

В стандартную библиотеку входят два альтернативных решения, которые подходят практически для любых ситуаций. Первое решение —

deque<bool>

deque

vector

reserve

capacity

deque<bool>

bool

deque

deque<bool>

bool

vector<bool>

vector<bool>

vector

vector<bool>

vector<bool>

bool

Второй альтернативой для

vector<bool>

bitset

bitset

bitset

bitset

bitset

vector<bool>

flip

vector<bool>

bitset

А теперь вернемся к благородному, но неудачному эксперименту, из-за которого появился «псевдоконтейнер»

vector<bool>

vector<bool>

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

vector<bool>

vector<bool>

deque<bool>

bitset

vector<bool>