Что такое контейнерный класс

vector films;

Эквивалентное объявление, использующее класс Qt -- QValueVector :

QValueVector films;

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

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

films.push_back(Film(4812, "A Hard Day's Night", 85)); films.push_back(Film(5051, "Seven Days to Noon", 94)); films.push_back(Film(1301, "Day of Wrath", 105)); films.push_back(Film(9227, "A Special Day", 110)); films.push_back(Film(1817, "Day for Night", 116));

Как правило, Qt предоставляет функции с теми же именами, что и STL, но в некоторых случаях Qt добавляет к классам дополнительные методы, с более интуитивно понятными именами. Например, классы Qt могут добавлять элементы как с помощью метода push_back(), так и с помощью дополнительного метода append().

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

vector films(5); films[0] = Film(4812, "A Hard Day's Night", 85); films[1] = Film(5051, "Seven Days to Noon", 94); films[2] = Film(1301, "Day of Wrath", 105); films[3] = Film(9227, "A Special Day", 110); films[4] = Film(1817, "Day for Night", 116);

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

Векторы допускают обход всех элементов в цикле, с использованием оператора "[ ]":

for (int i = 0; i < (int)films.size(); ++i) cerr 
В качестве альтернативы -- можно использовать итератор:
vector::const_iterator it = films.begin(); while (it != films.end())
Каждый контейнерный класс имеет два типа итераторов: iterator и const_iterator. Различие между ними заключается в том, что const_iterator не позволяет модифицировать элементы вектора.
Функция-член контейнера -- begin() возвращает итератор, который ссылается на первый элемент в контейнере (например, films[0]). Функция-член контейнера -- end() возвращает итератор, который ссылается на элемент "следующий за последним" (например, films[5]). Если контейнер пуст, значения, возвращаемые функциями begin() и end(), эквивалентны. Это обстоятельство может использоваться для проверки наличия элементов в контейнере, хотя для этой цели гораздо удобнее использовать функцию empty().






Итераторы обладают интуитивно понятным синтаксисом, который напоминает синтаксис указателей языка C++. Для перемещения к следующему или предыдущему элементу, можно использовать операторы "++" b "--", а унарный "*" -- для получения доступа к элементу контейнера, находящемуся в позиции итератора.
Если необходимо отыскать некоторый элемент в векторе, можно воспользоваться функцией STL -- find():
vector::iterator it = find(films.begin(), films.end(), Film(4812)); if (it != films.end()) films.erase(it);
Она возвращает итератор, указывающий на первый встретившийся элемент вектора, отвечающий критериям поиска (элементы контейнера сравниваются перегруженным operator==() с последним аргументом функции). Определение функции находится в заголовке , где вы найдете множество других шаблонных функций. Qt предоставляет аналоги некоторых из них, правда под другими именами (например, qFind()). Вы можете использовать их, если не желаете пользоваться библиотекой STL.

Сортировка элементов вектора может быть произведена функцией sort():






sort(films.begin(), films.end());
Для сравнения элементов вектора она использует оператор "<", если явно не указывается другая функция сравнения. На отсортированных векторах, для поиска некоторого элемента может использоваться функция binary_search(). Она дает результат, аналогичный find() (при условии, что в векторе нет двух фильмов с одинаковыми числовыми идентификаторами), но при этом работает намного быстрее.
int if (binary_search(films.begin(), films.end(), Film(id))) cerr 
В позицию итератора, с помощью функции insert(), может быть вставлен новый элемент или удален существующий, с помощью функции erase():
films.erase(it);
Элементы, которые следуют за удаляемым будут перемещены на одну позицию влево (или выше, если хотите) и размер вектора будет уменьшен на 1 элемент.


Пред.
В начало
След.


Взаимодействия между процессами.
На уровень выше
Списки.


16.6 – Контейнерные классы
В реальной жизни мы постоянно используем контейнеры. Сухие завтраки поставляются в коробках, страницы в вашей книге находятся внутри обложки и переплета, и вы можете хранить любое количество предметов в контейнерах в своем гараже. Без контейнеров было бы крайне неудобно работать со многими из этих объектов. Представьте, что вы пытаетесь прочитать книгу без какого-либо переплета или съесть хлопья, которые не были в коробке, и без тарелки. Это был бы бардак. Ценность контейнера в основном заключается в его способности помогать организовывать и хранить предметы, помещенные в него.
Точно так же контейнерный класс – это класс, предназначенный для хранения и организации нескольких экземпляров другого типа (либо другого класса, либо базового типа). Существует множество различных типов контейнерных классов, каждый из которых имеет различные преимущества, недостатки и ограничения в использовании. Безусловно, наиболее часто используемым контейнером в программировании является массив, примеры которого вы уже видели. Хотя C++ имеет встроенную поддержку массивов, программисты часто используют вместо него контейнерные классы массивов ( std::array или std::vector ) из-за дополнительных преимуществ, которые они предоставляют. В отличие от встроенных массивов, классы-контейнеры массивов обычно обеспечивают динамическое изменение размера (при добавлении или удалении элементов), запоминают свой размер при передаче в функции и выполняют проверку границ. Это не только делает классы-контейнеры массивов более удобными, чем обычные массивы, но и более безопасными.






Классы-контейнеры обычно реализуют довольно стандартный минимальный набор функций. Большинство хорошо определенных контейнеров будут включать функции, которые:

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

