Б. Страуструп - Язык программирования С++. Специальное издание, 3-изд. Бином. 2004 (1160791), страница 118
Текст из файла (страница 118)
Элементы добавляются в стек, при помощи рияй Ьасй() контейнера, используемого для хранения элементов. Следовательно стек не может переполниться, пока в машине есть достаточно памяти для удовлетворения требований этого контейнера (с использованием его распределителя памяти; см.
9 19А). С другой стороны, стек может переполниться снизу: во !с!Д я1асй<т1, иес1ог<!лг» я; я.рия!г (2), !э (я.етр1у ()) ( //можно заи!ититься от переполнения снизу // не снимать со гтека !рор) 535 17.3 Адаптеры последовательностей е1ке ( // но оно вполне возможно я рор (); // прекрасно: я.яхеО становится равным 0 жрор (); //яффект не определен, воклюжны неприктноспчи ) ) Отметим, что для использования элемента не нужно применять рор () (снимать элемент с вершины стека). Вместо этого обращаются к 1ор () (получить элемент с вершины стека).
рор () применяют, когда элемент болыпе не нужен. Это не вызывает слишком больших затруднений и более эффективно, когда удаление элемента с вершины стека не нужно: иоиЩкгасу<сдаг>й я) ( ч/ [я.1ор () ==-'с1 я.рор (); //... ) // удаляем воялчожные начальные 'с' 17.3.2. Очереди Определенный в заголовочном файле <с!иеие> контейнер ч)иеие — это интерфейс для контейнера, позволяющего вставлять элементы в конец (Ьасй ()) и извлекать элемен- ты из начала ()гоп1 ()): 1етр!а1е<с!аяз Т, с!акя С = Иедие<Т» с!акк ягч!гуиеие ( рго1есгеч!.
Сс; риЬИс. 1уреде/1урепате С:жа!ие 1уреиа!ие 1уре; 1уреч!е/~урепате Сзягае !урез!ее 1уре; 1уреч)е~С соп1а!пег 1уре; ехр! !сй уиеие (сопк1 Сй а = С ()): с (а) ( ) Ьоо! етр1у () сон я1 ( ге! игл с.етр!у (); ) я!ее !уре зеве () сопя1 ( ге1игп слезе (); ) иа!ие 1урей /гоп! () ( ге!ига с,!сочи! (); ) сопя! па! ие 1урей/гоп! () сопя! ( ге1игп саган! (); ) оа!ие !урей Ьасу () ( ге1игп с.Ьасу (); ) сопз! оа1ие 1урей Ьасу () сопя! ( гегичп с Ьасу (); ) иоийрикЬ (сопя! иа1ие урейх) ( с ризЬ Ьасу (х); ) иойурор () (с.рор /гоп! (); ) По умолчанию очередь ч7иеие для хранения своих элементов использует ч!еч!ие, но для этой цели может применяться и любая другая последовательность, предоставляющая операции/гоп!(), Ьасй (), рияй Ьасй ()и рор ~гоп1 (). Поскольку вектор не предо- В отличие от полностью разработанных контейнеров, ятасй (как и другие контейнер- ные адаптеры) не имеет среди параметров шаблона распределителя памяти.
Вместо этого я1асй и его пользователи обращаются к распределителю памяти того контейне- ра, который используется при реализации к1асй. Глава 17. Стандартные контейнеры 536 ставляет операцию рор ~гоп! (), он не может использоваться в качестве базового контейнера для очередей. Очереди, кажется, встречаются во всех системах. Для простой системы, основанной на передаче сообщений, можно определить сервер !программу, обрабатывающую сообщения) например так: зтгис1Мезлауе ( // сообщение ооЫ зегвег (диеие Меззауе>й д) ( тИ!е ('д етргу Н) ( Меззауей т = д/гоп! (); т.зего!се Н; дрор Н' // получили сообщение //вызвалифункцию оослулкнванна запроса // униюпогкили сооощенне Сообщения помещаются в очередь при помощи ризй ().
Если запрашивающая программа и сервер выполняются в разных процессах или потоках, для доступа к очереди необходима какая-то синхронизация. Например: ооЫзегвег2 (диеие<Меззауе>й д, Тосяй !с!е) ( в!л!!е Нд.етр!у Н) ( Меззауе т; ( йоспР1г !л (!сяГ //блокнруем пголько на зрелы //извлечениясообщения ГЭ" !в.4.Ц // сообщение получил кто-то другой !/(детр1у Н)ге!игп, т =д/гоп1Н; дрор Н; ) т веги!се Н, //взлезали функцию обслуясивония запроса В С++ да и вообще в мире нет стандартного определения параллельности или блокировки. Посмотрите, что может предложить ваша система, и как это реализовать на С++ Я 17.8(8)), 17.3.3.
Очереди с приоритетом 1етр!аге лс1азз Т, с!азз С = оес1ог<Т, с!азз Стр = !езз<1урепате Ссоа!ие 1уре» с!азз зЫсрпогту диеие ( рго1ес1ел(: Сс; Стрстр; Очередь с приоритетом Грг!ор!1у диене) — это такая очередь, где каждому элементу назначен приоритет, определяющий порядок, в котором элементы достигают выхода из очереди (1ор ()): 537 17.3.
Адаптеры последовательностей риЫЕс ЕуресЕе/!урепате Ссоо!ие гуре оаЕие 1уре; гуре!Ее~!урсов!не Сея!ее !уре иле Еуре; ЕурееЕе/С соп1аепег Еуре; екр!!с!1 рпоп1у диеие (сопя1 Стрй а! = Стр (), сопя1Сй а2 = С ()) с(а2), стр(а!) (таус Ьеар(с Ьеут (), сепг!(), стр);) // сп. э ЕЬЯ Еетр!а1екс!аяя !п> рпогиу див ие (ЕпЯгя1, 7п !ая1, сопяЕ Стрй = Стр (), сопя! Сй = С ()); Ьоо! етр1у () сопя! ( ге!ига с етрЕу (); ) я!ее гуре я сев () сопя! ( ге1игп с я!ее (); ) сон я1 оа(ие 1урей 1ор () сон я1( ге1игп с/гап1 (); ) ооЫ ризЬ (сопя!оп!ие 1урей); ооЫрор (), )' Объявление рг!ог!Еу диеие находится в заголовочном файле <диене>.
По умолчанию рг!ог!!у па!ие просто сравнивает элементы при помощи оператора <, и !ор () возврапЕает наибольший элемент: я! ис1Меяяауе( сп1 рг!ог!Еу; Ьоо1 орега1огс (сопИМеяяауей х) сопя1 ( ге1игп рггог!Еу < хрг!ог!!у; ) //-. ооЫ яегоег Ерг!ог!1у диеиелМеязауе>й д, Еосуй !сЬ) тЫ!е (!д етр1у ()) ( Меяяауе т; ( 4.осЕЕРЕг Ь (!су); //Еиокируе я только на зрелы // извлечения сообщения !э" ! 4.4. !) !/ (д етр1у ()) ге!игп; // сооощение полу нм кгпв-то другой т = д.!ор (); д.рор (); ) т яегс!се (); // визвалн функцию ооглуясива низ запроси Этот пример отличается от примера с очередью Я 17.3.2) тем, что сообщения с более высоким приоритетом будут обслуживаться первыми.
Порядок, в котором элементы с равными приоритетами достигнут выхода из очереди, не определен. Считается, что два элемента имеют равный приоритет, если ни у одного из них приоритет не выше, чем у другого Я 17.4.1.5). Альтернативу оператору < для сравнения элементов можно указать в аргументе шаблона. Например, мы могли бы отсортировать строки без учета регистра, поместив их в ргЕогиу диеиекяеггпу, вес!огсз(ппу>, Аеосаяе> рд; //используем !4осаяе для //сравнения Еэ" 154.!) при помощи рдрияЕе (), а затем получив обратно при помощи рд Еор () и рд рор ().
Глава 17. Стандартные контейнеры 538 //ошибка: типы не совпадают рпоп!у диене<в!пну>8 рд! = рд; Мы можем создать критерий сравнения, не затрагивая типа рг!ор!1у диене, задав объект сравнения подходящего типа в качестве аргумента конструктора.
Например: // тип, используемый длл выра женил кршперия //'сравнение во время выполнения //использовать критерий сравнения п з1гис! огг1пя сгпр ( В!г!пу стр (сп1 и = О); 0 ... !уреде/рпоп1у диене<в!с!пу, иессог<зтг!пу', 81гту стр > Рдиеие; ооЫу(Рдиеией рд) //рд использует 5!г!пу стр() для сравнений Рдиеие рд2 (8!пну стр (писаке)) рд = рд2' // правильно: рд и рд2 одного и того же типа //рд теперь гпакже использует Я1г!пу стр(посазе) Поддержание порядка элементов не бесплатно, но и не так уж дорого.
Один полезный способ реализации рпог!1у диеие заключается в использовании дерева, чтобы отслеживать относительное положение элементов. Это приводит к тому, что обе операции ризй () и рор () обходятся как О (!оу (и)). По умолчанию очередь с приоритетом использует для хранения своих элементов вектор, но в этом качестве может использоваться и любая другая последовательность, предоставляющая операции/гоп!(), ризй Ьасн (), рор Ьасй () и нтераторы с произвольным доступом. Очередь с приоритетом скорее всего реализуется при помощи кучи (пеар) Я 18.8). 17.4. Ассоциативные контейнеры Ассоциативный массив — это один из самых полезных и универсальных типов, определяемых пользователем. Фактически, в языках, занимающихся главным образом обработкой текстов и символов, это зачастую встроенный тип.
Ассоциативный массив, часто называемый отображением (щар), а иногда словарем ( Йсс(опагу), содержит пары значений. Зная одно значение, называемое кл!оном (йеу), мы можем получить доступ к другому, называемому отоброзкенным значением (щарред ча1пе). Ассоциативный массив можно представить как массив, для которого индекс не обязательно должен иметь целочисленный тип: 1етр!а!е<с!азз К, с!азз Ъ > с!азз Алсос ( раб!!а )г!> орега1ог() (сопз1Кй) // возвращает ссылку на У, соответгтвуюи1ий К Таким образом, ключ типа К «именует.
отображенное значение )г. Ассоциативные контейнеры — это обобщение поня~на ассоциативного массива. тар — это традиционный ассоциативный массив, где по значению ключа можно Объекты, определенные шаблонами с разными аргументами, относятся к разным типам (8 13.6З.1). Например: 539 17 4. Ассоциативные контейнеры однозначно найти значение. Контейнер ти!1!!пар — это ассоциативный массив, позволяющий дублировать элементы для данного ключа, а яе1 (множество) и ти(1!яе1 можно рассматривать как вырожденные ассоциативные массивы, в которых ключу не соответствует никакого значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
