Контейнеры STL. Часть 2

Контейнеры STL. Часть 2
Оцени эту статью




контейнеры STL C++ , Standard Template Library, контейнер с++, vector

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

  1. Контейнер — хранение набора объектов в памяти.

  2. Итератор — средство доступа к содержимому отдельных объектов в контейнере.

  3. Алгоритм — определение наиболее стандартных вычислительных процедур на контейнерах.

  4. Адаптер — адаптация основны категорий для обеспечения наиболее употребляемых интерфейсов (таких как стек или очередь).

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

Библиотека STL — это весьма обширная область. Её описанию посвящены целые отдельные книги (одна из лучших книг на русском языке, достаточная для освоения STL в деталях, показана в конце текста). Мы же, в силу начального уровня знакомства, рассмотрим технику STL на интуитивно ясных примерах.

Синтаксис STL основан на использовании таких синтаксических конструкций языка C++ как шаблоны (templates) классов и шаблоны функций. Но для успешного применения техники STL совсем не обязательно глубокое понимание техники templates.

Центральным понятием STL, вокруг которого крутится всё остальное, это контейнер (ещё используют термин коллекция). Контейнер — это набор некоторого количества однотипных элементов, упакованных в контейнер определённым образом. Простейшим прототипом контейнера в классическом языке C++ является массив. Тот способ, которым элементы упаковываются в контейнер, определяет тип контейнера и особенности работы с элементами в таком контейнере. STL вводит целый ряд разнообразных типов контейнеров:

  • последовательные контейнеры — вектор (vector), двусвязный список (list), дэк (deque);

  • ассоциативные контейнеры — множества (set и multiset ), хэш-таблицы (map и multimap);

  • псевдо-контейнеры — битовые маски (bitset), строки (string и wstring), массивы (valarray);

Мы последовательно рассмотрим на примерах использование основных контейнеров, переходя от более простых к сложным. Простейшим типом из них является вектор. Близким прототипом вектора является массив С++. Но размер вектора в любое время может динамически изменяться операциями добавления (метод push_back()) или удаления элемента. Так же, как и для массива, мы можем обратиться к произвольному элементу вектора операцией индексации [n]. Это уже и есть первый, поверхностный слой познаний о vector, который позволяет нам начать с ним работать:

Описание vector<float> (это и есть упоминавшийся ранее template в описании класса) объявляет в коде объект array: вектор элементов типа float.

Далее мы видим такие методы класса vector<float>, как max_size() — максимально возможная длина векторов вообще (константа реализации); size() — текущий размер (число элементов) вектора; capacity() — текущая ёмкость вектора (максимальное число элементов, которое может быть помещено в вектор в текущем его размещении). Выполнение этого фрагмента даст что-то примерно следующее (детали могут различаться в зависимости от реализации):

контейнеры STL C++ , Standard Template Library, контейнер с++, vector

Здесь видно достаточно интересное поведение вектора (в этом и его смысл): как только при добавлении очередного элемента, ёмкости вектора становится недостаточно, делается новое размещение вектора, резервируя для него удвоенную ёмкость (с запасом, чтобы следующее же добавление нового элемента не потребовало сразу же нового переразмещения).

Таким образом мы получили эквивалент массива C++, размер которого (size()) меняется в произвольных пределах от нескольких единиц до миллионов элементов. Обратим внимание (это очень важно), что увеличение размера вектора достигается не индексацией за пределы его текущего размера, а «заталкиванием» (метод push_back()) нового элемента в конец вектора. Другой способ изменить размер вектора — это вызвать методы resize(). Именно поэтому, для вектора предусмотрено 2 разных способа индексации: операция [n] и метод-функция at(n). Метод at() проверяет текущий размер вектора size(), и при индексации за его границу срабатывает исключение (это ошибка!). Напротив, операция индексации не проверяет границу, что небезопасно, но зато это быстрее.

контейнеры STL C++ , Standard Template Library, контейнер с++[1] Мейерс Скотт, Эффективное использование STL, «Питер» СПб. 2002, ISBN: 5-94723-382-7, 244 стр. По ссылке можно читать книгу online.

Рассылка новых уроков по программированию:

Olej

Об авторе Olej

Стаж практических программных разработок около 40 лет. Преподаватель международной софтверной компании Global Logic. Постоянный автор публикаций IBM Developer Works. Научный редактор книжного издательства компьютерной литературы "Символ-Плюс", Санкт-Петербург.

Добавить комментарий

Код размещайте в тегах: <pre class="lang:c++ decode:true ">YOUR CODE</pre>