Иногда некоторые классы-контейнеры опускают некоторые из этих функций. Например, классы-контейнеры массивов часто опускают функции вставки и удаления, потому что они медленные, и разработчик класса не хочет поощрять их использование.
Классы-контейнеры реализуют связь «член чего-либо». Например, элементы массива являются членами (принадлежат) массива. Обратите внимание, что мы используем термин «член» в общепринятом смысле, а не в смысле члена класса C++.
Типы контейнеров
Классы контейнеров обычно бывают двух разных видов. Контейнеры значений – это композиции, в которых хранятся копии хранимых объектов (и, таким образом, контейнеры несут ответственность за создание и уничтожение этих копий). Контейнеры ссылок – это агрегации, которые хранят указатели или ссылки на другие объекты (и, следовательно, не несут ответственности за создание или уничтожение этих объектов).
В отличие от реальной жизни, где контейнеры могут содержать любые типы объектов, которые вы в них помещаете, в C++ контейнеры обычно содержат только один тип данных. Например, если у вас есть массив чисел int , он будет содержать только числа int . В отличие от некоторых других языков, многие контейнеры C++ не позволяют произвольно смешивать типы. Если вам нужны контейнеры для хранения чисел int и double , вам, как правило, придется написать для этого два отдельных контейнера (или использовать шаблоны, что является расширенной функцией C++). Несмотря на ограничения использования, контейнеры чрезвычайно полезны и делают программирование проще, безопаснее и быстрее.






Контейнерный класс массива
В этом примере мы собираемся написать класс массива значений int с нуля, который реализует большую часть общих функций, которые должны иметь контейнеры. Этот класс массива будет контейнером значений, в котором будут храниться копии элементов. Как следует из названия, контейнер будет содержать массив чисел int , аналогичный std::vector .
Сначала создадим файл IntArray.h :
#ifndef INTARRAY_H #define INTARRAY_H class IntArray < >; #endif
Нашему классу IntArray нужно будет отслеживать два значения: сами данные и размер массива. Поскольку мы хотим, чтобы наш массив мог изменяться в размере, нам нужно будет выполнить какое-то динамическое размещение, что означает, что для хранения данных нам придется использовать указатель.
#ifndef INTARRAY_H #define INTARRAY_H class IntArray < private: int m_length<>; int *m_data<>; >; #endif
Теперь нам нужно добавить несколько конструкторов, которые позволят нам создавать объекты IntArray . Мы собираемся добавить два конструктора: один, который создает пустой массив, и второй, который позволит нам создать массив заранее определенного размера.






#ifndef INTARRAY_H #define INTARRAY_H #include // for assert() class IntArray < private: int m_length<>; int *m_data<>; public: IntArray() = default; IntArray(int length): m_length < length >< assert(length >= 0); if (length > 0) m_data = new int[length]<>; > >; #endif
Нам также понадобятся функции, которые помогут очистить объекты IntArray . Сначала мы напишем деструктор, который просто освобождает любые динамически размещенные данные. А затем напишем функцию с именем erase() , которая сотрет массив и установит значение длины в 0.
~IntArray() < delete[] m_data; // здесь нам не нужно устанавливать m_data в значение null // или m_length в 0, так как объект в любом случае будет // уничтожен сразу после этой функции >void erase() < delete[] m_data; // Нам нужно убедиться, что мы установили здесь m_data // равным nullptr, иначе это оставит указатель // указывающим на освобожденную память! m_data = nullptr; m_length = 0; >
Теперь давайте перегрузим operator[] , чтобы мы могли получить доступ к элементам массива. Мы должны проверить индекс, чтобы убедиться, что он корректен, что лучше всего сделать с помощью функции assert() . Также добавим функцию доступа для получения длины массива. Пока всё:
#ifndef INTARRAY_H #define INTARRAY_H #include // для assert() class IntArray < private: int m_length<>; int *m_data<>; public: IntArray() = default; IntArray(int length): m_length < length >< assert(length >= 0); if (length > 0) m_data = new int[length]<>; > ~IntArray() < delete[] m_data; // здесь нам не нужно устанавливать m_data в значение null // или m_length в 0, так как объект в любом случае будет // уничтожен сразу после этой функции >void erase() < delete[] m_data; // Нам нужно убедиться, что мы установили здесь m_data // равным nullptr, иначе это оставит указатель // указывающим на освобожденную память! m_data = nullptr; m_length = 0; >int& operator[](int index) < assert(index >= 0 && index < m_length); return m_data[index]; >int getLength() const < return m_length; >>; #endif
На данный момент у нас есть класс IntArray , который мы уже можем использовать. Мы можем размещать объекты IntArray заданного размера и можем использовать operator[] для извлечения или изменения значений элементов.
Однако есть еще кое-что, что мы не можем сделать с нашим объектом IntArray . Мы по-прежнему не можем изменить его размер, по-прежнему не можем вставлять или удалять элементы и по-прежнему не можем отсортировать его.
Во-первых, давайте напишем код, который позволит нам изменять размер массива. Для этого мы напишем две разные функции. Первая функция, reallocate() , уничтожает все существующие элементы в массиве при изменении его размера, но она будет быстрой. Вторая функция, resize() , сохраняет все существующие элементы в массиве при изменении его размера, но она будет медленной.






