Бьерн Страуструп. Язык программирования С++. Специальное издание (2011) (1004033), страница 116
Текст из файла (страница 116)
Другие записи в этой таблицы означают степень эффективности операций. Запись салаг означает, что операция занимает время, не зависящее от числа элементов контейнера. По-другому, это же можно записать в виде 0(1). Запись 0(л) означает, что операция занимает время, пропорциональное числу участвующих в операции элементов. Суффикс» означает, что в ряде случаев операция может потребовать дополнительных затрат времени. Например, вставка элемента в список имеет фиксированную цену (поэтому она помечена как соивг), в то время как для векторов она приводит к перемещению всех элементов, начиная с места вставки (что соответствует 0(л) ).
Но иногда при этом приходится перемещать все элементы (поэтому я добавил»). Обозначение с большой буквой 0 абсолютно традиционное. Знак + я добавил для программистов, которым помимо средней оценки быстродействия важна еще и предсказуемость. Для 0(л)» принят термин итог)(сей 1(леагите (линейное время с амореизаиией).
Очевидно, что если солят очень велико, то это может и превысить оценку 0(л) . В то же время, если число элементов велико, то соим будет значить «дешево»э 0 (л) будет значить дорого, а О (1оя (л) ) — «более-менее дешево». Для умеренно больших л оценка О (1од (л) ) ближе к константе, чем к оценке О (л) . Для тех, кому цена операции очень важна, лучше присмотреться к этому повнимательнее, например поточнее понять, какие элементы формируют число л.
Наконец отметим, что никакие перечисленные в таблице базовые операции не являются «слищком дорогими», то есть среди них нет операций порядка 0(л*л) или хуже того. За исключением вл(ля, перечисленные стоимостные оценки соответствуют требованиям стандарта. Оценки для ви 1ля — это мои предположения. Оценки для агас1г и авеле соответствуют умолчательной реализации с применением Феяие (й17.3.1, $17.3.2). Приведенные оценки сложности и цены являются оценками сверху. Они позволяют пользователю прикинуть, что можно ожидать от разных реализаций, Для особо важных случаев некоторые реализации могут предоставить варианты получше. 17.1.3. Внутреннее представление Стандарт не определяет для контейнеров никаких внутренних представлений (гергевелгаг(ол, сокращенно — гер). Вместо этого, он специфицирует открытый интерфейс и некоторые требования к сложности. Чтобы удовлетворить стандарту, разработчики применяют подходящие и тщательно оптимизированные варианты.
Контейнер в общем случае представляется некоторой структурой данных, содержащей элементы, доступной через дескриптор, содержащий размер и емкость контейнера. Для контейнера гесгог, структура данных под элементы является непрерывной областью памяти, фактически массивом: е!етепв ех1га красе 561 17.1. Стандартные контейнеры Для списков структура данных в типичном представлении является набором связей, указывающих на элементы: е(еюепм: Д~~ Д~~ Д Ассоциативный контейнер гоар наиболее вероятно представим сбалансированным деревом узлов, указывающих на пары (ключ, значение) ()геу,ча1це): Г [; поде) (кеу, ча1пе) ра)гк '( ) Строки могут реализовываться так, как описано в Э11.12, или как последовательность массивов, каждый из которых содержит небольшой набор символов: згпне: '( тер затая зерпеп1з: ') ~ [ 17.1.4.
Требования к элементам контейнеров Элементы в контейнерах — это копии вставляемых объектов. Таким образом, чтобы объект мог стать элементом контейнера, он должен иметь тнп, позволяющий реализации контейнера скопировать объект. Контейнер может копировать объекты посредством копирующего конструктора или операции присваивания; в обоих случаях копия должна быть эквивалентна исходному объекту.
Грубо говоря, это означает, что любая ваша проверка на равенство значений объектов должна констатировать равенство копии и оригинала. Другими словами, копирование элементов должно работать весьма похоже на копирование встроенных типов (включая указатели). Например, следующий код Глава 17. Стандартные контейнеры 562 Ха Х:: орегагог= (сопл( Ха а) ( // копирование всех членов а в «Гя(з гвтигп *Иняз ) // подходящая операция присваивания делает Х подходящим типом элементов стандартных контейнеров, но гоЫ У::орега<ог= (сопят Уа а) ( // обнуление всех членов а ) // не подходящая операция присваивания 17.1.4.1.
Операция сравнения "<" Ассоциативные контейнеры требуют, чтобы их элементы могли быть упорядочены. То же относится и ко многим операциям, которые применяются к контейнерам (например, хогг О ). По умолчанию, для упорядочения элементов используется операция <. Если же эта операция не подходит, то программист сам предоставляет альтернативу (817.4.1.5, 818.4.2). Критерий упорядочения должен обеспечить так называемое строгое слабое упорядочение (зтпст звеа)с огдегзп8). Неформально это означает, что «меньше» и «равно» должны быть транзитивными.
То есть для критерия упорядочения стр: 1. стр(х,х) есть «ложь». 2. Если стр (х, у) — «истина» и стр (у, х) — «истина», то стр (х, х) — тоже «истинан. 3. Определим ваи(и(х,у) как! (стр(х,у) ( (стр(у,х) ) . Тогда, если вцил (х,у)— «истина» и вонзи(у,х) — «истина», то и вди)г (х, х) тоже «истина». Рассмотрим: гетр(а(в<с!азз йап> юИ хогг(11ап/1«вг, йап Ьзз) з // используем < для сравнении гетр(агв<сймз 7(ап, с(азз Стр> юИ юзт (йап багз(, яая (азг, Стр стр); р используем стр Первая из представленных версий использует операцию <, а вторая — пользовательскую функцию сравнения стр().
Допустим, мы хотим отсортировать контей- того же самого в отношении типа Уне достигает: для него операция присваивания не имеет традиционной семантики и не имеет принятого возвращаемого типа. Некоторые нарушения правил для стандартных контейнеров обнаруживаются компилятором, но те нарушения, которые компилятором не выявляются, могут приводить к непредсказуемому поведению.
Например, операция присваивания, генерирующая исключения, может оставить некоторые элементы недокопированными (в промежуточном состоянии), или вообще привести их в некорректное состояние, что вызовет серьезные проблемы впоследствии. Такая операция присваивания, вообще говоря, сама плохо спроектирована (814.4.б.!, приложение Е).
Когда копирование элементов для их помещения в контейнер — это не то, что требуется, альтернативой является помещение в контейнер указателей на объекты. Наиболее типичными примерами являются полиморфные типы ($2.5.4, 812.2.6). Например, для сохранения полиморфного поведения мы применяем гесгог<айаре*>, а не гесгог< Ягоре>. ) 7.1. Стандартные контейнеры 563 нер аул!1, используя нечувствительное к регистру букв сравнение. Мы можем это сделать, определив класс функциональных объектов (811.9, 818А), выполняющий сравнение, будучи вызванным для пары значений типа ззг(пя: с!азз )тосте ~У сазе-(тетйсее згпп8 сотраге ( риЫ(с: Ьоо! орегагог() (сопи згг1паз, соли милях) сопи; )1 Ьоо! Хосазе:: орегатог() (соль! згг!лдь х, сопзт мппяь у) соле! Юге(игп ггие (7 х И 1ехгсохгарЬ(са(1у (ет глол у, пот 1оlс(ле сазе га1о оссоилг ( зтппе:: сот! йега1ог р = х.
Ьеягп ( ); згппд::сола Ьегагог а = у. Ьеагл () 1 ьгЬ1(е(р! =х.епь!() зь 4! =у.епь!() зь тоиррег(ер) ==гоиррег(*Е) ) ЬЕР1 ++о; ) ь7(р == х.ель!() ) ге<игл а! = у.ель(() (Т(4 == у.епг(() ) ге!игл уагзег ге1игл 1оиррег(ер) «оиррег(*Е) 1 ) Теперь мы можем вызвать хогг(), используя данный критерий сравнения. Например, пусть контейнер 7Ьи11 изначально имеет следующее содержимое: уги11 ь арр1е реаг Арр!е Реаг 1етоп Тогда вызвав хогг(уги!1. Ьеи!п (), 7Ьи11. епг! (), Хосазе () ), получим Гги(1: Арр!е арр1е !егпоп . Реаг реаг в то время как обычная сортировка зог1(уги11.
Ьея1п (), 71 и11. епь!() ) дала бы иной результат: уги11: Арр!е Реаг арр!е !егаоп реаг в предположении, что в заданной кодировке заглавные буквы идут раньше строчных. Имейте в виду, что операция < для С-строк (то есть для типа сйаг*) не дает лексикографического упорядочения (813.5.2).
Из-за этого ассоциативные контейнеры работают неожиданно для многих пользователей, когда в качестве ключей используются С-строки. Чтобы заставить их работать надлежащим образом, для сравнения С-строк нужно организовать лексикографическое сравнение, например, следующим образом: заисг Сзгппа !ет Ьоо! орегагог ( ) (сот! слог* р, соль! слог* а) солью Бб4 Глава 17.
Стандартные контейнеры /геШ(п з(гетр (р, (!) <О( ) )( тар<сйаг*, 1п(, Сз(г!пя !езз> т( //здесь тар использует з(гстро для сравнения // ключей типа сопл( сйаг* 17.1.4.2. Другие операции сравнения Итак, по умолчанию контейнеры и алгоритмы используют операцию <, чтобы произвести сравнение на «меньше», Когда это не подходит, программист может определить свой собственный критерий сравнения, передавая его в качестве параметра.
Однако для проверки на равенство такого механизма передачи нет. Вместо этого, когда программист определяет свой критерий сшр, выполняются две проверки на равенство: (Т(х == у) дне делается в случае пользовательских сравнений ф'(! стр (х, у) ь й ! стр (у, х) ) р вот что делается в с(нл(ае пользовательского критерия стр Таким образом мы избавляемся от необходимости передавать каждому контейнеру и алгоритму критерий проверки на равенство. Это может показаться расточительным, но стандартная библиотека использует проверки на равенство не часто, к тому же в 50% таких случаев требуется всего лишь одно обрашение к сп(р() .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
