Все операции с контейнером можно разделить на несколько групп:
• операции доступа к элементам, включая операцию замены значений элементов;
• операции добавления и удаления отдельных элементов или групп элементов;
• операции поиска элементов и групп элементов;
• операции с контейнером как объектом; в частности, важными являются операции объединения контейнеров;
• прочие (специальные) операции, зависящие от вида контейнера.
Операции доступа мы уже рассмотрели. Операции добавления и удаления элементов работают только для контейнера переменного размера. Очевидно, что эти операции с элементами можно выполнять самыми разными способами:
• добавлять и удалять элементы в начале контейнера;
• то же самое делать в «хвосте» контейнера;
• вставлять элементы перед текущим элементом или после него, удалять текущий элемент;
• делать вставки в соответствии с некоторым порядком сортировки элементов контейнера, в этом случае обязательно выполняется операция поиска;
• удалять элемент, содержимое которого равно заданному, в этом случае «за кадром» тоже работает операция поиска.
Первые три операции обычно применяются к последовательным контейнерам. Способ вставки и удаления определяет вид последовательного контейнера. Если вставка и удаление выполняются только на одном конце контейнера, то такой контейнер называется стеком, а работает он в соответствии с дисциплиной обслуживания LifO (Last In First Out — последним вошел, первым вышел). Говорят, что текущий элемент находится на вершине стека. Если же элементы добавляются на одном конце, а удаляются из другого, контейнер называется очередью. Очередь работает в соответствии с дисциплиной обслуживания FifO (First In First Out — первым пришел, первым ушел). Можно выполнять и вставку, и удаление на обоих концах контейнера — такой контейнер называется деком (от английского термина deque1, который является аббревиатурой от «double ended queue», то есть «очередь с двумя концами»). Таким образом, дек представляет собой обобщение очереди и стека.
Если же контейнер ассоциативный, то он упорядочен по полю доступа, поэтому операции вставки и удаления всегда выполняются в последних вариантах. Но и последовательный контейнер может быть отсортирован, поэтому операция вставки тоже может вставлять «по порядку». Примером отсортированного последовательного контейнера является приоритетная очередь priori ty_queue — один из последовательных контейнеров стандартной библиотеки.
Все операции, которые мы рассматривали до сих пор, — это операции с отдельными элементами контейнера. Но и с самим контейнером или его частью можно выполнять некоторые операции — вспомните класс TString (см. листинг 4.2). Обычно строки можно инициализировать другими строками и присваивать. Строки можно объединять разными способами, можно выполнять много разных операций с подстроками. Аналогично — и с контейнерами. Наиболее часто используется операция объединения двух контейнеров с получением нового контейнера, которая может быть реализована в различных вариантах:
• простое сцепление двух контейнеров, в новый контейнер попадают все элементы и первого, и второго контейнеров; операция не коммутативна;
Этот термин, ставший ныне общепринятым, впервые использовал Дональд Кнут.
• объединение упорядоченных контейнеров, называемое слиянием, в новый контейнер попадают все элементы первого и второго контейнеров; объединенный контейнер упорядочен; операция коммутативна;
• объединение двух контейнеров как объединение множеств, в новый контейнер попадают только те элементы, которые есть хотя бы в одном контейнере; операция коммутативна;
• объединение двух контейнеров как пересечение множеств, в новый контейнер попадают только те элементы, которые есть в обоих контейнерах; операция коммутативна.
Одной из операций с контейнером является извлечение из него части элементов и создание из них нового контейнера. Часто эту операцию выполняет конструктор, а требуемая часть контейнера задается двумя итераторами.
Отдельно необходимо сказать о контейнерах-множествах. Множество — это контейнер, в котором каждый элемент единственный. Помимо операций объединения и пересечения, для контейнеров-множеств реализуется операция вычитания множеств: в контейнер-результат попадают только те элементы первого контейнера, которых нет во втором; операция не коммутативна. Очень часто с множествами выполняется операция проверки включения, которая фактически является операцией поиска (как отдельного элемента, так и подмножества элементов).
Тип элементов оказывает существенное влияние на то, какие операции могут выполняться с контейнером. Например, для строк операция сортировки обычно не нужна, а для числовых контейнеров или для списка счетов в банке такая операция может быть не только полезной, но и необходимой. Для числовых контейнеров, очевидно, часто необходимы операции поиска минимума и максимума, суммы и произведения элементов контейнера — как в нашем «умном» массиве (см. листинг 5.2).
Опубликовал Kest
November 05 2013 14:43:10 ·
0 Комментариев ·
5675 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