// reallocate изменяет размер массива. Любые существующие элементы // будут уничтожены. Эта функция работает быстро. void reallocate(int newLength) < // Сначала мы удаляем все существующие элементы erase(); // Если теперь наш массив будет пустым, возвращаемся отсюда if (newLength // resize изменяет размер массива. Любые существующие элементы // будут сохранены. Эта функция работает медленно. void resize(int newLength) < // если массив уже имеет нужную длину, мы закончили if (newLength == m_length) return; // Если мы изменяем размер до пустого массива, делаем это и возвращаемся if (newLength // Теперь мы можем предположить, что newLength - это как минимум 1 элемент. // Этот алгоритм работает следующим образом: // Сначала размешаем новый массив. // Затем копируем элементы из существующего массива в новый массив. // Как только это будет сделано, можно уничтожить старый массив // и заставить m_data указывать на новый массив. // Сначала мы должны разместить новый массив int *data< new int[newLength] >; // Затем нам нужно выяснить, сколько элементов скопировать из // существующего массива в новый массив. Мы хотим скопировать // столько элементов, сколько есть в меньшем из двух массивов. if (m_length > 0) < int elementsToCopy< (newLength >m_length) ? m_length : newLength >; // Теперь копируем элементы один за другим for (int index< 0 >; index < elementsToCopy ; ++index) data[index] = m_data[index]; >// Теперь мы можем удалить старый массив, потому что он нам больше не нужен delete[] m_data; // И вместо него используем новый массив! Обратите внимание, что это просто // заставляет m_data указывать на адрес нового массива, который мы // разместили динамически. Поскольку данные были размещены динамически, // они не будут уничтожены, когда выйдут за пределы области видимости. m_data = data; m_length = newLength; >
Ух! Это было немного сложно!
Многие контейнерные классы массивов на этом останавливаются. Однако на всякий случай, если вы хотите увидеть, как будут реализованы функции вставки и удаления, мы напишем и их. Алгоритмы их обеих очень похожи на resize() .
void insertBefore(int value, int index) < // Проверяем значение нашего индекса на корректность assert(index >= 0 && index ; // Копируем все элементы до индекса for (int before< 0 >; before < index; ++before) data[before] = m_data[before]; // Вставляем наш новый элемент в новый массив data [index] = value; // Копируем все значения после вставленного элемента for (int after< index >; after < m_length; ++after) data[after+1] = m_data[after]; // Наконец, удаляем старый массив и используем вместо него новый delete[] m_data; m_data = data; ++m_length; >void remove(int index) < // Проверяем значение нашего индекса на корректность assert(index >= 0 && index < m_length); // Если это последний элемент в массиве, // делаем массив пустым и выходим if (m_length == 1) < erase(); return; >// Сначала создаем новый массив на один элемент меньше старого массива int *data< new int[m_length-1] >; // Копируем все элементы до индекса for (int before< 0 >; before < index; ++before) data[before] = m_data[before]; // Копируем все значения после удаленного элемента for (int after< index+1 >; after < m_length; ++after) data[after-1] = m_data[after]; // Наконец, удаляем старый массив и используем вместо него новый delete[] m_data; m_data = data; --m_length; >// Пара дополнительных функций для удобства void insertAtBeginning(int value) < insertBefore(value, 0); >void insertAtEnd(int value) < insertBefore(value, m_length); >_м); >
Ниже приведен наш контейнерный класс IntArray целиком.
#ifndef INTARRAY_H #define INTARRAY_H #include // для assert() class IntArray < private: int m_length<>; int *m_data<>; public: IntArray() = default; IntArray(int length): m_length < length >< assert(length >= 0); if (length > 0) m_data = new int[length]<>; > ~IntArray() < delete[] m_data; // здесь нам не нужно устанавливать m_data в значение null // или m_length в 0, так как объект в любом случае будет // уничтожен сразу после этой функции >void erase() < delete[] m_data; // Нам нужно убедиться, что мы установили здесь m_data // равным nullptr, иначе это оставит указатель // указывающим на освобожденную память! m_data = nullptr; m_length = 0; >int& operator[](int index) < assert(index >= 0 && index < m_length); return m_data[index]; >// reallocate изменяет размер массива. Любые существующие элементы // будут уничтожены. Эта функция работает быстро. void reallocate(int newLength) < // Сначала мы удаляем все существующие элементы erase(); // Если теперь наш массив будет пустым, возвращаемся отсюда if (newLength // resize изменяет размер массива. Любые существующие элементы // будут сохранены. Эта функция работает медленно. void resize(int newLength) < // если массив уже имеет нужную длину, мы закончили if (newLength == m_length) return; // Если мы изменяем размер до пустого массива, делаем это и возвращаемся if (newLength // Теперь мы можем предположить, что newLength - это как минимум 1 элемент. // Этот алгоритм работает следующим образом: // Сначала размешаем новый массив. // Затем копируем элементы из существующего массива в новый массив. // Как только это будет сделано, можно уничтожить старый массив // и заставить m_data указывать на новый массив. // Сначала мы должны разместить новый массив int *data< new int[newLength] >; // Затем нам нужно выяснить, сколько элементов скопировать из // существующего массива в новый массив. Мы хотим скопировать // столько элементов, сколько есть в меньшем из двух массивов. if (m_length > 0) < int elementsToCopy< (newLength >m_length) ? m_length : newLength >; // Теперь копируем элементы один за другим for (int index< 0 >; index < elementsToCopy ; ++index) data[index] = m_data[index]; >// Теперь мы можем удалить старый массив, потому что он нам больше не нужен delete[] m_data; // И вместо него используем новый массив! Обратите внимание, что это просто // заставляет m_data указывать на адрес нового массива, который мы // разместили динамически. Поскольку данные были размещены динамически, // они не будут уничтожены, когда выйдут за пределы области видимости. m_data = data; m_length = newLength; > void insertBefore(int value, int index) < // Проверяем значение нашего индекса на корректность assert(index >= 0 && index ; // Копируем все элементы до индекса for (int before< 0 >; before < index; ++before) data [before] = m_data[before]; // Вставляем наш новый элемент в новый массив data[index] = value; // Копируем все значения после вставленного элемента for (int after< index >; after < m_length; ++after) data[after+1] = m_data[after]; // Наконец, удаляем старый массив и используем вместо него новый delete[] m_data; m_data = data; ++m_length; >void remove(int index) < // Проверяем значение нашего индекса на корректность assert(index >= 0 && index < m_length); // Если это последний элемент в массиве, // делаем массив пустым и выходим if (m_length == 1) < erase(); return; >// Сначала создаем новый массив на один элемент меньше старого массива int *data< new int[m_length-1] >; // Копируем все элементы до индекса for (int before< 0 >; before < index; ++before) data[before] = m_data[before]; // Копируем все значения после удаленного элемента for (int after< index+1 >; after < m_length; ++after) data[after-1] = m_data[after]; // Наконец, удаляем старый массив и используем вместо него новый delete[] m_data; m_data = data; --m_length; >// Пара дополнительных функций для удобства void insertAtBeginning(int value) < insertBefore(value, 0); >void insertAtEnd(int value) < insertBefore(value, m_length); >int getLength() const < return m_length; >>; #endif
А теперь давайте протестируем его, чтобы убедиться, что он работает:
#include #include "IntArray.h" int main() < // Объявляем массив из 10 элементов IntArray array(10); // Заполняем массив числами от 1 до 10 for (int i< 0 >; i; i
Эта программа дает следующий результат:






