Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 117
Текст из файла (страница 117)
Она просто изменяет структуры данных списка, относящиеся к элементу. Кроме удаления-вставки отдельных элементов и диапазонов, прн помощи функции яр11се () мы можем удалить-вставить все элементы списка: Глава 17. Стандартные контейнеры 530 )ги1!.яр!!се (!ги!! Ьеу1л (), спгиз), Это приведет к следующему результату: /па!. угаре3гш! 1етоп арр1е огапуе реаг сигиз <езлр!у> (пусто) Во всех версиях функция зр((се () получает в качестве второго аргумента список, из которого берутся элементы. Это позволяет удалять элементы из их первоначального списка.
Просто итератор не позволил бы этого, поскольку не существует универсального способа определить контейнер, содержащий элемент, по одному лишь итератору на этот элемент Я 18.6). Естественно, аргумент-итератор должен быть допустимым итератором для списка, на элементы которого оп (предположительно) указывает. То есть он должен указывать на элемент того списка или быть его концом (еЫ ()) . В противном случае результат не определен и может привести к неприятностям.
Например: 1!я!<я!с!лу>1!ега!оср =Япг1 1Х(ри1!Ьеу!и () /ги1!елз1 (), !а!1!а! Гр )); /ги11.зр!1се (р, с16 ия, с1!гиз Ьеу1л ()); // правильно /) и1!.яр!!се (р, с1!гиз,ага!! Ьеу1п ()); //ошибка:/ги11.6еу1пО не указывает О внутрь списка сисис с17гиз зр!гее (рХги11,/ги!1Ьеугп ()); //вшие>ко; р не указиваегл // внутрь списка слгиз С первой функцией зрйсе () все правильно, даже если список с1!гиз пуст.
Функция тегде () (слияние) объединяет два сортированных списка, удаляя элементы из одного списка и вставляя в другой с сохранением порядка. Например: арр1е да!псе реаг ,12. 1етоп угаре~гш! огапуе !!те можно отсортировать и объединить таким образом: /7.зо ге (); /2.зог! (); ~1.тегуе (/2); В результате получится: 71: арр1е угарезги1! 1етоп 11те огапуе реаг ушлое /2. <етр1у> (пусто) Если один из объединяемых списков не отсортирован, щегле () все же выдаст список, содержащий объединение элементов этих двух списков.
Однако относительно порядка в получившемся списке нет никаких гарантий. Как и ярйсе (), щегле() воздерживается от копирования элементов. Вместо этого она удаляв~ элементы из списка-источника и вставляет их в целевой список. После х,!легре (у) список у окажется пустым. 17.2. Последовательности 17.2.2.2. Операции с начальными элементами Операции с первыми элементами списков созданы в дополнение к операциям, кото- рые имеют дело с последними элементами, обеспечиваемым всеми последовательно- стями Я 16.3.5): Еетр!а ге<с!акк Т, с!акк А = айосагогнТ» с!акк !!кЕ ( риЬ!Ес //- // доступ к элементам: ге/егеасе/гоп! )), // ссылка на первый элемент сопке ге~егепсеЯопЕ () сопя!1 // добавление нового первого элемента //удаление первого элемента ооЕеЕ рик/е Тгопг )сопя! Те ) оогд рар !гоп! )); 0-.
17.2.2.3. Другие операции Вставка и удаление элементов особенно эффективны для списков. Когда такие опе- рации встречаются часто, это, конечно, стимулирует людей предпочитать списки. Что, в свою очередь, делает осмысленным поддержку обычных способов удаления элементов напрямую: гетр)аге<г!акв Т, с!акк А = аНосагогяТ» с!авк ЙвЕ 1 риЬ!Еа со!с! гетоое )сонэ! Тй оаЕ); !етр!а!его)акк РгееЕ> оо!еЕ гетоие ь|)РгееЕР); оокуипгг/ие )); //удаляет дуоликаты при полющи == Еегпр!агейла)акк ВЕпргееЕ> оо)сЕ ипи!ие )В!пРгед Ь); // удаля егп дубликаты // при нолти)и Ь оо!еЕгеоегкг(); //ойрапгный порядок элементов Например, получив /гиге арр!е агапке дгаре~гиЕЕ !етоп огапуе Нте реаг дигпсе Первый элемент контейнера называютугопЕ.
Для списков операции с началом так же эффекгивны и удобны, как и операции с концом Я 163.6). Когда есть выбор, лучше предпочесть операции с конечными элементами, а не с начальными. Программы, написанные с использованием последних элементов, применимы как для списков, так и для векторов. Поэтому если существует возможность, что программа, использующая списки, когда-нибудь разовьется в обобщенный алгоритм, применимый к множеству контейнеров, лучше всего выбирать более широко распространенные операции с концами. Зто частный случай того правила, что, решая задачу, для достижения максимальной гибкости разумно использовать минимальный набор операций. Глава 17.
Стандартные контейнеры мы можем удалить все элементы со значением 'огалпе" таким образом: уги!!.гетоое ( огляде ); В результате получим; уги!1: арр1е угареГга!! 1етоп 1!те реаг уишсе Часто интереснее удалить все элементы, отвечающие какому-либо критерию, а не просто все элементы с данным значением. Это выполняет операция гетоое (7 (). Например: уги!!.гетоое у" (!л!!!а! ('1)); удалит изЯ ш1все элементы на букву 1', оставив: угара арр1е угареуги!! реаг уатсе Обычная причина удаления элементов — устранение дубликатов.
Это обеспечивает операция ил1аие (). Например, если бы 1' и!!содержал такой список: арр1е реаг арр!е арр!е релг простоеЯи!!.ил!дие () привело бы к результату: арр1е реаг арр!е реаг в то время как предварительная сортировка (а потом вызов ил!уие ()) даст: арр1е реаг Если нужно удалить только определенные дубликаты, мы можем ввести предикат !логическое условие), чтобы указать, какие именно дубликаты мы хотим удалить. Например, мы мо~ли бы определить бинарный предикат 8 18А.2) !л!!!а12 (х), чтобы выявлять строки, начинающиеся на букву к, и возвращающий уа1ве для каждой строки, начинающейся на какую-либо другую букву.
В списке реаг реаг арр1е арр1е мы можем удалить последовательные дубликаты каждого фрукта на оукву 'р' следу- ющим вызовом: уги1!.ил!уие (!и!!!а!2 ( р')); Это даст нам: реаг арр!е арр1е Как отмечено в у 16.3.2, иногда мы хотим просмотреть контейнер в обратном порядке. Для списков можно изменить порядок элементов так, чтобы первый стал после71ним и т. д. без копирования элементов. Это обеспечивается операцией геиегае (). Из списка уги!1: 'лапала слеп у 1!те л!гаыоеггу вызов уги!!.геоегае () сделает: 533 17.3. Адаптеры последовательностей вггатЬеггу йте сдеггу Ьапапа Удаляемый из списка элемент уничтожается.
Однако заметим, что уничтожение указателя не влечет за собой удаления (с(е!е1е) элемента, на который он указывает. Если вам нужен контейнер указателейг, который при удалении нз него указателя (или уничтожения всего контейнера) уничтожает элемент, на который указывает этот указатель, вы должны написать его самостоятельно Я 17.8[13!). 17.2.3. Очереди с двумя концами Контейнер с(едие (читается «дек») — это очередь с двумя концами. То есть это последовательность, оптимизированная таким образом, что операции' с обоими концами почти так же эффективны, как в списке, в то время как обращение по индексу приближается по своей эффективности к вектору: 1ет р!а1е<с!аве Т, с!авв А = а!!оса 1ог<Т» с1авв вЫ>г!едие ( //гпипи и операции, такие же как в вес!ог Ц !б 3 3, э !б 3 5, х !б 3 б), // крове сарасду() и гевегое() плюс операции с пачололпг (б ! 7222) как в ЙИ Вставка и удаление элементов «в середине» здесь так же (не)эффективны, как в векторе, то есть вставка «в середине» ведет себя не так, как в списке.
Следовательно, контейнер с(едие используют там, где добавление и удаление элементов производится «с краев». Например, мы могли бы воспользоваться очередями с двумя концами для моде.пирования участка железной дороги или колоды игральных карт: с!едие<саг еЫту по 3; дедов<Сакс!> Ьопив; 17.3. Адаптеры последовательностей Контейнеры вес1ог, 11в1 и с!едие не построить один из другого без потери эффективности. С другой стороны, при помощи этих трех базовых последовательностей можно изящно и эффективно реализовать стеки (е(асЬ) и очереди (диеие).
Поэтому классы в1ас)с и диеие определены це как отдельные контейнеры, а как адаптеры базовых контейнеров. Адаптер контейнера предоставляет ограниченный интерфейс к контейнеру. В частности, адаптеры не предоставляют итераторов; предполагается, что они (адаптеры) будут использоваться только через их специализированные интерфейсы. Методы по созданию из контейнеров контейнерных адаптеров часто полезны Лля неинтрузивного приспособления интерфейса класса к потребностям пользователя.
1?.3.1. Стек Адаптер ебасй определен в заголовочном файле <в1ас!с>. Он так прост, что лучший способ описать его — это представить реализацию: гетр!аге<с!авв Т, с!авв С = с!едие<Г > с!авв вЫсв1асЬ ( рго1ес1еаг Сс; риб!!с: 1урег)е)" 1урепате С:та!ие 1уре оа!ие 1уре; 534 Глава 17. Стандартные контейнеры 1уреде/гурепате Сгяхе гуре ясее 1уре, 1урег)е/С сон гашег 1уре; ехр!гсй Иасй (соля1 Са а = С ()): с (а) ( ) Ьоо! етр1 у () сопя1 ( ге1игп с.етр1у (); ) яме Еуреахе() сопИ(гелггл с.я!хе 0;) иа!ие 1уре8 1ор (г ( ге!игл с.Ьасй (), ) сопИиа!ие гуре! 1ор() соля1(ге!игл сЬасй();) иоЫрияй (сопя!ил!ие 1урейх) (срияй Ьасй (х),) иоЫ рор () ( с.рор Ьасй ();) То есть я1асй — зто просто интерфейс для контейнера, тип которого передается как аргумент шаблона.
Все, что я1асй делает — это удаляег из интерфейса нестековые операции для своего контейнера и дает операцггяы Ьасй (), ризй Ьасй () и рор Ьасй () общепринятые имена — соответственно 1ор (), рияй () и рор (). По умолчанию стек хранит своп элементы в очереди с двумя концами, но можно использовать любую другуго последовательность, обеспечивающую операции Ьасй (), ризй Ьасй () ирор Ьасй(). Например: Иасйссйаг> И, // использует дедие<сааг> для хранения // элементов типо савг ятасй<!л1, иес1ог-!п!» я2; // ислольэуегп иес1окггг!> для хранети // элелгентов тигга !п1 с1тобы инициализировать стек, можно предоставить существующий контейнер. На- ггрглмер: иоЫ рпл1 Ьисйгиагд (иес1огс!пт>ь и) ( // инидиалиэнруелг сослгоянгге иэ и ягпсйс !лг, иес!ог !пс»я1а1е(и); шМ!е (з1аге.яме ()) ( сои1«я1а1е.гор Ц; я1а1е.рор (); ) ) Однако элементы аргумента-контейнера копируются, поэтому указание существующего контейнера в качестве аргумента может оказаться дорогостоящим.