40 1 2 3 5 20 6 7 8 30
Хотя написание контейнерных классов может быть довольно сложным, хорошая новость заключается в том, что вам нужно написать их только один раз. Как только контейнерный класс заработает, вы можете повторно использовать его так часто, как захотите, без каких-либо дополнительных усилий по написанию кода.
Также стоит прямо упомянуть, что даже несмотря на то, что наш пример класса-контейнера IntArray хранит значения встроенного типа данных ( int ), мы могли бы так же легко использовать пользовательский тип (например, класс Point ).
Еще один момент: если класс из стандартной библиотеки соответствует вашим потребностям, используйте его вместо создания своего собственного. Например, вместо IntArray лучше использовать std::vector . Он протестирован в боевых условиях, эффективен и прекрасно сочетается с другими классами стандартной библиотеки. Но иногда вам может понадобиться специализированный контейнерный класс, которого нет в стандартной библиотеке, поэтому полезно знать, как создать свой собственный контейнер, когда вам это нужно. Мы поговорим о контейнерах стандартной библиотеки, когда рассмотрим еще несколько базовых тем.
Контейнерные классы
 






Контейнерные классы 
Контейнерные классы — это классы, предназначенные для хранения 
данных, организованных определенным образом. Примерами 
контейнеров могут служить массивы, линейные списки или стеки. Для 
каждого типа контейнера определены методы для работы с его 
элементами, не зависящие от конкретного типа данных, которые 
хранятся в контейнере, поэтому один и тот же, вид контейнера можно 
использовать для хранения, данных различных типов. Эта возможность 
реализована с помощью шаблонов классов, поэтому часть библиотеки 
С++, в которую входят контейнерные классы, а также алгоритмы и 
итераторы, о которых будет рассказано в следующих разделах, 
называют стандартной библиотекой "шаблонов (STL — Standard 
Template library). 
STL содержит контейнеры, реализующие основные структуры данных, 
используемые при написании программ — векторы, двусторонние 
очереди, списки и их разновидности, словари и множества. Контейнеры 
можно разделить на два тала: последовательные и ассоциативные. 
2. 
Итератор является аналогом указателя на элемент. Он используется для просмотра 
контейнера в прямом или обратном направлении. Все, что требуется от итератора — 
уметь ссылаться на элемент контейнера и реализовывать операцию - перехода к его 
следующему элементу. Константные итераторы используются тoгда, когда значения, 
соответствующих элементов контейнера не изменяются. 
При помощи итераторов просматривать контейнеры не заботясь о фактических типах 
данных, используемых для доступа к элементам. 
Для этого в каждом контейнере определено несколько методов, перечисленных ниже. 
Метод 
Пояснение 
iterator begin(), 
const_iterator begin() const 
Указывают на первый элемент 
iterator end(), 
const_itepator end() const 
Указывают на элемент, следующей 
за последним: 
reverse iterator rbegin(), 
Const_reverse_iterator rbegin() const 
Указывают на первый элемент в 
обратной последовательности 
reverse_iterator rend(), 
const_reverse_iterator rend() const 
Указывают на элемент, следующий 
за последним, в обратной последовательности 
3. 
Во всех контейнерах определены методы, позволяющие 
получить сведения о размере контейнеров: 
Метод 
size() 
Пояснение 
Число элементов 
maxsize() 
Максимальный размер контейнера 
(порядка миллиарда элементов) 
empty() 
Булевская функция, показывающая, 
пуст ли контейнер 
4. 
Последовательные контейнеры 
Векторы (vector), двусторонние очереди (deque) и списки (1ist) 
поддерживают разные наборы операций, среди которых есть 
совпадающие операции. Они, могут быть реализованы с 
разной эффективностью: 
Операция 
Вставка в начало 
Удаление из начала 
Вставка в конец 
Удаление из конца 
Вставка в 
произвольное место 
Удаление из 
произвольного места 
Произвольный 
доступ к элементу 
Метод 
push_front 
pop_front 
push_back 
pop_back 
insert 
vector 
+ 
+ 
(+) 
deque 
+ 
+ 
+ 
+ 
(+) 
list 
+ 
+ 
+ 
+ 
+ 
erase 
(+) 
(+) 
+ 
[].at 
+ 
+ 
- 
5. 
Знак + означает, что соответствующая операция реализуется за 
постоянное время, не зависящее от количества n элементов в 
контейнере. Знак (+) означает, что соответствующая операция 
реализуется за время, пропорциональное n. Для малых n время 
операций, обозначенных +, может превышать время операций, 
обозначенных (+). но для большого количества элементов последние 
могут оказаться очень дорогими. 
Итак, вектор — это структура, эффективно реализующая 
произвольный доступ к элементам, добавление, в конец и 
удаление из конца. 
Двусторонняя очередь эффективно реализует произвольный 
доступ к элементам, добавление в оба конца и удаление из 
обоих, концов. 
Список эффективно реализует вставку и удаление элементов в 
произвольное место, но не имеет произвольного доступа к 
своим элементам. 






6. 
Вектор 
Примеры конструкторов: 
Создает вектор из 10 равных единице элементов: 
vector v2 (10,1); 
Создается вектор, равный вектору v1: 
vector v4(v1); 
Создается вектор из двух элементов, равных первым двум 
элементам v1: 
vector v3 (v1.begin(), v1.begin()+ 2); 
Создается вектор из 10 объектов класса monstr 
(работает конструктор по умолчаний): 
vector m1(10); 
Создается вектор из 5 объектов класса monstr с заданным именем 
(работает конструктор с параметров char*): 
vector m2 (5, monstr("Вася")); 
В шаблоне vector определены операция присваивания и функция 
копирования: 
7. 
vector& operator=(const vector &х); 
void assign(size_type n, const Т &value); 
template «class InputIter> 
void assign(InputIter first, InputIter last); 
Здесь через T обозначен тип элементов вектора. Вектора можно 
присваивать друг другу точно так же, как стандартные типы данных 
или строки. После присваивания размер вектора становится равным 
новому значению, все старые элементы удаляются. 
Примеры: 
vector v1,v2; 
Первым 10 элементам вектора v1 присваивается значение 1: 
v1.assign(10,1); 
Первым 3 элементам вектора v2 присваиваются значения v1[5], 
v1[6], vl[7]: v2.assign(v1.begin()+5,v1.begin()+8); 
Для векторов определены операции сравнения ==, !=, 
8. 
Пример. В файле находится произвольное количество целых чисел. 
Программа считывает их в вектор и выводит на экран в том же порядке. 
#include  
#include  
#include  
#include  
using namespace std; 
void main() ifstream in("input.txt"); 
vector v; 
vector ::iterator i; 
int x; 
do < in>>x; v.push_back(x); 
> while (!in.eof()); 
sort(v.begin(),v.end()); 
for (i= v.begin(); i!=v.end();i++) 
cout > 
9. 
Двусторонние очереди (deque) 
Двусторонняя очередь – это последовательный контейнер, который, 
наряду с вектором, поддерживает произвольный доступ к элементам 
и обеспечивает вставку и удаление из обоих концов очереди за 
постоянное время. Те же операции с элементами внутри очереди 
занимают время, пропорциональное количеству перемещаемых 
элементов. Распределение памяти выполняется автоматически. 
Доступ к элементам очереди осуществляется за постоянное время, 
хотя оно и несколько больше, чем для вектора. 
Примеры конструкторов (см. примеры для вектора): 
deque d2 (10, 1); 
deque d4 (v1); 
deque d3 (v1.begin(), v1.begin() + 2); 
deque m1(10); 
deque m2 (5, Monstr(“Bacя в очереди”)); 
10. 
В шаблоне deque определены операция присваивания, функция 
копирования, итераторы, операции сравнения, операции и функции 
доступа к элементам и изменения объектов, аналогичные 
соответствующим операциям и функциям вектора. 
Вставка и удаление так же, как и для вектора, выполняются за 
пропорциональное количеству элементов время. Если эти операции 
выполняются над внутренними элементами очереди, все значения 
итераторов и ссылок на элементы очереди становятся 
недействительными. Кроме перечисленных, определены функции 
добавления и выборки из начала очереди: 
void push_front(const Т& value); 
void pop_front(); 
При выборке элемент удаляется из очереди. Для очереди 
определены resize и size. К очередям можно применять алгоритмы 
стандартной библиотеки. 






11. 
Списки (list) 
Список не предоставляет произвольного доступа к своим элементам, 
зато вставка и удаление выполняются за постоянное время. Класс list 
реализован в STL в виде двусвязного списка, каждый узел которого 
содержит ссылки на последующий и предыдущий элементы. Поэтому 
операции инкремента и декремента для итераторов списка 
выполняются за постоянное время, а передвижение на n узлов 
требует времени, пропорционального n. 
После выполнения операций вставки и удаления значения всех 
итераторов и ссылок остаются действительными. 
Список поддерживает конструкторы, операцию присваивания, 
функцию копирования, операции сравнения и итераторы. 
Для занесения в начало и конец списка определены методы, 
аналогичные соответствующим методам очереди: 
void push_front(const T& value); 
void pop_front(); 
void push_back(const T& value); 
void pop_back(); 
12. 
В общем случае для поиска элемента в списке используется функция 
find. Для удаления элемента по его значению применяется функция 
remove: 
void remove(const Т& value); 
Если элементов со значением value в списке несколько, все они будут 
удалены. Для сортировки элементов списка используется метод sort: 
void sort(); 
template void sort(Compare comp); 
В первом случае список сортируется по возрастанию элементов (в 
соответствии с определением операции < для элементов), во втором
— в соответствии с функциональным объектом Compare. 
13. 
14. 
Стеки (stack) 
Как известно, в стеке допускаются только две операции, изменяющие 
его размер — добавление элемента в вершину стека и выборка из 
вершины. Стек можно реализовать на основе любого из рассмотренных контейнеров: вектора, двусторонней очереди или списка. 
Таким образом, стек является не новым типом контейнера, а 
вариантом имеющихся, поэтому он называется адаптером 
контейнера. Другие адаптеры (очереди и очереди с приоритетами) 
будут рассмотрены в следующих разделах. 
В STL стек определен по умолчанию на базе двусторонней очереди: 
template > 
При работе со стеком нельзя пользоваться итераторами и 
нельзя получить значение элемента из середины стека. Для 
стека, как и для всех рассмотренных выше контейнеров, определены операции сравнения. 
Пример использования стека (программа вводит из файла числа 
и выводит их на экран в обратном порядке): 
15. 
#include  
#include  
#include  
#include  
using namespace std; 
int main() ifstream in("input.txt"); 
stack > s; 
int x; 
while ( in >>x, !in.eof()) s.push(x); 
while (!s.empty()) x = s.top(); cout > 
> 
Содержимое файла input.txt: 
56 34 54 0 76 23 51 11 51 11 76 88 
Результат работы программы: 
88 76 11 51 11 51 23 76 0 54 34 56 

16. 
Очереди (queue) 
Для очереди допускаются две операции, изменяющие ее размер добавление элемента в конец и выборка из начала. Очередь является 
адаптером, который можно реализовать на основе двусторонней 
очереди или списка. 
В STL очередь определена по умолчанию на базе двусторонней 
очереди: 
template > 
Методы front и back используются для получения значений 
элементов, находящихся соответственно в начале и в конце 
очереди (при этом элементы остаются в очереди). 
Пример работы с очередью (программа вводит из файла числа в 
очередь и выполняет выборку из нее, пока очередь не опустеет): 






17. 
18. 
Ассоциативные контейнеры 
Как уже указывалось, ассоциативные контейнеры обеспечивают 
быстрый доступ к данным за счет того, что они, как правило, 
построены на основе сбалансированных деревьев поиска 
(стандартом регламентируется, только интерфейс контейнеров, а не 
их реализация). 
Словарь построен на основе пар значений, первое из которых 
представляет собой ключ для идентификации элемента, а второе — 
собственно элемент. Можно сказать, что ключ ассоциирован с 
элементом, откуда и произошло название этих контейнеров. 
Например, в англо-русском словаре ключом является английское 
слово, а элементом — русское. Обычный массив тоже можно 
рассматривать как словарь, ключом в котором служит номер 
элемента. В словарях, описанных в STL, в качестве ключа, может 
использоваться значение произвольного типа. Ассоциативные 
контейнеры описаны в заголовочных файлах и . 
19. 
Для хранения пары «ключ—элемент» используется шаблон pair, 
описанный в заголовочном файле : 
template struct pair typedef Tl first_type; 
typedef T2 second_type; 
Tl first; 
T2 second; 
pair(); 
pair (const T1& x, const T2& y); 
template pair(const pair &p); 
>; 
Шаблон pair имеет два параметра, представляющих собой типы 
элементов пары. Первый элемент имеет имя first, второй — second. 
Определено два конструктора: один должен получать два значения 
для инициализации элементов, второй (конструктор копирования) — 
ссылку на другую пару. Конструктора по умолчанию у пары нет, то 
есть при создании объекта ему требуется присвоить значение явным 
образом. 
20. 
Пример формирования пар: 
#include  
#include  
using namespace std; 
int main() pair p1(10, 12.3), p2(p1); 
p2=make_pair(20, 12.3); 
// Эквивалентно p2=pair (20,12.3> 
cout cout p2.first-=10; 
if (p1==p2) cout p1.second -=1; 
if (p2 > p1) cout p1\n"; 
> 
Результат работы программы: 
p1: 10 12.3 
p2: 20 12.3 
pl==p2 
p2 > p1 
21. 
Словари (map) 
В словаре (map), в отличие от словаря с дубликатами (multimap), все 
ключи должны быть уникальны. Элементы в словаре хранятся в 
отсортированном виде, поэтому для, ключей должно быть 
определено отношение «меньше». Шаблон словаря содержит три 
параметра: тип ключа, тип элемента и тип функционально объекта, 
определяющего отношение «меньше»: 
template > 
class map public: 
typedef pair value_type; 
explicit map(const Compared &comp=Compare()); 
template  
map(InputIter first, InputIter last, const Compare& comp=Compare ()); 
map(const map & x); 
> 
Как видно из приведенного описания (оно дано с сокращениями), 
тип элементов словаря value_type определяется как пара элементов 
типа Key и Т. 






22. 
Первый конструктор создает пустой словарь, используя указанный 
функциональный объект. Второй конструктор создает словарь и 
записывает в него элементы, определяемые диапазоном указанных 
итераторов. Время работы этого конструктора пропорционально 
количеству записываемых элементов, если они упорядочены, и 
квадрату количества элементов, если нет. Третий конструктор 
является конструктором копирования. 
Как и для всех контейнеров, для словаря определены деструктор, 
операция присваивания и операции отношения. 
Для доступа к элементам по ключу определена операция [ ]: 
Т& operator[](const Key & х); 
С помощью этой операции можно не только получать значения 
элементов, но и добавлять в словарь новые. В качестве примера 
словаря рассмотрим телефонную книгу, ключом в которой служит 
фамилия, а элементом — номер телефона: 
23. 
24. 
Словари с дубликатами Как уже упоминалось, словари с дубликатами (multimap) 
допускают хранение элементов с одинаковыми ключами. 
Поэтому для них не определена операция доступа по индексу 
[ ], а добавление с помощью функции insert выполняется 
успешно в любом случае. Функция возвращает итератор на 
вставленный элемент. 
Элементы с одинаковыми ключами хранятся в словаре в 
порядке их занесения. При удалении элемента по ключу 
функция erase возвращает количество удаленных элементов. 
Функция equal_range возвращает диапазон итераторов, 
определяющий все вхождения элемента с заданным ключом. 
Функция count может вернуть значение, большее 1. В 
остальном словари с дубликатами аналогичны обычным 
словарям. 
25. 
Множества (set) 
Множество — это ассоциативный контейнер, содержащий только 
значения ключей, то есть тип value_type соответствует типу Key. 
Значения ключей должны быть уникальны. Шаблон множества имеет 
два параметра: тип ключа и тип функционального объекта, 
определяющего отношение «меньше»: 
template > 
Из описания, приведенного с сокращениями, видно, что интерфейс 
аналогичен интерфейсу словаря. Ниже приведен простой пример, в 
котором создается множества целых чисел: 
#include  
#include  
using namespace std; 
typedef set > set_i; 
set_i::iterator i; 
int main() int a[4] = ; 
set_i si; 
// Создается пустое множество 
set_i s2(a, a+4); // Множество создается копированием массива 
26. 
#include  
#include  
using namespace std; 
typedef set > set_i; 
set_i::iterator i; 
int main() int a[4] = ; 
set_i si; 
// Множество создается 
//копированием массива: 
set_i s2(a, a+4); 
// Конструктор копирования : 
s3(s2); 
// Вставка элементов: 
s3.insert(10); 
s3.insert(6); 
cout for (i=s2.begin(); i!=s2.end(); i++) cout cout cout for (i=s3.begin(); i!=s3.end(); i++) 
cout cout if(s2.find(10)!=s2.end()) cout else cout cout return 0; 
> 
Результат работы программы: 
s2: 1 2 4 
S3: 1 2 4 6 10 
NO 
Как и для словаря, элементы в множестве хранятся отсортированными. Повторяющиеся элементы в множество не заносятся. 

27. 
Класс bitset 
Класс bitset предназначен для работы с отдельными 
битами. Т. е. экземпляр этого класса представляет из 
себя набор переменных булевского типа. Число же 
битов (булевских переменных) указывается при 
создании экземпляра класса bitset. 
С переменными типа bitset можно производить 
стандартные побитовые операции. Кроме того, можно 
получать значения отдельных битов в bitset, число 
установленных битов, изменять все биты на 
противоположные и др. 
Привет 
28. 
#include  
#include  
using namespace std; 
int main() bitset b0; 
b0[0] = 1; 
b0[1] = 0; 
b0[2] = 1; 
bitset b1(string("001")); 
cout // Побитовые операции. 
cout <<"*****\n";
bitset res = b0 & b1; // Побитовое "и". 
cout res = b0 | b1; // Побитовое "или". 
cout res = b0 ^ b1; // Исключающее "или". 
cout cout <<"*****\n";
// Число установленный битов 
cout // Общее число элементов. 
cout // Обращение битов на 
противоположные. 
b0.flip(); 
cout // Сдвиг битов влево. 
b1 = b1 cout // Обнуление всех битов. 
b1 = b1.reset(); 
cout system("pause"); 
return 0; 
> 

Что такое контейнерный класс
На этом шаге рассмотрим контейнерные классы.
Одна из самых распространенных задач в программировании заключается в организации обработки групп элементов. Реализация и отладка программ с использованием подобного рода структур отнимает у разработчиков много времени, т. к. они каждый раз вынуждены решать одни и те же задачи. Для решения этой проблемы библиотека контейнеров предоставляет набор часто используемых классов, на правильную работоспособность которых можно положиться. Это позволяет разработчику сконцентрироваться на реализации самого приложения и не вникать в детали реализации используемых контейнерных классов.
Qt предоставляет библиотеку контейнеров, именуемую Tulip, являющуюся составной частью ядра Qt, поэтому ее понимание очень важно для дальнейшего изучения. Данная библиотека не только очень похожа на STL (Standard Template Library, стандартная библиотека шаблонов), но и совместима с ней. В данном случае, разработчик может свободно выбирать, чем ему лучше воспользоваться — Tulip или STL. Предпочтительнее выбрать первую библиотеку, т. к. Tulip является частью Qt и активно используется в ней. Второй аргумент в пользу применения Tulip — это то, что эта библиотека в соответствии со спецификой классов Qt оптимизирована по производительности и расходу памяти. Использование в программах шаблонных классов, на основе которых построены контейнеры, заметно увеличивает размер исполняемых программ. Это связано с тем, что в каждом объектном файле реализации класса, использующего контейнеры, находится созданный компилятором код контейнеров с нужными типами, и этот код может повторяться. Библиотека Tulip создавалась именно с учетом этих обстоятельств и, кроме того, оптимизирована для заметного уменьшения размера объектного кода.
Реализация классов Tulip расположена в модуле QtCore. В основе библиотеки Tulip (как и в STL) лежат три понятия:

контейнерные классы (контейнеры);
алгоритмы;
итераторы.

Контейнерные классы — это классы, которые в состоянии хранить в себе элементы различных типов данных. Почти все контейнерные классы в Qt реализованы как шаблонные и, таким образом, они могут хранить данные любого типа. Основная идея шаблона состоит в создании родового класса, который определяется при создании объекта этого класса. Классы контейнеров могут включать целые серии других объектов, которые, в свою очередь, тоже могут являться контейнерами.
Очень важно правильно понимать отличия разновидностей контейнеров, для того чтобы правильно подобрать контейнер для конкретного случая. От этого в значительной степени зависит скорость работы кода и эффективность использования памяти. Qt предоставляет две категории разновидностей классов контейнеров: последовательные (sequence containers) и ассоциативные (associative containters).
Последовательные контейнеры — это упорядоченные коллекции, где каждый элемент занимает определенную позицию. Позиция зависит от места его вставки. К последовательным контейнерам относятся: вектор (vector), список (list), стек (stack) и очередь (queue). Соответственно, Qt содержит пять классов этой категории:

QVector — вектор;
QList — список;
QLinkedList — двусвязный список;
QStack — стек;
QQueue — очередь.

Ассоциативные контейнеры — это коллекции, в которых позиция элемента зависит от его значения, т. е. после занесения элементов в коллекцию порядок их следования будет задаваться их значением. К ассоциативным контейнерам относятся: множество (set), словарь (map) и хэш (hash). Классы этой категории:

QSet — множество;
QMap — словарь;
QMultiMap — мультисловарь;
QHash — хэш;
QMultiHash — мультихэш.

Во всех контейнерах этих двух групп доступны операции, перечисленные в табл. 1.
 
Таблица 1. Операторы и методы, определенные во всех контейнерных классах 
 
Оператор, метод
 
Описание
 
 
 
== и !=
 
Операторы сравнения, равно и не равно
 
 
 
=
 
Оператор присваивания
 
 
 
[ ]
 
Оператор индексации. Исключение составляют только классы QSet и QLinkedList , в нем этот оператор не определен
 
 
 
begin() и constBegin()
 
Методы, возвращающие итераторы, установленные на начало последовательности элементов контейнера. Для класса QSet возвращаются только константные итераторы
 
 
 
end() и constEnd()
 
Методы, возвращающие константные итераторы, установленные на конец последовательности элементов контейнера
 
 
 
clear()
 
Удаление всех элементов контейнера
 
 
 
insert()
 
Операция вставки элементов в контейнер
 
 
 
remove()
 
Операция удаления элементов из контейнера
 
 
 
size() и count()
 
Оба метода идентичны — возвращают количество элементов контейнера, но применение первого предпочтительно, т. к. соответствует STL
 
 
 
value()
 
Возвращает значение элемента контейнера. В QSet этот метод не определен
 
 
 
empty() и isEmpty()
 
Возвращают true, если контейнер не содержит ни одного элемента. Оба метода идентичны, но применение первого предпочтительно, т. к. соответствует STL
 
 
 

ПРИМЕЧАНИЕ . Важно не забывать о том, что классы, унаследованные от класса QObject, не имеют доступного конструктора копирования и оператора присваивания, т. к. они находятся в секции private. Следовательно, их объекты не могут храниться в контейнерах, поэтому нужно сохранять в контейнерах не сами объекты, наследуемые от класса QObject, а указатели на них. 
Если вам нужно проверить, содержит ли контейнер элементы или нет, то не применяйте для этого метод size(), а используйте метод empty(). Причина проста: метод empty() для всех контейнеров выполняется с постоянной сложностью, а size() может потребовать для контейнера списка линейных затрат, что может существенно снизить скорость вашего алгоритма.
На следующем шаге рассмотрим итераторы.


Похожие публикации:

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