Онлайн библиотека PLAM.RU


  • Совет 1. Внимательно подходите к выбору контейнера
  • Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода
  • Совет 3. Реализуйте быстрое и корректное копирование объектов в контейнерах
  • Совет 4. Вызывайте empty вместо сравнения size() с нулем
  • Совет 5. Используйте интервальные функции вместо одноэлементных
  • Совет 6. Остерегайтесь странностей лексического разбора C++
  • Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера
  • Совет 8. Никогда не создавайте контейнеры, содержащие auto_ptr
  • Совет 9. Тщательно выбирайте операцию удаления
  • Совет 10. Помните о правилах и ограничениях распределителей памяти
  • Совет 11. Учитывайте область применения пользовательских распределителей памяти
  • Совет 12. Разумно оценивайте потоковую безопасность контейнеров STL

    • Контейнеры

    В STL входит немало полезных компонентов (в том числе итераторы, алгоритмы и объекты функций), однако большинство программистов C++ ставит на первое место именно контейнеры. По сравнению с массивами контейнеры обладают большей гибкостью и функциональностью. Они динамически увеличивают (а иногда и уменьшают) свои размеры, самостоятельно управляют памятью, следят за количеством хранящихся объектов, ограничивают алгоритмическую сложность поддерживаемых операций и обладают массой других достоинств. Популярность контейнеров STL легко объяснима — просто они превосходят своих конкурентов, будь то контейнеры из других библиотек или самостоятельные реализации. Контейнеры STL не просто хороши. Они действительно хороши.

    В этой главе приведены общие сведения, относящиеся ко всем типам контейнеров STL (конкретные типы контейнеров будут рассмотрены в других главах). В частности, мы рассмотрим такие вопросы, как выбор подходящего контейнера при заданных ограничениях; возможность работы кода, написанного для одного типа контейнера, с другими типами контейнеров; особая роль операций копирования объектов в контейнерах; проблемы, возникающие при создании контейнеров с указателями

    auto_ptr
    ; нюансы, связанные с удалением элементов; оптимизация работы с контейнерами и замечания относительно работы контейнеров в многопоточной среде.

    Список получился внушительным, но пусть вас это не пугает. Материал излагается небольшими порциями, а попутно вы встретите немало полезных идей, которые сможете немедленно применить в своих программах.

    Итак, STL предоставляет в ваше распоряжение множество разных контейнеров, но знаете ли вы, насколько широко это разнообразие? Следующая краткая сводка поможет вам убедиться в том, что вы ни о чем не забыли.

    Совет 1. Внимательно подходите к выбору контейнера

    • Стандартные последовательные контейнеры STL:

    vector, string, deque
    и
    list
    .

    • Стандартные ассоциативные контейнеры STL:

    set, multiset, map
    и
    multimap
    .

    • Нестандартные последовательные контейнеры:

    slist
    и
    rope
    . Контейнер
    slist
    представляет односвязный список, а
    rope
    — строку с дополнительными возможностями. Краткий обзор этих нестандартных (но достаточно широко распространенных) контейнеров приведен в совете 50.

    • Нестандартные ассоциативные контейнеры:

    hash_set, hash_multiset
    ,
    hash_ map
    и
    hash_multimap
    . Эти популярные разновидности стандартных ассоциативных контейнеров, построенные на базе хэш-таблиц, рассматриваются в совете 25.

    • 

    vector<char>
    как замена для
    string
    . Условия, при которых возможна подобная замена, описаны в совете 13.

    • 

    vector
    как замена для стандартных ассоциативных контейнеров. Как будет показано в совете 23, в некоторых ситуациях
    vector
    превосходит стандартные ассоциативные контейнеры как по быстродействию, так и по экономии памяти.

    • Некоторые стандартные контейнеры, не входящие в STL: массивы,

    bitset
    ,
    valarray
    ,
    stack
    ,
    queue
    и
    piority_queue
    . Поскольку эти контейнеры не относятся к STL, в этой книге они практически не упоминаются, хотя в совете 16 описан случай, когда массив оказывается предпочтительнее контейнеров SQL, а в совете 18 объясняется, почему
    bitset
    может быть лучше
    vector<bool>
    . Также стоит помнить о возможности использования массивов с алгоритмами STL, поскольку указатели могут работать как итераторы массивов.

    При столь широком ассортименте контейнеров возрастает и количество факторов, которыми следует руководствоваться при их выборе. К сожалению, многие описания STL ограничиваются поверхностным взглядом на мир контейнеров и полностью игнорируют многие факторы, относящиеся к выбору оптимального контейнера. Этот недостаток присущ даже Стандарту, который предлагает выбирать между

    vector, deque
    и
    list
    на основании следующих критериев: «…
    vector, list
    и
    deque
    обладают различными характеристиками в зависимости от класса выполняемых операций, в соответствии с которыми должен осуществляться выбор. Вектор (
    vector
    ) представляет собой тип последовательного контейнера, который используется в большинстве случаев. Список (
    list
    ) используется при частых операциях вставки и удаления в произвольной позиции. Дек (
    deque
    ) выбирается в случае, если большинство вставок и удалений производится в начале или в конце последовательности элементов».

    Если ограничиться алгоритмической сложностью, эта рекомендация звучит вполне разумно, но на практике приходится учитывать множество других факторов.

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

    В блоковых контейнерах (также называемых контейнерами со смежной памятью) элементы хранятся в одном или нескольких динамически выделяемых блоках памяти, по несколько элементов в каждом блоке. При вставке нового или удалении существующего элемента другие элементы того же блока сдвигаются вверх или вниз, освобождая место для нового элемента или заполняя место, ранее занимаемое удаленным элементом. Подобные перемещения влияют как на скорость работы (советы 5 и 14), так и на безопасность (об этом — ниже). К числу стандартных блоковых контейнеров относятся

    vector
    ,
    string
    и
    deque
    . Нестандартный контейнер
    rope
    также является блоковым.

    В узловых контейнерах каждый динамически выделенный фрагмент содержит ровно один элемент. Операции удаления и вставки выполняются только с указателями на узлы, не затрагивая содержимого самих узлов, и потому обходятся без перемещений данных в памяти. К этой категории относятся контейнеры связанных списков (такие как

    list
    и
    slist
    ), а также все стандартные ассоциативные контейнеры, обычно реализуемые в форме сбалансированных деревьев. Как будет показано в совете 25, реализация нестандартных хэшированных контейнеров тоже построена на узловом принципе.

    Разобравшись с терминологией, можно переходить к анализу факторов, учитываемых при выборе контейнера. В дальнейшем описании не учитываются контейнеры, не входящие в STL (массивы, битовые множества и т. д.), поскольку книга все-таки посвящена STL.

    • Нужна ли возможность вставки нового элемента в произвольной позиции контейнера? Если нужна, выбирайте последовательный контейнер; ассоциативные контейнеры не подходят.

    • Важен ли порядок хранения элементов в контейнере? Если порядок следования элементов не важен, хэшированные контейнеры попадают в число возможных кандидатов. В противном случае придется обойтись без них.

    • Должен ли контейнер входить в число стандартных контейнеров C++? Если выбор ограничивается стандартными контейнерами, то хэшированные контейнеры,

    slist
    и
    rope
    , исключаются.

    • К какой категории должны относиться итераторы? С технической точки зрения итераторы произвольного доступа ограничивают ваш выбор контейнерами

    vector, deque
    и
    string
    , хотя, в принципе, можно рассмотреть и возможность применения
    rope
    (этот контейнер рассматривается в совете 50). Если нужны двусторонние итераторы, исключается класс slist (совет 50) и одна распространенная реализация хэшированных контейнеров (совет 25).

    • Нужно ли предотвратить перемещение существующих элементов при вставке или удалении? Если нужно, воздержитесь от использования блоковых контейнеров (совет 5).

    • Должна ли структура памяти контейнера соответствовать правилам языка C? Если должна, остается лишь использовать

    vector
    (совет 16).

    • Насколько критична скорость поиска? Если скорость поиска критична, рассмотрите хэшированные контейнеры (совет 25), сортированные векторы (совет 23) и стандартные ассоциативные контейнеры — вероятно, именно в таком порядке.

    • Может ли в контейнере использоваться подсчет ссылок? Если подсчет ссылок вас не устраивает, держитесь подальше от

    string
    , поскольку многие реализации
    string
    построены на этом механизме (совет 13). Также следует избегать контейнера
    rope
    (совет 50). Конечно, средства для представления строк вам все же понадобятся — попробуйте использовать
    vector<char>
    .

    • Потребуется ли транзакционная семантика для операций вставки и удаления? Иначе говоря, хотите ли вы обеспечить надежную отмену вставок и удалений? Если хотите, вам понадобится узловой контейнер. При использовании транзакционной семантики для многоэлементных (например, интервальных — см. совет 5) вставок следует выбрать

    list
    — единственный стандартный контейнер, обладающий этим свойством. Транзакционная семантика особенно важна при написании кода, безопасного по отношению к исключениям. Вообще говоря, транзакционная семантика реализуется и для блоковых контейнеров, но за это приходится расплачиваться быстродействием и усложнением кода. За дополнительной информацией обращайтесь к книге Саттера «Exceptional C++» [8].

    • Нужно ли свести к минимуму количество недействительных итераторов, указателей и ссылок? Если нужно — выбирайте узловые контейнеры, поскольку в них операции вставки и удаления никогда не приводят к появлению недействительных итераторов, указателей и ссылок (если они не относятся к удаляемым элементам). В общем случае операции вставки и удаления в блоковых контейнерах могут привести к тому, что все итераторы, указатели и ссылки станут недействительными.

    • Не подойдет ли вам последовательный контейнер с итераторами произвольного доступа, в котором указатели и ссылки на данные всегда остаются действительными, если из контейнера ничего не удаляется, а вставка производится только в конце? Ситуация весьма специфическая, но если вы с ней столкнетесь — выбирайте

    deque
    . Следует заметить, что итераторы
    deque
    могут стать недействительными, даже если вставка производится только в конце контейнера. Это единственный стандартный контейнер STL, у которого итераторы могут стать недействительными при действительных указателях и ссылках.

    Вряд ли эти вопросы полностью исчерпывают тему. Например, в них не учитывается тот факт, что разные типы контейнеров используют разные стратегии выделения памяти (некоторые аспекты этих стратегий описаны в советах 10 и 14). Но и этот список наглядно показывает, что алгоритмическая сложность выполняемых операций — далеко не единственный критерий выбора. Бесспорно, она играет важную роль, но приходится учитывать и другие факторы.

    При выборе контейнеров STL предоставляет довольно большое количество вариантов, а за пределами STL их оказывается еще больше. Прежде чем принимать окончательное решение, обязательно изучите все возможные варианты. «…Контейнер, используемый в большинстве случаев»? Я так не думаю.

    Совет 2. Остерегайтесь иллюзий контейнерно-независимого кода

    Основным принципом STL является обобщение. Массивы обобщаются в контейнеры, параметризованные по типам хранящихся объектов. Функции обобщаются в алгоритмы, параметризованные по типам используемых итераторов. Указатели обобщаются в итераторы, параметризованные по типам объектов, на которые они указывают.

    Но это лишь начало. Конкретные разновидности контейнеров обобщаются в категории (последовательные и ассоциативные), а похожие контейнеры наделяются сходными функциями. Стандартные блоковые контейнеры (совет 1) обладают итераторами произвольного доступа, тогда как стандартные узловые контейнеры (также описанные в совете 1) поддерживают двусторонние итераторы. Последовательные контейнеры поддерживают операции

    push_front
    и/или
    push_back
    , у ассоциативных контейнеров такие операции отсутствуют. В ассоциативных контейнерах реализованы функции
    lower_bound
    ,
    upper_bound
    и
    equal_range
    , обладающие логарифмической сложностью, а в последовательных контейнерах их нет.

    При таких тенденциях к обобщению возникает естественная мысль — последовать положительному примеру. Желание похвальное. Несомненно, им стоит руководствоваться при написании собственных контейнеров, итераторов и алгоритмов, но многие программисты пытаются добиться этой цели несколько иным способом. Вместо того чтобы ориентироваться на конкретный тип контейнера, они пытаются обобщить синтаксис так, чтобы в программе, например, использовался

    vector
    , но позднее его можно было бы заменить на
    deque
    или
    list
    без изменения кода, в котором этот контейнер используется. Иначе говоря, они пытаются писать контейнерно-независимый код. Подобные обобщения, какими бы благими намерениями они не были вызваны, почти всегда нежелательны.

    Даже самый убежденный сторонник контейнерно-независимого кода вскоре осознает, что универсальный код, работающий как с последовательными, так и с ассоциативными контейнерами, особого смысла не имеет. Многие функции существуют только в контейнерах определенной категории; например, функции

    push_front
    и
    push_back
    поддерживаются только последовательными контейнерами; функции
    count
    и
    lower_bound
    — только ассоциативными контейнерами и т. д. Даже сигнатуры таких базовых операций, как
    insert
    и
    erase
    , зависят от категории. Например, в последовательном контейнере вставленный объект остается в исходной позиции, тогда как в ассоциативном контейнере он перемещается в позицию, соответствующую порядку сортировки данного контейнера. Или другой пример: форма erase, которой при вызове передается итератор, для последовательного контейнера возвращает новый итератор, но для ассоциативного контейнера не возвращается ничего (в совете 9 показано, как это обстоятельство влияет на программный код).

    Допустим, вас посетила творческая мысль — написать код, который работал бы со всеми распространенными последовательными контейнерами:

    vector
    ,
    deque
    и
    list
    . Разумеется, вам придется программировать в контексте общих возможностей этих контейнеров, а значит, функции
    reserve
    и
    capacity
    (совет 14) использовать нельзя, поскольку они не поддерживаются контейнерами
    deque
    и
    list
    . Присутствие
    list
    также означает, что вам придется отказаться от оператора
    []
    и ограничиться двусторонними итераторами, что исключает алгоритмы, работающие с итераторами произвольного доступа —
    sort
    ,
    stable_sort
    ,
    partial_sort
    и
    nth_element
    (совет 31).

    С другой стороны, исходное намерение поддерживать

    vector
    исключает функции
    push_front
    и
    pop_front
    ;
    vector
    и
    deque
    исключают применение
    splice
    и реализацию
    sort
    внутри контейнера. Учитывая те ограничения, о которых говорилось выше, последний запрет означает, что для вашего «обобщенного последовательного контейнера» не удастся вызвать никакую форму
    sort
    .

    Пока речь идет о вещах простых и очевидных. При нарушении любого из этих ограничений ваша программа не будет компилироваться по крайней мере для одного из контейнеров, которые вы намеревались поддерживать. Гораздо больше проблем возникнет с программами, которые будут компилироваться.

    В разных последовательных контейнерах действуют разные правила недействительности итераторов, указателей и ссылок. Чтобы ваш код правильно работал с

    vector
    ,
    deque
    и
    list
    , необходимо предположить, что любая операция, приводящая к появлению недействительных итераторов, указателей и ссылок в любом из этих контейнеров, приведет к тем же последствиям и в используемом контейнере. Отсюда следует, что после каждого вызова
    insert
    недействительным становится абсолютно все, поскольку
    deque::insert
    делает недействительными все итераторы, а из-за невозможности использования
    capacity
    приходится предполагать, что после операции
    vector::insert
    становятся недействительными все указатели и ссылки (как упоминается в совете 1, контейнер
    deque
    обладает уникальным свойством — в некоторых случаях его итераторы могут становиться недействительными с сохранением действительных указателей и ссылок). Аналогичные рассуждения приводят к выводу, что после каждого вызова
    erase
    все итераторы, указатели и ссылки также должны считаться недействительными.

    Недостаточно? Данные контейнера не передаются через интерфейс C, поскольку данная возможность поддерживается только для

    vector
    (совет 16). Вы не сможете создать экземпляр контейнера с типом
    bool
    — как будет показано в совете 18,
    vector<bool>
    не всегда ведет себя как
    vector
    и никогда не хранит настоящие логические величины. Вы даже не можете рассчитывать на постоянное время вставки-удаления, характерное для
    list
    , поскольку в
    vector
    и
    deque
    эти операции выполняются с линейной сложностью.

    Что же остается после всего сказанного? «Обобщенный последовательный контейнер», в котором нельзя использовать

    reserve
    ,
    capacity
    ,
    operator[], push_front, pop_front, splice
    и вообще любой алгоритм, работающий с итераторами произвольного доступа; контейнер, у которого любой вызов
    insert
    и
    erase
    выполняется с линейной сложностью и приводит к недействительности всех итераторов, указателей и ссылок; контейнер, несовместимый с языком С и не позволяющий хранить логические величины. Захочется ли вам использовать подобный контейнер в своем приложении? Вряд ли.

    Если умерить амбиции и отказаться от поддержки

    list
    , вы все равно теряете
    reserve
    ,
    capacity
    ,
    push_front
    и
    pop_front
    ; вам также придется полагать, что вызовы
    insert
    и
    erase
    выполняются с линейной сложностью, а все итераторы, указатели и ссылки становятся недействительными; вы все равно теряете совместимость с С и не можете хранить в контейнере логические величины.

    Даже если отказаться от последовательных контейнеров и взяться за ассоциативные контейнеры, дело обстоит не лучше. Написать код, который бы одновременно работал с

    set
    и
    map
    , практически невозможно, поскольку в
    set
    хранятся одиночные объекты, а в
    map
    хранятся пары объектов. Даже совместимость с
    set
    и
    multiset
    (или
    map
    и
    multimap
    ) обеспечивается с большим трудом. Функция
    insert
    , которой при вызове передается только значение вставляемого элемента, возвращает разные типы для
    set/map
    и их multi-аналогов, при этом вы должны избегать любых допущений относительно того, сколько экземпляров данной величины хранится в контейнере. При работе с
    map
    и
    multimap
    приходится обходиться без оператора
    []
    , поскольку эта функция существует только в
    map
    .

    Согласитесь, игра не стоит свеч. Контейнеры действительно отличаются друг от друга, обладают разными достоинствами и недостатками. Они не были рассчитаны на взаимозаменяемость, и с этим фактом остается только смириться. Любые попытки лишь искушают судьбу, а она этого не любит.

    Но рано или поздно наступит день, когда окажется, что первоначальный выбор контейнера был, мягко говоря, не оптимальным, и вы захотите переключиться на другой тип. При изменении типа контейнера нужно не только исправить ошибки, обнаруженные компилятором, но и проанализировать весь код, где он используется, и разобраться, что следует изменить в свете характеристик нового контейнера и правил перехода итераторов, указателей и ссылок в недействительное состояние. Переходя с

    vector
    на другой тип контейнера, вы уже не сможете рассчитывать на С-совместимую структуру памяти, а при обратном переходе нужно проследить за тем, чтобы контейнер не использовался для хранения
    bool
    .

    Если вы знаете, что тип контейнера в будущем может измениться, эти изменения можно упростить обычным способом — инкапсуляцией. Одно из простейших решений основано на использовании определений

    typedef
    для типов контейнера и итератора. Следовательно, фрагмент

    class Widget{...};

    vector<Widget> vw;

    Widget bestWidget;

    … // Присвоить значение bestWidget

    vector<Widget>::iterator i = // Найти Widget с таким же значением,

     find(vw.begin(),vw.end().bestWidget) // как у bestWidget

    записывается в следующем виде:

    class Widget{...};

    typedef vector<Widget> WidgetContaner;

    typedef WidgetContainer:iterator WCIterator;

    WidgetContaner vw;

    Widget bestWidget;

    …

    WCIterator i = find(vw.begin().vw.end(),bestWidget);

    Подобная запись значительно упрощает изменение типа контейнера, что особенно удобно, когда изменение сводится к простому добавлению нестандартного распределителя памяти (такое изменение не влияет на правила недействительности итераторов/указателей/ссылок).

    class Widget{...};

    template<typename T> // В совете 10 объясняется, почему

    SpecialAllocator{...}; // необходимо использовать шаблон

    typedef vector<Widget, SpecialAllocator<Widget> WidgetContainer;

    typedef WidgetContainer::iterator WCIterator;

    WidgetContainer vw;// Работает

    Widget bestWidget;

    WCIterator i=find(vw.begin().vw.end().bestWidget); // Работает

    Даже если вас не интересуют аспекты

    typedef
    , связанные с инкапсуляцией, вы наверняка оцените экономию времени. Предположим, у вас имеется объект типа

    map<string,

     vector<Widget>::iterator,

     CIStringCompare> // CIStringCompare - сравнение строк

                      // без учета регистра: см. совет 19

    и вы хотите перебрать элементы множества при помощи

    const_iterator
    . Захочется ли вам вводить строку

    map<string.vector<Widget>::iterator, CIStringCompare>::const_iterator

    больше одного раза? После непродолжительной работы в STL вы поймете, что

    typedef
    — ваш друг.

    Typedef
    всего лишь определяет синоним для другого типа, поэтому инкапсуляция производится исключительно на лексическом уровне. Она не помешает клиенту сделать то, что он мог сделать ранее (и не позволит сделать то, что было ранее недоступно). Если вы захотите ограничить зависимость клиента от выбранного типа контейнера, вам понадобятся более серьезные средства — классы.

    Чтобы ограничить объем кода, требующего модификации при замене типа контейнера, скройте контейнер в классе и ограничьте объем информации, доступной через интерфейс класса. Например, если вам потребуется создать список клиентов, не используйте класс

    list
    напрямую, определите класс
    CustomerList
    и инкапсулируйте
    list
    в его закрытой части:

    class CustomerList {

    private:

     typedef list<Customer> CustomerContainer;

     typedef CustomerContainer::iterator CCIterator;

     CustomerContainer customers:

    public: // Объем информации, доступной

     …      // через этот интерфейс, ограничивается

    };

    На первый взгляд происходящее выглядит глупо. Ведь список клиентов — это список, не правда ли? Вполне возможно. Но в будущем может оказаться, что возможность вставки-удаления в середине списка используется не так часто, как предполагалось вначале, зато нужно быстро выделить 20% клиентов с максимальным объемом сделок — эта задача просто создана для алгоритма

    nthelement
    (совет 31). Однако
    nthelement
    требует итератора произвольного доступа и не будет работать с контейнером
    list
    . В этой ситуации «список» лучше реализовать на базе
    vector
    или
    deque
    .

    Рассматривая подобные изменения, необходимо проанализировать все функции класса

    CustomerList
    , а также всех «друзей» (
    friend
    ) и посмотреть, как на них отразится это изменение (в отношении быстродействия, недействительности итераторов/указателей/ссылок и т. д.), но при грамотной инкапсуляции деталей реализации
    CustomerList
    это изменение практически не повлияет на клиентов
    CustomerList
    .

    Совет 3. Реализуйте быстрое и корректное копирование объектов в контейнерах

    В контейнерах хранятся объекты, но не те, которые вы им передаете. Более того, при получении объекта из контейнера вам предоставляется не тот объект, который находился в контейнере. При включении объекта (вызовом

    insert, push_back
    и т. д.) в контейнер заносится копия указанного объекта. При получении объекта из контейнера (например, вызовом
    front
    или
    back
    ) вы также получаете копию. Копирование на входе, копирование на выходе — таковы правила STL.

    Но и после того, как объект окажется в контейнере, он может участвовать в операциях копирования. В результате вставки или удаления элементов в

    vector, string
    и
    deque
    существующие элементы контейнера обычно перемещаются (копируются) в памяти (советы 5 и 14). Алгоритмы сортировки (совет 31),
    next_permutation
    и
    previous_permutation
    ;
    remove
    ,
    unique
    и их родичи (совет 32);
    rotate
    и
    reverse
    — все эти операции приводят к копированию объектов. Да, копирование объектов действительно занимает очень важное место в STL.

    Возможно, вам будет интересно узнать, как же производится копирование. Очень просто — объект копируется вызовом соответствующих функций этого объекта, а точнее копирующего конструктора и копирующего оператора присваивания. В пользовательских классах эти функции обычно объявляются следующим образом:

    class Widget{

    public:

     Widget(const Widget&):// Копирующий конструктор

     Widget& operator=(const Widget&);// Копирующий оператор присваивания

     …

    };

    Как обычно, если вы не объявите эти функции самостоятельно, компилятор сделает это за вас. Встроенные типы (

    int
    , указатели и т. д.) копируются простым копированием их двоичного представления. Копирующие конструкторы и операторы присваивания описаны в любом учебнике по C++. В частности, эти функции рассмотрены в советах 11 и 27 книги «Effective C++».

    Теперь вам должен быть ясен смысл этого совета. Если контейнер содержит объекты, копирование которых сопряжено с большими затратами, простейшее занесение объектов в контейнер может заметно повлиять на скорость работы программы. Чем больше объектов перемещается в контейнере, тем больше памяти и тактов процессора расходуется на копирование. Более того, у некоторых объектов само понятие «копирование» имеет нетрадиционный смысл, и при занесении таких объектов в контейнер неизменно возникают проблемы (пример приведен в совете 8).

    В ситуациях с наследованием копирование становится причиной отсечения. Иначе говоря, если создать контейнер объектов базового класса и попытаться вставить в него объекты производного класса, «производность» этих объектов утрачивается при копировании объектов (копирующим конструктором базового класса) в контейнер:

    vector<Widget> vw;

    class Special Widget: // SpecialWidget наследует от класса

     public Widget{...};  // Widget (см. ранее)

    SpecialWidget sw; // sw копируется в vw как объект базового класса

    vw.push_back(sw); // Специализация объекта теряется (отсекается)

    Проблема отсечения предполагает, что вставка объекта производного класса в контейнер объектов базового класса обычно приводит к ошибке. А если вы хотите, чтобы полученный объект обладал поведением объекта производного класса (например, вызывал виртуальные функции объектов производного класса), вставка всегда приводит к ошибке. За дополнительной информацией обращайтесь к «Effective C++», совет 22. Другой пример проявления этой проблемы в STL описан в совете 38.

    Существует простое решение, обеспечивающее эффективное, корректное и свободное от проблемы отсечения копирование — вместо объектов в контейнере хранятся указатели. Иначе говоря, вместо контейнера для хранения

    Widget
    создается контейнер для
    Widget*
    . Указатели быстро копируются, результат точно совпадает с ожидаемым (поскольку копируется базовое двоичное представление), а при копировании указателя ничего не отсекается. К сожалению, у контейнеров указателей имеются свои проблемы, обусловленные спецификой STL. Они рассматриваются в советах 7 и 33. Пытаясь справиться с этими проблемами и при этом не нажить хлопот с эффективностью, корректностью и отсечением, вы, вероятно, обнаружите симпатичную альтернативу — умные указатели. За дополнительной информацией обращайтесь к совету 7.

    Если вам показалось, что STL злоупотребляет копированием, не торопитесь с выводами. Да, копирование в STL выполняется довольно часто, но в целом библиотека спроектирована с таким расчетом, чтобы избежать лишнего копирования. Более того, она избегает лишнего создания объектов. Сравните с поведением классического массива — единственного встроенного контейнера C и C++:

    Widget w[maxNumWidgets]; // Создать массив объектов Widget

     // Объекты инициализируются конструктором

     // по умолчанию

    В этом случае конструируются

    maxNumWidgets
    объектов
    Widget
    , даже если на практике будут использоваться лишь некоторые из них или все данные, инициализированные конструктором по умолчанию, будут немедленно перезаписаны данными, взятыми из другого источника (например, из файла). Вместо массива можно воспользоваться контейнером STL
    vector
    и создать вектор, динамически увеличивающийся в случае необходимости:

    vector<Widget> vw; // Создать вектор, не содержащий ни одного

     // объекта Widget и увеличивающийся по мере

     // необходимости

    Можно также создать пустой вектор, в котором зарезервировано место для

    maxNumWidgets
    объектов
    Widget
    , но не сконструирован ни один из этих объектов:

    vector<Widget> vw;

    vw.reserve(maxNumWidgets); // Функция reserve описана в совете 14

    По сравнению с массивами контейнеры STL ведут себя гораздо цивилизованнее. Они создают (посредством копирования) столько объектов, сколько указано, и только по вашему требованию, а конструктор по умолчанию выполняется только с вашего разрешения. Да, контейнеры STL создают копии; да, в особенностях их работы необходимо хорошо разбираться, но не стоит забывать и о том, что они означают большой шаг вперед по сравнению с массивами.

    Совет 4. Вызывайте empty вместо сравнения size() с нулем

    Для произвольного контейнера с следующие две команды фактически эквивалентны:

    if (c.size()==0)...

    if (c.empty())...

    Возникает вопрос — почему же предпочтение отдается одной конструкции, особенно если учесть, что

    empty
    обычно реализуется в виде подставляемой (inline) функции, которая просто сравнивает
    size()
    с нулем и возвращает результат?

    Причина проста: функция

    empty
    для всех стандартных контейнеров выполняется с постоянной сложностью, а в некоторых реализациях
    list
    вызов
    size
    требует линейных затрат времени.

    Но почему списки так себя ведут? Почему они не обеспечивают выполнения

    size
    с постоянной сложностью? Это объясняется в основном уникальными свойствами функций врезки (
    splicing
    ). Рассмотрим следующий фрагмент:

    list<int> list1;

    list<int> list2;

    list1.splice(                                  // Переместить все узлы list2

     list1.end(),list2,                            // от первого вхождения 5

     find(list2.begin(), list2.end(), 5),          // до последнего вхождения 10

     find(list2.rbegin(), list2.rend(), 10).base() // в конец listl

    );                                             // Вызов base() рассматривается

                                                   // в совете 28

    Приведенный фрагмент не работает, если только значение 10 не входит в

    list2
    после 5, но пока не будем обращать на это внимания. Вместо этого зададимся вопросом: сколько элементов окажется в списке
    list1
    после врезки? Разумеется, столько, сколько было до врезки, в сумме с количеством новых элементов. Последняя величина равна количеству элементов в интервале, определяемом вызовами
    find(list2.begin(), list2.end(), 5)
    и
    find(list2.rbegin(),list2.rend(),10).base()
    . Сколько именно? Чтобы ответить на этот вопрос, нужно перебрать и подсчитать элементы интервала. В этом и заключается проблема.

    Допустим, вам поручено реализовать

    list
    . Это не просто контейнер, а стандартный контейнер, поэтому заранее известно, что класс будет широко использоваться. Естественно, реализация должна быть как можно более эффективной. Операция определения количества элементов в списке будет часто использоваться клиентами, поэтому вам хотелось бы, чтобы операция
    size
    работала с постоянной сложностью. Класс
    list
    нужно спроектировать так, чтобы он всегда знал количество содержащихся в нем элементов.

    В то же время известно, что из всех стандартных контейнеров только

    list
    позволяет осуществлять врезку элементов без копирования данных. Можно предположить, что многие клиенты выбирают
    list
    именно из-за эффективности операции врезки. Они знают, что интервальная врезка из одного списка в другой выполняется за постоянное время; вы знаете, что они это знают, и постараетесь не обмануть их надежды на то, что функция
    splice
    работает с постоянными затратами времени.

    Возникает дилемма. Чтобы операция size выполнялась с постоянной сложностью, каждая функция класса

    list
    должна обновлять размеры списков, с которыми она работает. К числу таких функций относится и
    splice
    . Но сделать это можно только одним способом — функция должна подсчитать количество вставляемых элементов, а это не позволит обеспечить постоянное время выполнения
    splice
    … чего мы, собственно, и пытались добиться. Если отказаться от обновления размеров списков функцией splice, добиться постоянного времени выполнения для
    splice
    можно, но тогда с линейной сложностью будет выполняться
    size
    — ей придется перебирать всю структуру данных и подсчитывать количество элементов. Как ни старайся, чем-то —
    size
    или
    splice
    — придется пожертвовать. Одна из этих операций может выполняться с постоянной сложностью, но не обе сразу.

    В разных реализациях списков эта проблема решается разными способами в зависимости от того, какую из операций —

    size
    или
    splice
    — авторы хотят оптимизировать по скорости. При работе с реализацией
    list
    , в которой было выбрано постоянное время выполнения
    splice
    , лучше вызывать
    empty
    вместо
    size
    , поскольку
    empty
    всегда работает с постоянной скоростью. Впрочем, даже если вы не используете такую реализацию, не исключено, что это произойдет в будущем. Возможно, программа будет адаптирована для другой платформы с другой реализацией STL, или вы перейдете на новую реализацию STL для текущей платформы.

    В любом случае вы ничем не рискуете, вызывая

    empty
    вместо проверки условия
    size()=0
    . Мораль: если вам потребовалось узнать, содержит ли контейнер ноль элементов — вызывайте
    empty
    .

    Совет 5. Используйте интервальные функции вместо одноэлементных

    Есть два вектора,

    v1
    и
    v2
    . Как проще всего заполнить
    v1
    содержимым второй половины
    v2
    ? Только не надо мучительно размышлять над тем, что считать «половиной» при нечетном количестве элементов в
    v2
    . Просто постарайтесь быстро дать разумный ответ.

    Время истекло! Если вы предложили

    v1.assign(v2.begin()+v2.size()/2, v2.end())

    или нечто похожее — поздравляю, пять баллов. Если в вашем ответе присутствуют вызовы более чем одной функции, но при этом он обходится без циклов, вы получаете «четверку». Если в ответе задействован цикл, вам есть над чем поработать, а если несколько циклов — значит, вы узнаете из этой книги много нового.

    Кстати говоря, если при чтении ответа вы произнесли «Чего-чего?» или что-нибудь в этом роде, читайте внимательно, потому что речь пойдет об очень полезных вещах.

    Я привел эту задачу по двум причинам. Во-первых, она напоминает вам о существовании очень удобной функции

    assign
    , о которой многие программисты попросту забывают. Функция
    assign
    поддерживается всеми стандартными последовательными контейнерами (
    vector, string, deque
    и
    list
    ). Каждый раз, когда вам требуется полностью заменить содержимое контейнера, подумайте, нельзя ли добиться желаемой цели присваиванием. Если вы просто копируете один контейнер в другой контейнер того же типа, задача решается функцией
    operator=
    . Но, как показывает приведенный пример, существует также функция
    assign
    , которая позволяет заполнить контейнер новыми данными в тех случаях, когда
    operator=
    не подходит.

    Во-вторых, эта задача показывает, почему интервальные функции лучше своих одноэлементных аналогов. Интервальной называется функция контейнера, которая, подобно алгоритмам STL, определяет интервал элементов для выполняемой операции при помощи двух параметров-итераторов. Без интервальной функции нам пришлось бы создавать специальный цикл:

    vector<Widget> v1,v2; // Предполагается, что v1 и v2 -

                          // векторы объектов Widget

    …

    v1.clear():

    for (vector<Widget>::const_iterator ci=v2.begin()+v2.size()/2; ci != v2.end(); ++ci)

     v1.push_back(*ci);

    В совете 43 подробно объясняется, почему использовать явные циклы не рекомендуется, но и без этого ясно, что написание этого фрагмента потребует больше усилий, чем простой вызов

    assign
    . Цикл также отрицательно влияет на быстродействие, но к этой теме мы вернемся позже.

    Одно из возможных решений заключается в том, чтобы последовать совету 43 и воспользоваться алгоритмом:

    v1.clear();

    copy(v2.begin()+v2.size()/2, v2.end(), back_inserter(v1));

    Но и этот вариант требует больших усилий, чем простой вызов

    assign
    . Более того, хотя цикл не встречается в программе, он наверняка присутствует внутри вызова
    copy
    (см. совет 43). В результате потенциальное снижение быстродействия не исчезает (вскоре мы поговорим об этом). А сейчас я хочу ненадолго отвлечься от темы и заметить, что практически все случаи использования
    copy
    , когда приемный интервал задается итератором вставки (
    inserter, back_inserter
    или
    front_inserter
    ), могут — и должны — заменяться вызовами интервальных функций. Например, вызов
    copy
    заменяется интервальной версией
    insert
    :

    v1.insert(v1.end(), v2.begin()+v2.size()/2. v2.end());

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

    v1
    . Вызов
    copy
    означает примерно то же, но не столь очевидно. В данном случае важно не то, что элементы копируются, а то, что в
    v1
    добавляются новые данные. Функция
    insert
    прямо говорит об этом, а
    copy
    лишь сбивает с толку. Нет ничего особенно интересного в том факте, что данные где-то копируются, — собственно, вся библиотека STL построена на принципе копирования. Копирование играет настолько важную роль в STL, что ему посвящен совет 3.

    Многие программисты STL злоупотребляют функцией

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

    Вернемся к примеру с

    assign
    . Мы уже выяснили две причины, по которым интервальным функциям отдается предпочтение перед их одноэлементными аналогами.

    • Написание кода с интервальными функциями обычно требует меньших усилий.

    • Решения с интервальными функциями обычно выглядят более наглядно и логично.

    Короче говоря, программы с интервальными функциями удобнее как писать, так и читать. О чем тут еще говорить?

    Впрочем, некоторые склонны относить эти аргументы к стилю программирования, а вопросы стиля вызывают у программистов такую же жаркую полемику, как и тема выбора Лучшего В Мире Редактора (хотя о чем тут спорить? Всем известно, что это

    Emacs
    ). Было бы неплохо иметь более универсальный критерий для сравнения интервальных функций с одноэлементными. Для стандартных последовательных контейнеров такой критерий существует: эффективность. При работе со стандартными последовательными контейнерами применение одноэлементных функций приводит к более частому выделению памяти, более частому копированию объектов и/или выполнению лишних операций по сравнению с реализацией, основанной на интервальных функциях.

    Предположим, вы хотите скопировать массив

    int
    в начало
    vector
    (исходное размещение данных в массиве может объясняться тем, что данные были получены через унаследованный интерфейс с языком С. Проблемы, возникающие при объединении контейнеров STL с интерфейсом C, описаны в совете 16). Решение с интервальной функцией
    insert
    контейнера
    vector
    выглядит просто и бесхитростно:

    int data[numValues]; // Предполагается, что numValues

                         // определяется в другом месте

    vector<int> v;

    …

    v.insert(v.begin().data, data+numValues); // Вставить int из data

                                              // в начало v

    Вероятно, решение с циклическим вызовом

    insert
    выглядит примерно так:

    vector<int>::iterator insertLoc(v.begin());

    for(int i=0; i<numValues; ++i) {

     insertLoc = v.insert(insertLoc.data[i]);

    }

    Обратите внимание на сохранение значения, возвращаемого при вызове

    insert
    , до следующей итерации. Если бы значение
    insertLoc
    не обновлялось после каждой вставки, возникли бы две проблемы. Во-первых, все итерации цикла после первой повели бы себя непредсказуемым образом, поскольку в результате каждого вызова
    insert
    значение
    insertLoc
    становилось бы недействительным. Во-вторых, даже если бы значение
    insertLoc
    оставалось действительным, вставка всегда производилась бы в начале вектора (то есть в
    v.begin()
    ), и в результате содержимое массива было бы скопировано в обратном порядке.

    Попробуем последовать совету 43 и заменим цикл вызовом copy:

    copy(data, data+numValues, inserter(v, v.begin()));

    После создания экземпляра шаблона решение с

    copy
    практически идентично решению с циклом, поэтому в своем анализе эффективности мы ограничимся вторым вариантом и будем помнить, что все сказанное в равной степени относится к решению с
    copy
    . В случае с циклом вам будет проще понять, чем обусловлены потери эффективности. Да, это именно «потери» во множественном числе, поскольку решение с одноэлементной версией
    insert
    сопряжено с тремя видами затрат, отсутствующими при использовании интервальной версии
    insert
    .

    Первая потеря обусловлена лишними вызовами функций. Естественно, последовательная вставка

    numValues
    элементов требует
    numValues
    вызовов
    insert
    . При вызове интервальной формы
    insert
    достаточно одного вызова функции, тем самым экономится
    numValues-1
    вызов. Возможно, подстановка (
    inlining
    ) избавит вас от этих затрат… а может, и нет. Уверенным можно быть лишь в одном: при использовании интервальной формы
    insert
    эти затраты заведомо отсутствуют.

    Подстановка не спасает от второго вида затрат, обусловленных неэффективностью перемещения существующих элементов

    v
    на итоговые позиции после вставки. Каждый раз, когда
    insert
    включает в
    v
    новый элемент, все элементы после точки вставки смещаются на одну позицию, освобождая место. Элемент в позиции p перемещается в позицию p+1 и т. д. В нашем примере
    numValues
    элементов вставляются в начало
    v
    . Следовательно, каждый элемент, находившийся в
    v
    до вставки, сдвигается в общей сложности на
    numValues
    позиций. Но при каждом вызове
    insert
    элемент сдвигается только на одну позицию, поэтому это потребует
    numValues
    перемещений. Если до вставки вектор
    v
    содержал n элементов, количество перемещений будет равно n
    *numValues
    . В нашем примере вектор
    v
    содержит числа типа
    int
    , поэтому перемещение сведется к простому вызову
    memmove
    , но если бы в
    v
    хранились пользовательские типы вроде
    Widget
    , то каждое перемещение было бы сопряжено с вызовом оператора присваивания или копирующего конструктора данного типа (в большинстве случаев вызывался бы оператор присваивания, но перемещения последнего элемента вектора обеспечивались бы вызовом копирующего конструктора). Таким образом, в общем случае последовательная вставка
    numValues
    новых объектов в начало
    vector<Widget>
    с n элементами требует n
    *numValues
    вызовов функций: (n-1)
    *numValues
    вызовов оператора присваивания
    Widget
    и
    numValues
    вызовов копирующего конструктора
    Widget
    . Даже если эти вызовы будут подставляемыми, все равно остаются затраты на перемещение элементов
    numValues
    раз.

    С другой стороны, Стандарт требует, чтобы интервальные функции

    insert
    перемещали существующие элементы контейнера непосредственно в итоговые позиции, то есть по одному перемещению на элемент. Общие затраты составят n перемещений (
    numValues
    для копирующего конструктора типа объектов в контейнере, остальное — для оператора присваивания этого типа). По сравнению с одноэлементной версией интервальная версия
    insert
    выполняет на n
    *(numValues-1)
    меньше перемещений. Только задумайтесь: при
    numValues=100
    интервальная форма
    insert
    выполняет на 99% меньше перемещений, чем эквивалентный код с многократно повторяющимися вызовами одноэлементной формы
    insert
    !

    Прежде чем переходить к третьей категории затрат, стоит сделать небольшое замечание. То, что написано в предыдущем абзаце — правда, только правда и ничего, кроме правды, но это не вся правда. Интервальная форма

    insert
    может переместить элемент в конечную позицию за одну операцию только в том случае, если ей удастся определить расстояние между двумя итераторами без перехода. Это возможно почти всегда, поскольку такой возможностью обладают все прямые итераторы, а они встречаются практически повсеместно. Все итераторы стандартных контейнеров обладают функциональными возможностями прямых итераторов — в том числе и итераторы нестандартных хэшированных контейнеров (совет 25). Указатели, играющие роль итераторов в массивах, тоже обладают этой возможностью. В общем-то, из всех стандартных итераторов она не присуща только итераторам ввода и вывода. Следовательно, все сказанное выше справедливо в том случае, если итераторы, передаваемые интервальной форме
    insert
    , не являются итераторами ввода (скажем,
    istream_iterator
    — см. совет 6). Только в этом случае интервальной форме
    insert
    приходится перемещать элементы на свои итоговые места по одной позиции, вследствие чего преимущества интервальной формы теряются (для итераторов вывода эта проблема вообще не возникает, поскольку итераторы вывода не могут использоваться для определения интервала
    insert
    ).

    Мы подошли к третьей категории затрат, от которых страдают неразумные программисты, использующие многократную вставку отдельного элемента вместо одной вставки целого интервала. Эти затраты связаны с выделением памяти, хотя они также имеют неприятные аспекты, относящиеся к копированию. Как объясняется в совете 14, когда вы пытаетесь вставить элемент в вектор, вся память которого заполнена, вектор выделяет новый блок памяти, копирует элементы из старой памяти в новую, уничтожает элементы в старой памяти и освобождает ее.

    После этого вставляется новый элемент. В совете 14 также говорится о том, что при заполнении всей памяти многие реализации векторов удваивают свою емкость, поэтому вставка

    numValues
    новых элементов может привести к тому, что новая память будет выделяться со временем log2numValues. В совете 14 упоминается о существовании реализации, обладающей таким поведением, поэтому последовательная вставка 1000 элементов может привести к 10 операциям выделения памяти с побочными затратами на копирование элементов). С другой стороны, интервальная вставка может вычислить объем необходимой памяти еще до начала вставки (если ей передаются прямые итераторы), поэтому ей не придется выделять новую память больше одного раза. Как нетрудно предположить, экономия может оказаться довольно существенной.

    Приведенные рассуждения относились к векторам, но они в равной степени применимы и к строкам. В определенной степени они относятся и к декам, но по механизму управления памятью деки отличаются от векторов и строк, поэтому аргумент относительно многократного выделения памяти в этом случае не действует. Впрочем, два других фактора (лишние перемещения элементов в памяти и лишние вызовы функций) обычно все же действуют, хотя и несколько иным образом.

    Из стандартных последовательных контейнеров остается только

    list
    , но и в этом случае интервальная форма
    insert
    обладает преимуществами перед одноэлементной. Конечно, такой фактор, как лишние вызовы функций, продолжает действовать, но из-за некоторых особенностей связанных списков проблемы с копированием и выделением памяти отсутствуют. Вместо них возникает другая проблема: многократные избыточные присваивания указателям
    next
    и
    prev
    для некоторых узлов списка.

    Каждый раз, когда в связанный список включается новый элемент, необходимо присвоить значения указателям

    next
    и
    prev
    нового узла. Кроме того, необходимо задать указатель
    next
    предыдущего узла (назовем его узлом B) и указатель
    prev
    следующего узла (назовем его узлом A).

    Предположим, в список была вставлена серия новых узлов вызовами одноэлементной версии

    insert
    . Во всех узлах, кроме последнего, значение
    next
    будет задаваться дважды — сначала указатель будет ссылаться на узел А, а затем на следующий вставленный элемент. Указатель
    prev
    узла А будет изменяться при каждой вставке нового узла в предшествующую позицию. Если перед А в список включаются
    numValues
    узлов, будет выполнено
    numValues-1
    лишних присваиваний указателю
    next
    вставленных узлов и
    numValues-1
    лишних присваиваний указателю
    prev
    узла А, то есть в общей сложности
    2*(numValues-l)
    лишних операций присваивания. Конечно, присваивание указателю обходится недорого, но зачем вообще платить, если можно обойтись без этого?

    Наверное, вы уже поняли, что без лишних присваиваний действительно можно обойтись. Для этого достаточно воспользоваться интервальной формой

    insert
    контейнера
    list
    . Функция заранее знает, сколько узлов будет вставлено в список, что позволяет сразу присвоить каждому указателю правильное значение.

    Таким образом, для стандартных последовательных контейнеров выбор между одноэлементной и интервальной вставкой отнюдь не сводится к стилю программирования. Для ассоциативных контейнеров критерий эффективности уже не столь убедителен, хотя проблема лишних вызовов функций существует и в этом случае. Кроме того, некоторые специализированные разновидности интервальной вставки могут оптимизироваться и в ассоциативных контейнерах, хотя, насколько мне известно, подобные оптимизации пока существуют лишь в теории. Конечно, к тому моменту, когда вы будете читать эту книгу, теория может воплотиться на практике, и тогда интервальная вставка в ассоциативных контейнерах действительно будет превосходить одноэлементную вставку по эффективности. В любом случае она никогда не будет работать менее эффективно, поэтому вы ничего не теряете.

    Если отвлечься от соображений эффективности, остается непреложный факт: вызовы интервальных функций более компактны, а программа становится более наглядной, что упрощает ее долгосрочное сопровождение. Даже этих двух причин вполне достаточно для того, чтобы отдать предпочтение интервальным функциям, а выигрыш в эффективности можно рассматривать как бесплатное приложение.

    После столь пространных рассуждений о чудесах интервальных функций было бы уместно привести краткую сводку таких функций. Если вы заранее знаете, какие функции контейнеров существуют в интервальных версиях, вам будет проще определить, когда ими можно воспользоваться. В приведенных ниже сигнатурах тип

    iterator
    в действительности означает тип итератора для данного контейнера, то есть контейнер
    ::iterator
    . С другой стороны, тип
    InputIterator
    означает любой допустимый итератор ввода.

    • Интервальные конструкторы. У всех стандартных контейнеров существуют конструкторы следующего вида:

    контейнер::контейнер(InputIterator begin, // Начало интервала

                         InputIterator end); // Конец интервала

    При передаче этому конструктору итераторов

    istream_iterator
    и
    istreambuf_iterator
    (совет 29) иногда встречается одна из самых удивительных ошибок C++, вследствие которой компилятор интерпретирует эту конструкцию как объявление функции, а не как определение нового объекта контейнера. В совете 6 рассказано все, что необходимо знать об этой ошибке, в том числе и способы ее преодоления.

    • Интервальная вставка. Во всех стандартных последовательных контейнерах присутствует следующая форма insert:

    void контейнер::insert(iterator position, // Позиция вставки

                           InputIterator begin, // Начало интервала

                           InputIterator end); // Конец интервала

    Ассоциативные контейнеры определяют позицию вставки при помощи собственных функций сравнения, поэтому в них предусмотрена сигнатура без параметра

    position
    :

    void контейнер::insert(InputIterator begin, InputIterator end);

    Рассматривая возможности замены одноэлементных вызовов insert интервальными версиями, не забывайте, что некоторые одноэлементные варианты маскируются под другими именами. Например, push_front и push_back заносят в контейнер отдельный элемент, хотя в их названии отсутствует слово insert. Если в программе встречается циклический вызов push_front/push_back или алгоритм (например, copy), которому в качестве параметра передается front_inserter или back_inserter, перед вами потенциальный кандидат для применения интервальной формы insert.

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

    iterator контейнер::erase(iterator begin, iterator end);

    В ассоциативных контейнерах сигнатура выглядит так:

    void контейнер::erase(iterator begin, iterator end);

    Чем обусловлены различия? Утверждается, что в ассоциативных контейнерах возврат итератора (для элемента, следующего за удаленным) привел бы к неприемлемому снижению быстродействия. Мне и многим другим это утверждение кажется сомнительным, но Стандарт есть Стандарт, а в нем сказано, что версии

    erase
    для последовательных и ассоциативных контейнеров обладают разными типами возвращаемого значения.

    Многое из того, что говорилось в этом совете по поводу эффективности

    insert
    , относится и к
    erase
    . Интервальная форма
    erase
    также сокращает количество вызовов функций по сравнению с одноэлементной формой. При одноэлементном удалении элементы тоже сдвигаются на одну позицию к своему итоговой позиции, тогда как в интервальном варианте каждый элемент перемещается к итоговой позиции за одну операцию.

    Но erase не присущ такой недостаток

    insert
    контейнеров
    vector
    и
    string
    , как многократные выделения памяти (конечно, для erase речь пойдет о многократном освобождении). Дело в том, что память, занимаемая
    vector
    и
    string
    , автоматически увеличивается для новых элементов, но при уменьшении количества элементов память не освобождается (в совете 17 рассказано о том, как уменьшить затраты освободившейся памяти в
    vector
    и
    string
    ).

    К числу особенно важных аспектов интервального удаления относится идиома erase-remove, описанная в совете 29.

    • Интервальное присваивание. Как упоминалось в самом начале совета, во всех последовательных контейнерах предусмотрена интервальная форма

    assign
    :

    void контейнер::assign(InputIterator begin, InputIterator end);

    Итак, мы рассмотрели три веских аргумента в пользу применения интервальных функций вместо их одноэлементных аналогов. Интервальные функции обеспечивают более простую запись, они более четко выражают ваши намерения и обладают более высоким быстродействием. Против этого трудно что-либо возразить.

    Совет 6. Остерегайтесь странностей лексического разбора C++

    Предположим, у вас имеется файл, в который записаны числа типа

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

    ifstream dataFile("ints.dat");

    list<int> data(istream_iterator<int>(dataFile), // Внимание! Эта строка

     istream_iterator<int>());                      // работает не так, как

                                                    // вы предполагали

    Идея проста: передать пару

    istream_iterator
    интервальному конструктору
    list
    (совет 5), после чего скопировать числа из файла в список.

    Программа будет компилироваться, но во время выполнения она ничего не сделает. Она не прочитает данные из файла. Она даже не создаст список — а все потому, что вторая команда не объявляет список и не вызывает конструктор. Вместо этого она… Произойдет нечто настолько странное, что я даже не рискну прямо сказать об этом, потому что вы мне не поверите. Вместо этого я попробую объяснить суть дела постепенно, шаг за шагом. Надеюсь, вы сидите? Если нет — лучше поищите стул…

    Начнем с азов. Следующая команда объявляет функцию

    f
    , которая получает
    double
    и возвращает
    int
    :

    int f(double d);

    То же самое происходит и в следующей строке. Круглые скобки вокруг имени параметра

    d
    не нужны, поэтому компилятор их игнорирует:

    int f(double(d));// То же,- круглые скобки вокруг d игнорируются

    Рассмотрим третий вариант объявления той же функции. В нем просто не указано имя параметра:

    int f(double);// То же; имя параметра не указано

    Вероятно, эти три формы объявления вам знакомы, хотя о возможности заключать имена параметров в скобки известно далеко не всем (до недавнего времени я о ней не знал).

    Теперь рассмотрим еще три объявления функции. В первом объявляется функция

    g
    с параметром — указателем на функцию, которая вызывается без параметров и возвращает
    double
    :

    int g(double (*pf)()); // Функции g передается указатель на функцию

    То же самое можно сформулировать и иначе. Единственное различие заключается в том, что

    pf
    объявляется в синтаксисе без указателей (допустимом как в C, так и в C++):

    int g(double pf()); // То же; pf неявно интерпретируется как указатель

    Как обычно, имена параметров могут опускаться, поэтому возможен и третий вариант объявления

    g
    без указания имени
    pf
    :

    int g(double());// То же: имя параметра не указано

    Обратите внимание на различия между круглыми скобками вокруг имени параметра (например, параметра

    d
    во втором объявлении
    f
    ) и стоящими отдельно (как в этом примере). Круглые скобки, в которые заключено имя параметра, игнорируются, а круглые скобки, стоящие отдельно, обозначают присутствие списка параметров; они сообщают о присутствии параметра, который является указателем на функцию.

    После небольшой разминки с объявлениями

    f
    и
    g
    мы возвращаемся к фрагменту, с которого начинается этот совет. Ниже он приводится снова:

    list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

    Держитесь и постарайтесь не упасть. Перед вами объявление функции

    data
    , возвращающей тип
    list<int>
    . Функция
    data
    получает два параметра:

    • Первый параметр,

    dataFile
    , относится к типу
    istream_iterator<int>
    . Лишние круглые скобки вокруг
    dataFile
    игнорируются.

    • Второй параметр не имеет имени. Он относится к типу указателя на функцию, которая вызывается без параметров и возвращает

    istream_iterator<int>
    .

    Любопытно, не правда ли? Однако такая интерпретация соответствует одному из основных правил C++: все, что может интерпретироваться как указатель на функцию, должно интерпретироваться именно так. Каждый программист с опытом работы на C++ встречался с теми или иными воплощениями этого правила. Сколько раз вы встречались с такой ошибкой:

    class Widget{...}; // Предполагается, что у Widget

                       // имеется конструктор по умолчанию

    Widget w(); // Какая неприятность...

    Вместо объекта класса

    Widget
    с именем
    w
    в этом фрагменте объявляется функция
    w
    , которая вызывается без параметров и возвращает
    Widget
    . Умение распознавать подобные «ляпы» — признак хорошей квалификации программиста C++.

    Все это по-своему интересно, однако мы нисколько не приблизились к поставленной цели: инициализировать объект

    list<int>
    содержимым файла. Зато теперь мы знаем, в чем заключается суть проблемы, и легко справимся с ней. Объявления формальных параметров не могут заключаться в круглые скобки, но никто не запрещает заключить в круглые скобки аргумент при вызове функции, поэтому простое добавление круглых скобок поможет компилятору увидеть происходящее под нужным углом зрения:

    list<int> data((istream_iterator<int>(dataFile)), // Обратите внимание

     istream_iterator<int>());                        // на круглые скобки

                                                      // вокруг первого аргумента

                                                      // конструктора list

    Именно так следует объявлять данные. Учитывая практическую полезность

    istream_iterator
    и интервальных конструкторов (совет 5), этот прием стоит запомнить.

    К сожалению, не все компиляторы знают об этом. Из нескольких протестированных компиляторов почти половина соглашалась только на неправильное объявление

    data
    без дополнительных круглых скобок! Чтобы умиротворить такие компиляторы, можно закатить глаза и воспользоваться неверным, как было показано выше, объявлением
    data
    , но это недальновидное и плохо переносимое решение.

    Более грамотный выход заключается в том, чтобы отказаться от модного использования анонимных объектов

    istream_iterator
    при объявлении
    data
    и просто присвоить этим итераторам имена. Следующий фрагмент работает всегда:

    ifstream dataFile("ints.dat");

    istream_iterator<int> dataBegin(dataFile);

    istream_iterator<int> dataEnd;

    list<int> data(dataBegin.dataEnd);

    Именованные объекты итераторов противоречат стандартному стилю программирования STL, но зато ваша программа будет однозначно восприниматься как компиляторами, так и людьми, которые с ними работают.

    Совет 7. При использовании контейнеров указателей, для которых вызывался оператор new, не забудьте вызвать delete для указателей перед уничтожением контейнера

    Контейнеры STL отличаются умом и сообразительностью. Они поддерживают итераторы для перебора как в прямом, так и в обратном направлении (

    begin
    ,
    end
    ,
    rbegin
    и т.д.); они могут сообщить тип хранящихся в них объектов (
    value_type
    ); они выполняют все необходимые операции управления памятью при вставке и удалении; они сообщают текущее количество элементов и максимальную вместимость (
    size
    и
    max_size
    соответственно); и, конечно же, они автоматически уничтожают все хранящиеся в них объекты при уничтожении самого контейнера.

    Работая с такими интеллектуальными контейнерами, многие программисты вообще забывают о необходимости «прибрать за собой» и надеются, что контейнер выполнит за них всю грязную работу. Нередко их ожидания оправдываются, но если контейнер содержит указатели на объекты, созданные оператором

    new
    , этого не происходит. Разумеется, контейнер указателей уничтожает все хранящиеся в нем элементы при уничтожении самого контейнера, но «деструктор» указателя ничего не делает! Он не вызывает
    delete
    .

    В результате при выполнении следующего фрагмента возникает утечка ресурсов:

    void doSomething() {

    vector<Widget*> vwp;

    for (int i=0; i<SOME_MAGIC_NUMBER; ++i) vwp.push_back(new Widget);

     … // Использовать vwp

    } // Здесь происходит утечка Widget!

    Все элементы

    vwp
    уничтожаются при выходе
    vwp
    из области видимости, но это не изменяет того факта, что
    delete
    не вызывается для объектов, созданных оператором
    new
    . За удаление таких элементов отвечает программист, а не контейнер. Так было задумано. Только программист знает, нужно ли вызывать
    delete
    для этих указателей.

    Обычно это делать нужно. На первый взгляд решение выглядит довольно просто:

    void doSomethng() {

     vector<Widget*> vwp;

     ... // Как прежде

     for (vector<Widget*>::iterator = vwp.begin(); i != vwp.end(); ++i)

      delete *i;

    }

    Такое решение работает, если не проявлять особой разборчивости в трактовке этого понятия. Во-первых, новый цикл

    for
    делает примерно то же, что и
    for_each
    , но он не столь нагляден (совет 43). Во-вторых, этот код небезопасен по отношению к исключениям. Если между заполнением
    vwp
    указателями и вызовом
    delete
    произойдет исключение, это снова приведет к утечке ресурсов. К счастью, с обеими проблемами можно справиться.

    Чтобы от

    for_each
    -подобного цикла перейти непосредственно к
    for_each
    , необходимо преобразовать
    delete
    в объект функции. С этим справится даже ребенок — если, конечно, вы найдете ребенка, который захочет возиться с STL:

    template <typename T>

    struct DeleteObject:                     // В совете 40 показано,

     public unary_function<const T*, void> { // зачем нужно наследование

     void operator()(const T* ptr) const {

      delete ptr;

     }

    };

    Теперь становится возможным следующее:

    void doSomething() {

     … //См. ранее

     for_each(vwp.begin(), vwp.end(), DeleteObject<Widget>());

    }

    К сожалению, вам приходится указывать тип объектов, удаляемых

    DeleteObject
    (в данном примере
    Widget
    ), а это раздражает,
    vwp
    представляет собой
    vector<Widget*>
    — разумеется,
    DeleteObject
    будет удалять указатели
    Widget*
    ! Подобные излишества не только раздражают, но и приводят к возникновению трудно обнаружимых ошибок. Допустим, кто-нибудь по случайности объявляет класс, производный от
    string
    :

    class SpecialString: public string{...};

    Это рискованно, поскольку

    string
    , как и все стандартные контейнеры STL, не имеет виртуального деструктора, а открытое наследование от классов без виртуального деструктора относится к числу основных табу C++. Подробности можно найти в любой хорошей книге по C++. (В «Effective C++» ищите в совете 14.) И все же некоторые программисты поступают подобным образом, поэтому давайте разберемся, как будет вести себя следующий код:

    void doSomething() {

     deque<SpecialString*> dssp;

     for_each(dssp.begin(), end(), // Непредсказуемое поведение! Удаление

      DeleteObject<string>());     // производного объекта через указатель

                                   // на базовый класс при отсутствии

                                   // виртуального деструктора

    }

    Обратите внимание:

    dssp
    объявляется как контейнер, в котором хранятся указатели
    SpecialString*
    , но автор цикла
    for_each
    сообщает
    DeleteObject
    , что он будет удалять указатели
    string*
    . Понятно, откуда берутся подобные ошибки. По своему поведению
    SpecialString
    имеет много общего со
    string
    , поэтому клиенту легко забыть, что вместо
    string
    он использует
    SpecialString
    .

    Чтобы устранить ошибку (а также сократить объем работы для клиентов

    DeleteObject
    ), можно предоставить компилятору возможность вычислить тип указания, передаваемого
    DeleteObject::operator()
    . Все, что для этого нужно, — переместить определение шаблона из
    DeleteObject
    в
    operator()
    :

    struct DeleteObject{ // Убрали определение шаблона

                         // и базовый класс

     template<typename T> // Определение шаблона

     void operator()(const T* ptr) const {

      delete ptr;

     }

    };

    Компилятор знает тип указателя, передаваемого

    DeleteObject::operator()
    , поэтому мы можем заставить его автоматически создать экземпляр
    operator()
    для этого типа указателя. Недостаток подобного способа вычисления типа заключается в том, что мы отказываемся от возможности сделать объект
    DeleteObject
    адаптируемым (совет 40). Впрочем, если учесть, на какое применение он рассчитан, вряд ли это можно считать серьезным недостатком.

    С новой версией

    DeleteObject
    код клиентов
    SpecialString
    выглядит так:

    void doSomething() {

     deque<SpecialString*> dssp;

     ...

     for_each(dssp.begin(), dssp.end(),

      DeleteObject());// Четко определенное поведение

    }

    Такое решение прямолинейно и безопасно по отношению к типам, что и требовалось.

    Однако безопасность исключений все еще не достигнута. Если исключение произойдет после создания

    SpecialString
    оператором
    new
    , но перед вызовом
    for_each
    , снова произойдет утечка ресурсов. Проблема решается разными способами, но простейший выход заключается в переходе от контейнера указателей к контейнеру умных указателей (обычно это указатели с подсчетом ссылок). Если вы незнакомы с концепцией умных указателей, обратитесь к любой книге по C++ для программистов среднего уровня и опытных. В книге «More Effective C++» этот материал приводится в совете 28.

    Библиотека STL не содержит умных указателей с подсчетом ссылок. Написание хорошего умного указателя (то есть такого, который бы всегда правильно работал) — задача не из простых, и заниматься ею стоит лишь в случае крайней необходимости. Я привел код умного указателя с подсчетом ссылок в «More Effective C++» в 1996 году. Хотя код был основан на хорошо известной реализации умного указателя, а перед изданием книги материал тщательно проверялся опытными программистами, за эти годы было найдено несколько ошибок. Количество нетривиальных сбоев, возникающих при подсчете ссылок в умных указателях, просто невероятно (за подробностями обращайтесь к списку опечаток и исправлений для книги «More Effective C++» [28]).

    К счастью, вам вряд ли придется создавать собственные умные указатели, поскольку найти проверенную реализацию не так сложно. Примером служит указатель

    shared_ptr
    из библиотеки Boost (совет 50). Используя
    shared_ptr
    , можно записать исходный пример данного совета в следующем виде:

    void doSomething() {

     typedef boost::shared_ptr<Widget> SPW; //SPW = "shared pointer

                                            // to Widget"

     vector<SPW> vwp;

     for (int i=0; i<SOME_MAGIC_NUMBER; ++i) //Создать SPW no Widget*

      vwp.push_back(SPW(new Widget));        //и вызвать push_back

      …                                      //Использовать vwp

    } //Утечки Widget не происходит.

      //даже если в предыдущем фрагменте

      //произойдет исключение

    Никогда не следует полагать, что автоматическое удаление указателей можно обеспечить созданием контейнера, содержащего

    auto_ptr
    . Эта кошмарная мысль чревата такими неприятностями, что я посвятил ей совет 8.

    Главное, что необходимо запомнить: контейнеры STL разумны, но они не смогут решить, нужно ли удалять хранящиеся в них указатели. Чтобы избежать утечки ресурсов при работе с контейнерами указателей, необходимо либо воспользоваться объектами умных указателей с подсчетом ссылок (такими, как

    shared_ptr
    из библиотеки Boost), либо вручную удалить каждый указатель при уничтожении контейнера.

    Напрашивается следующая мысль: если структура

    DeleteObject
    помогает справиться с утечкой ресурсов для контейнеров, содержащих указатели на объекты, можно создать аналогичную структуру
    DeleteArray
    , которая поможет избежать утечки ресурсов для контейнеров с указателями на массивы. Конечно, такое решение возможно. Другой вопрос, насколько оно разумно. В совете 13 показано, почему динамически размещаемые массивы почти всегда уступают
    vector
    и
    string
    , поэтому прежде чем садиться за написание
    DeleteArray
    , пожалуйста, прочитайте совет 13. Может быть, он убедит вас в том, что лучше обойтись без
    DeleteArray
    .

    Совет 8. Никогда не создавайте контейнеры, содержащие auto_ptr

    Честно говоря, в книге, посвященной эффективному использованию STL, данный совет не совсем уместен. Контейнеры

    auto_ptr
    (COAP, Containers Of Auto_Ptr) запрещены, а программа, которая попытается их использовать, не будет компилироваться. Комитет по стандартизации C++ приложил неслыханные усилия в этом направлении. Возможно, мне вообще не стоило бы говорить о контейнерах
    auto_ ptr
    — о них вам расскажет компилятор, причем в самых нелестных выражениях.

    Однако многие программисты работают на платформах STL, на которых COAP не запрещены. Более того, многие программисты по-прежнему подвержены иллюзии и видят в COAP простое, прямолинейное, эффективное средство для борьбы с утечкой ресурсов, часто присущей контейнерам указателей (советы 7 и 33). В результате возникает искушение воспользоваться COAP, даже если их невозможно создать.

    Вскоре я объясню, почему COAP произвели такой переполох, что Комитет по стандартизации предпринял специальные шаги по их запрещению. А пока начнем с первого недостатка, для понимания которого не нужно разбираться в

    auto_ptr
    и вообще в контейнерах: COAP не переносимы. Да и как может быть иначе? Они запрещены стандартом C++, и наиболее передовые платформы STL уже выполняют это требование. Вероятно, со временем платформы STL, которые сейчас не соответствуют Стандарту, выполнят его требования. Когда это произойдет, программы, использующие COAP, станут еще менее переносимыми, чем сейчас. Тот, кто заботится о переносимости своих программ, отвергнет COAP хотя бы по этой причине.

    Впрочем, не исключено, что переносимость вас не волнует. Если это так, позвольте напомнить об уникальном (а по мнению некоторых — нелепом) смысле операции копирования

    auto_ptr
    .

    При копировании

    auto_ptr
    право владения объектом, на который ссылается указатель, переходит к копии, а исходному указателю присваивается NULL. Да, вы не ошиблись: копирование указателя auto_ptr приводит к его модификации.

    auto_ptr<Widget> pw1(new Widget); //pw1 ссылается на Widget

    auto_ptr<Widget> pw2(pw1);        //pw2 ссылается на объект Widget,

                                      //принадлежащий pw1; pw1 присваивается

                                      //NULL (таким образом, объект Widget

                                      //передается от pw1 к pw2)

    pwl = pw2; //pw1 снова ссылается на Widget:

               //pw2 присваивается NULL

    Конечно, такое поведение необычно и даже по-своему интересно, но для пользователя STL в первую очередь важно то, что оно приводит к крайне неожиданным последствиям. Рассмотрим внешне безобидный фрагмент, который создает вектор

    auto_ptr<Widget>
    и сортирует его функцией, сравнивающей значения Widget:

    bool WidgetAPCompare(const auto_ptr<Widget>& lhs, const auto_ptr<Widget>& rhs) {

     return *lhs < *rhs; // Предполагается, что для объектов Widget

                         // существует оператор <

    }

    vector<auto_ptr<Widget> > widgets; // Создать вектор и заполнить его

    …                                  // указателями auto_ptr на Widget.

                                       // Помните, что этот фрагмент

                                       // не должен компилироваться!

    sort(widgets.begin(), widgets.end(), // Отсортировать вектор

     widgetAPCompare);

    Пока все выглядит вполне разумно, да и с концептуальной точки зрения все действительно разумно — но результат разумным никак не назовешь. Например, в процессе сортировки некоторым указателям

    auto_ptr
    , хранящимся в
    Widget
    , может быть присвоено значение NULL. Сортировка вектора приводит к изменению его содержимого! Давайте разберемся, как это происходит.

    Оказывается, реализация

    sort
    часто строится на некой разновидности алгоритма быстрой сортировки. Работа этого алгоритма строится на том, что некоторый элемент контейнера выбирается в качестве «опорного», после чего производится рекурсивная сортировка по значениям, большим и меньшим либо равным значению опорного элемента. Реализация такого алгоритма в
    sort
    может выглядеть примерно так:

    template<class RandomAccessIterator, // Объявление sort скопировано

     class Compare>                      // прямо из Стандарта

    void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {

     // typedef описывается ниже

     typedef typename iterator_traits<RandomAccessIterator>::value_type ElementType;

     RandomAccessIterator i;

     ...                         // Присвоить i указатель на опорный элемент

     ElementType pivotValue(*i); // Скопировать опорный элемент в локальную

     ...                         // временную переменную; см. далее комментарий.

                                 // Остальная сортировка

    }

    Если вы не привыкли читать исходные тексты STL, этот фрагмент выглядит жутковато, но в действительности в нем нет ничего страшного. Нетривиально здесь выглядит только запись

    iterator_traits<RandomAccessIterator>::value_type
    ,  но это всего лишь принятое в STL обозначение типа объекта, на который указывают итераторы, переданные
    sort
    . Перед ссылкой
    iterator_traits<RandomAccessIterator>::value_type
    должен стоять префикс
    typename
    , поскольку это имя типа, зависящее от параметра шаблона (в данном случае
    RandomAccessIterator
    ), — дополнительная информация приведена на с. 20.

    Проблемы возникают из-за следующей команды, которая копирует элемент из сортируемого интервала в локальный временный объект:

    ElementType pivotValue(*i);

    В данном случае элементом является

    auto_ptr<Widget>
    , поэтому в результате скопированному указателю
    auto_ptr
    (тому, который хранится в векторе) присваивается
    NULL
    . Более того, когда
    pivotValue
    выходит из области видимости, происходит автоматическое удаление объекта
    Widget
    , на который
    pivotValue
    ссылается. Итак, после вызова
    sort
    содержимое вектора изменяется и по меньшей мере один объект
    Widget
    удаляется. Вследствие рекурсивности алгоритма быстрой сортировки существует вероятность того, что сразу нескольким элементам вектора будет присвоено значение
    NULL
    и сразу несколько объектов
    Widget
    будут удалены, поскольку опорный элемент копируется на каждом уровне рекурсии.

    Подобные ловушки весьма зловредны, и Комитет по стандартизации постарался, чтобы вы заведомо не попадались в них. Уважайте их труд и никогда не создавайте контейнеры

    auto_ptr
    , даже если ваша платформа STL это позволяет.

    Впрочем, это вовсе не исключает возможности создания контейнеров умных указателей. Контейнеры умных указателей вполне допустимы. В совете 50 описано, где найти умные указатели, хорошо работающие в контейнерах STL, просто

    auto_ptr
    не относится к их числу.

    Совет 9. Тщательно выбирайте операцию удаления

    Допустим, у нас имеется стандартный контейнер STL

    с
    , содержащий числа типа
    int
    :

    контейнер<int> с;

    и вы хотите удалить из него все объекты со значением 1963. Как ни странно, способ решения этой задачи зависит от контейнера; универсального решения не существует.

    Для блоковых контейнеров (

    vector
    ,
    deque
    или
    string
    — см. совет 1) оптимальный вариант построен на использовании идиомы
    erase-remove
    (совет 32):

    c.erase(remove(c.begin(), c.end(), 1963), // Идиома erase-remove хорошо

     c.end());                                // подходит для удаления элементов

                                              // с заданным значением

                                              // из контейнеров vector, string

                                              //и deque

    Приведенное решение работает и для контейнеров

    list
    , но как будет показано в совете 44, функция
    remove
    контейнера
    list
    работает эффективнее:

    с.remove(1963); // Функция remove хорошо подходит для удаления

                    // элементов с заданным значением из списка

    Стандартные ассоциативные контейнеры (такие как

    set
    ,
    multiset
    ,
    map
    и
    multimap
    ) не имеют функции
    remove
    с именем
    remove
    , а использование алгоритма
    remove
    может привести к стиранию элементов контейнера (совет 32) и возможной порче его содержимого. За подробностями обращайтесь к совету 22, где также объясняется, почему вызовы remove для контейнеров
    map/multimap
    не компилируются никогда, а для контейнеров
    set/multiset
    — компилируются в отдельных случаях.

    Для ассоциативных контейнеров правильным решением будет вызов

    erase
    :

    c.erase(1963); // Функция erase обеспечивает оптимальное

                   // удаление элементов с заданным значением

                   // из стандартных ассоциативных контейнеров

    Функция

    erase
    не только справляется с задачей, но и эффективно решает ее с логарифмической сложностью (вызовы
    remove
    в последовательных контейнерах обрабатываются с линейной сложностью). Более того, в ассоциативных контейнерах функция
    erase
    обладает дополнительным преимуществом — она основана на проверке эквивалентности вместо равенства (это важное различие рассматривается в совете 19).

    Слегка изменим проблему. Вместо того чтобы удалять из с все объекты с заданным значением, давайте удалим все объекты, для которых следующий предикат (совет 39) возвращает

    true
    :

    bool badValue(int х); // Возвращает true для удаляемых объектов

    В последовательных контейнерах (

    vector
    ,
    string
    ,
    deque
    и
    list
    ) достаточно заменить
    remove
    на
    remove_if
    :

    c.erase(remove_if(c.begin(), c.end(), badValue), // Лучший способ уничтожения

     c.end());                                       // объектов, для которых badValue

                                                     // возвращает true, в контейнерах

                                                     // vector, string и deque

    с.remove_if(badValue); // Оптимальный способ уничтожения

                           // объектов, для которых badValue

                           // возвращает true, в контейнере

                            // list

    Со стандартными ассоциативными контейнерами дело обстоит посложнее. Существуют два решения: одно проще программируется, другое эффективнее работает. В первом решении нужные значения копируются в новый контейнер функцией

    remove_copy
    , после чего содержимое двух контейнеров меняется местами:

    АссоцКонтейнер<int> с;//с - один из стандартных

    …                     // ассоциативных контейнеров

    АссоцКонтейнер<int> goodValues: // Временный контейнер для хранения

                                    // элементов, оставшихся после удаления

    remove_copy_if(c.begin(), c.end(), // Скопировать оставшиеся элементы

     inserter(goodValues,              // из с в goodValues

     goodValues.end()), badValue);

    с.swap(goodValues);// Поменять содержимое с и goodValues

    У подобного решения имеется недостаток — необходимость копирования элементов, остающихся после удаления. Такое копирование может обойтись дороже, чем нам хотелось бы.

    От этих затрат можно избавиться за счет непосредственного удаления элементов из исходного контейнера. Но поскольку в ассоциативных контейнерах отсутствует функция, аналогичная

    remove_if
    , придется перебирать все элементы с в цикле и принимать решение об удалении текущего элемента.

    С концептуальной точки зрения эта задача несложна, да и реализуется она просто. К сожалению, решение, которое первым приходит в голову, редко бывает правильным. Вероятно, многие программисты предложат следующий вариант:

    АссоцКонтейнер<int> с;

    …

    for(АссоцКонтейнер<int>::iterator i=cbegin(); // Наглядный, бесхитростный

        i!=cend();                                // и ошибочный код, который

        ++i) {                                    // стирает все элементы с

     if (badValue(*i)) c.erase(i);                // для которых badValue

    }                                             // возвращает true.

                                                  // Не поступайте так!

    Выполнение этого фрагмента приводит к непредсказуемым результатам. При стирании элемента контейнера все итераторы, указывающие на этот элемент, становятся недействительными. Таким образом, после возврата из

    c.erase(i)
    итератор
    i
    становится недействительным. Для нашего цикла это фатально, поскольку после вызова
    erase
    итератор
    i
    увеличивается (
    ++i
    в заголовке цикла
    for
    ).

    Проблема решается просто: необходимо позаботиться о том, чтобы итератор переводился на следующий элемент с перед вызовом

    erase
    . Это проще всего сделать постфиксным увеличением i при вызове:

    АссоцКонтейнер<int> с;

    for(АссоцКонтейнер<int>::iterator i=c.begin();// Третья часть заголовка

        i!=c.end();                               // цикла for пуста; i теперь

        /* пусто */) {                            // изменяется внутри цикла

    if (badValue(*i)) c.erase(i++);// Для удаляемых элементов

     else ++i;                     // передать erase текущее

    }                              // значение i и увеличить i.

                                   // Для остающихся элементов

                                   // просто увеличить i

    Новый вариант вызова

    erase
    работает, поскольку выражение
    i++
    равно старому значению
    i
    , но у него имеется побочный эффект — приращение
    i
    . Таким образом, мы передаем старое (не увеличенное) значение
    i
    и увеличиваем
    i
    перед вызовом
    erase
    . Именно это нам и требовалось. Хотя это решение выглядит просто, лишь немногие программисты предложат его с первой попытки.

    Пора сделать следующий шаг. Помимо простого удаления всех элементов, для которых

    badValue
    возвращает
    true
    , мы также хотим регистрировать каждую операцию удаления в журнале.

    Для ассоциативных контейнеров задача решается очень просто, поскольку она требует лишь тривиальной модификации созданного цикла:

    ofstream logFile;// Файл журнала

    АссоцКонтейнер<int> с;

    …

    for(АссоцКонтейнер<int>::iterator i=c.begin();// Заголовок цикла остается

        i!=c.end();) {                            // без изменений

     if(badValue(*i)) {

      logFile<<"Erasing "<<*i<<'\n'; // Вывод в журнал

      c.erase(i++);// Удаление

    } else ++i;

    }

    На этот раз хлопоты возникают с

    vector
    ,
    string
    и
    deque
    . Использовать идиому
    erase/remove
    не удается, поскольку
    erase
    или
    remove_if
    нельзя заставить вывести данные в журнал. Более того, вариант с циклом
    for
    , только что продемонстрированный для ассоциативных контейнеров, тоже не подходит, поскольку для контейнеров
    vector
    ,
    string
    и
    deque
    он приведет к непредсказуемым последствиям. Вспомните, что для этих контейнеров в результате вызова
    erase
    становятся недействительными все итераторы, указывающие на удаляемый элемент. Кроме того, недействительными становятся все итераторы после удаляемого элемента, в нашем примере — все итераторы после
    i
    . Конструкции вида
    i++
    ,
    ++i
    и т. д. невозможны, поскольку ни один из полученных итераторов не будет действительным.

    Следовательно, с

    vector
    ,
    string
    и
    deque
    нужно действовать иначе. Мы должны воспользоваться возвращаемым значением erase, которое содержит именно то, что нам требуется — действительный итератор, который указывает на элемент, следующий за удаленным. Иначе говоря, программа выглядит примерно так:

    for(ПослКонтейнер<int>::iterator = cbegin(); i != cend(); ) {

     if (badValue(*i)) {

      logFile<<"Erasing "<<*i<<'\n';

      i=c.erase()); // Сохраняем действительный итератор i,

     }              // для чего ему присваивается значение,

     else ++i;      // возвращаемое функцией erase

    }

    Такое решение превосходно работает, но только для стандартных последовательных контейнеров. По весьма сомнительным причинам (совет 5) функция

    erase
    для стандартных ассоциативных контейнеров возвращает
    void
    . В этом случае приходится использовать методику с постфиксным приращением итератора, переданного
    erase
    . Кстати говоря, подобные различия между последовательными и ассоциативными контейнерами — один из примеров того, почему контейнерно-независимый код обычно считается нежелательным (совет 2).

    Какое из этих решений лучше подойдет для контейнера

    list
    ? Оказывается, в отношении перебора и удаления
    list
    может интерпретироваться как
    vector/string/deque
    или как ассоциативный контейнер — годятся оба способа. Обычно выбирается первый вариант, поскольку
    list
    , как и
    vector/string/deque
    , принадлежит к числу последовательных контейнеров. С точки зрения опытного программиста STL программа, в которой перебор и удаление из
    list
    производятся по правилам ассоциативных контейнеров, выглядит странно.

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

    Удаление всех объектов с заданным значением:

    • контейнеры

    vector
    ,
    string
    и
    deque
    : используйте идиому
    erase/remove
    ;

    • контейнер

    list
    : используйте
    list::remove
    ;

    • стандартный ассоциативный контейнер: используйте функцию

    erase
    .

    Удаление всех объектов, соответствующих заданному предикату:

    • контейнер

    vector
    ,
    string
    и
    deque
    : используйте идиому
    erase/remove_if
    ;

    • контейнер

    list
    : используйте
    list::remove_if
    ;

    • стандартный ассоциативный контейнер: используйте

    remove_copy_if/swap
    или напишите цикл перебора элементов контейнера, но не забудьте о постфиксном приращении итератора, передаваемого при вызове
    erase
    .

    Дополнительные операции в цикле (кроме удаления объектов):

    • стандартный последовательный контейнер: напишите цикл перебора элементов, но не забывайте обновлять итератор значением, возвращаемым

    erase
    при каждом вызове;

    • стандартный ассоциативный контейнер: напишите цикл перебора элементов с постфиксным приращением итератора, передаваемого при вызове

    erase
    .

    Как видите, эффективное удаление элементов контейнера не сводится к простому вызову

    erase
    . Правильный подход зависит от того, по какому принципу отбираются удаляемые элементы, в каком контейнере они хранятся и какие дополнительные операции требуется выполнить при удалении. Действуйте осторожно и следуйте рекомендациям данного совета, и все будет нормально. Невнимательность обернется неэффективной работой или непредсказуемым поведением программы.

    Совет 10. Помните о правилах и ограничениях распределителей памяти

    Распределители памяти первоначально разрабатывались как абстракция для моделей памяти, позволяющих разработчикам библиотек игнорировать различия между

    near
    - и
    far
    -указателями в некоторых 16-разрядных операционных системах (например, DOS и ее зловредных потомках), однако эта попытка провалилась. Распределители также должны были упростить разработку объектных диспетчеров памяти, но вскоре выяснилось, что такой подход снижает эффективность работы некоторых компонентов STL. Чтобы избежать снижения быстродействия. Комитет по стандартизации C++ включил в Стандарт положение, которое практически выхолостило объектные распределители памяти, но одновременно выражало надежду, что от этой операции их потенциальные возможности не пострадают.

    Но это еще не все. Распределители памяти STL, как и

    operator new
    с
    operator new[]
    , отвечают за выделение (и освобождение) физической памяти, однако их клиентский интерфейс имеет мало общего с клиентским интерфейсом
    operator new
    ,
    operator new[]
    и даже
    malloc
    . Наконец, большинство стандартных контейнеров никогда не запрашивает память у своих распределителей. Еще раз подчеркиваю — никогда. В результате распределители производят довольно странное впечатление.

    Впрочем, это не их вина, и, конечно же, из этого факта вовсе не следует делать вывод о бесполезности распределителей. Тем не менее, прежде чем описывать области применения распределителей (эта тема рассматривается в совете 11), я должен объяснить, для чего они не подходят. Существует целый ряд задач, которые только на первый взгляд могут решаться при помощи распределителей. Прежде чем вступать в игру, желательно изучить границы игрового поля, в противном случае вы наверняка упадете и получите травму. Кроме того, из-за экзотических особенностей распределителей сам процесс обобщения выглядит весьма поучительным и занимательным. По крайней мере, я на это надеюсь.

    Перечень особенностей распределителей начинается с рудиментарных определений типов для указателей и ссылок. Как упоминалось выше, распределители изначально были задуманы как абстракции для моделей памяти, поэтому казалось вполне логичным возложить на них обеспечение определения типов (

    typedef
    ) для указателей и ссылок в определяемой модели. В стандарте C++ стандартный распределитель объектов типа
    T
    (
    allocator<T>
    ) предоставляет определения
    allocator<T>::pointer
    и
    allocator<T>::reference
    , поэтому предполагается, что пользовательские распределители также будут предоставлять эти определения.

    Ветераны C++ немедленно почуют неладное, поскольку в C++ не существует средств для имитации ссылок. Для этого пришлось бы перегрузить

    operator.
    (оператор «точка»), а это запрещено. Кроме того, объекты, работающие как ссылки, являются примером промежуточных объектов (proxy objects), а использование промежуточных объектов приводит к целому ряду проблем, одна из которых описана в совете 18. Подробное описание промежуточных объектов приведено в совете 30 книги «More Effective C++».

    В случае распределителей STL бессмысленность определений типов для указателей и ссылок объясняется не техническими недостатками промежуточных объектов, а следующим фактом: Стандарт разрешает считать, что определение типа

    pointer
    любого распределителя является синонимом
    T*
    , а определение типа
    reference
    — синонимом
    T&
    . Да, все верно, разработчики библиотек могут игнорировать определения и использовать указатели и ссылки напрямую! Таким образом, даже если вам удастся написать распределитель с новыми определениями для указателей и ссылок, никакой пользы от этого не будет, поскольку используемая реализация STL запросто сможет эти определения проигнорировать. Интересно, не правда ли?

    Пока вы не успели осмыслить этот пример странностей стандартизации, я приведу следующий. Распределители являются объектами, из чего следует, что они могут обладать собственными функциями, вложенными типами и определениями типов (такими как

    pointer
    и
    reference
    ). Однако в соответствии со Стандартом реализация STL может предполагать, что все однотипные объекты распределителей эквивалентны и почти всегда равны. Разумеется, это обстоятельство объяснялось вескими причинами. Рассмотрим следующий фрагмент:

    template<typename T> // Шаблон пользовательского

                         // распределителя памяти

    class SpecialAllocator{...};

    typedef SpecialAllocator<Widget> SAW; // SAW = "SpecialAllocator

                                          //for Widgets"

    list<Widget.SAW> L1;

    list<Widget.SAW> L2;

    L1.splice(L1.begin(), L2);

    Вспомните: при перемещении элементов из одного контейнера

    list
    в другой функцией
    splice
    данные не копируются. Стоит изменить значения нескольких указателей, и узлы, которые раньше находились в одном списке, оказываются в другом, поэтому операция врезки выполняется быстро и защищена от исключений. В приведенном примере узлы, ранее находившиеся в
    L2
    , после вызова
    splice
    перемещаются в
    L1
    .

    Разумеется, при уничтожении контейнера

    L1
    должны быть уничтожены все его узлы (с освобождением занимаемой ими памяти). А поскольку контейнер теперь содержит узлы, ранее входившие в
    L2
    , распределитель памяти
    L1
    должен освободить память, ранее выделенную распределителем
    L2
    . Становится ясно, почему Стандарт разрешает программистам STL допускать эквивалентность однотипных распределителей. Это сделано для того, чтобы память, выделенная одним объектом-распределителем (таким как
    L2
    ), могла безопасно освобождаться другим объектом-распределителем (таким как L1). Отсутствие подобного допущения привое бы к значительному усложнению реализации врезки и к снижению ее эффективности (кстати, операции врезки влияют и на другие компоненты STL, один из примеров приведен в совете 4).

    Все это, конечно, хорошо, но чем больше размышляешь на эту тему, тем лучше понимаешь, какие жесткие ограничения накладывает предположение об эквивалентности однотипных распределителей. Из него следует, что переносимые объекты распределителей — то есть распределители памяти, правильно работающие в разных реализациях STL, — не могут обладать состоянием. Другими совами, это означает, что переносимые распределители не могут содержать нестатических переменных (по крайней мере таких, которые бы влияли на их работу). В частности, отсюда следует, что вы не сможете создать два распределителя

    SpecialAllocator<int>
    , выделяющих память из разных куч (heap). Такие распределители не были бы эквивалентными, и в некоторых реализациях STL попытки использования обоих распределителей привели бы к порче структур данных во время выполнения программы.

    Обратите внимание: эта проблема возникает на стадии выполнения. Распределители, обладающие состоянием, компилируются вполне нормально — просто они не работают так, как предполагалось. За эквивалентностью всех однотипных распределителей вы должны следить сами. Не рассчитывайте на то, что компилятор предупредит о нарушении этого ограничения.

    Справедливости ради стоит отметить, что сразу же за положением об эквивалентности однотипных распределителей памяти в Стандарт включен следующий текст: «…Авторам реализаций рекомендуется создавать библиотеки, которые… поддерживают неэквивалентные распределители. В таких реализациях… семантика контейнеров и алгоритмов для неэквивалентных экземпляров распределителей определяется самой реализацией».

    Трогательное проявление заботы, однако пользователю STL, рассматривающему возможность создания нестандартного распределителя с состоянием, это не дает практически ничего. Этим положением можно воспользоваться только в том случае, если вы уверены в том, что используемая реализация STL поддерживает неэквивалентные распределители, готовы потратить время на углубленное изучение документации, чтобы узнать, подходит ли вам «определяемое самой реализацией» поведение неэквивалентных распределителей, и вас не беспокоят проблемы с переносом кода в реализации STL, в которых эта возможность может отсутствовать. Короче говоря, это положение (для особо любознательных — абзац 5 раздела 20.1.5) лишь выражает некие благие намерения по поводу будущего распределителей. До тех пор пока эти благие намерения не воплотятся в жизнь, программисты, желающие обеспечить переносимость своих программ, должны ограничиваться распределителями без состояния.

    Выше уже говорилось о том, что распределители обладают определенным сходством с оператором

    new
    — они тоже занимаются выделением физической памяти, но имеют другой интерфейс. Чтобы убедиться в этом, достаточно рассмотреть объявления стандартных форм
    operator new
    и
    allocator<T>::allocate
    :

    void* operator new(size_t bytes);

    pointer allocator<T>::allocate(size_type numObjects);

    // Напоминаю: pointer - определение типа.

    //практически всегда эквивалентное T*

    В обоих случаях передается параметр, определяющий объем выделяемой памяти, но в случае с оператором

    new
    указывается конкретный объем в байтах, а в случае с
    allocator<T>::allocate
    указывается количество объектов
    T
    , размещаемых в памяти. Например, на платформе, где
    sizeof (int)==4
    , при выделении памяти для одного числа
    int
    оператору
    new
    передается число 4, а
    allocator<int>::allocate
    — число 1. Для оператора
    new
    параметр относится к типу
    size_t
    , а для функции
    allocate
    — к типу
    allocator<T>::size_type
    , В обоих случаях это целочисленная величина без знака, причем
    allocator<T>::size_type
    обычно является простым определением типа для
    size_t
    . В этом несоответствии нет ничего страшного, однако разные правила передачи параметров оператору
    new
    и
    allocator<T>::allocate
    усложняют использование готовых пользовательских версий new в разработке нестандартных распределителей.

    Оператор new отличается от

    allocator<T>::allocate
    и типом возвращаемого значения. Оператор
    new
    возвращает
    void*
    , традиционный способ представления указателя на неинициализированную память в C++. Функция
    allocator<T>::allocate
    возвращает
    T*
    (через определение типа
    pointer
    ), что не только нетрадиционно, но и отдает мошенничеством. Указатель, возвращаемый
    allocator<T>::allocate
    , не может указывать на объект
    T
    , поскольку этот объект еще не был сконструирован! STL косвенно предполагает, что сторона, вызывающая
    allocator<T>::allocate
    , сконструирует в полученной памяти один или несколько объектов
    T
    (вероятно, посредством
    allocator<T>::construct
    ,
    uninitialized_fill
    или
    raw_storage_iterator
    ), хотя в случае
    vector::reseve
    или
    string::reseve
    этого может никогда не произойти (совет 13). Различия в типах возвращаемых значений оператора
    new
    и
    allocator<T>::allocate
    означают изменение концептуальной модели неинициализированной памяти, что также затрудняет применение опыта реализации оператора
    new
    к разработке нестандартных распределителей.

    Мы подошли к последней странности распределителей памяти в STL: большинство стандартных контейнеров никогда не вызывает распределителей, с которыми они ассоциируются. Два примера:

    list<int> L; // То же, что и list<int, allocator<int».

                 // Контейнер никогда не вызывает

                 // allocator<int> для выделения памяти!

    set<Widget.SAW> s;// SAW представляет собой определение типа

                      // для SpeciаlAllосаtor<Widget>, однако

                      // ни один экземпляр SAW не будет

                      // выделять память!

    Данная странность присуща

    list
    и стандартным ассоциативным контейнерам (
    set
    ,
    multiset
    ,
    map
    и
    multimap
    ). Это объясняется тем, что перечисленные контейнеры являются узловыми, то есть основаны на структурах данных, в которых каждый новый элемент размещается в динамически выделяемом отдельном узле. В контейнере
    list
    узлы соответствуют узлам списка. В стандартных ассоциативных контейнерах узлы часто соответствуют узлам дерева, поскольку стандартные ассоциативные контейнеры обычно реализуются в виде сбалансированных бинарных деревьев.

    Давайте подумаем, как может выглядеть типичная реализация

    list<T>
    . Список состоит из узлов, каждый из которых содержит объект
    T
    и два указателя (на следующий и предыдущий узлы списка).

    template<typename T>,           // Возможная реализация

    typename Allocator=allocator<T> // списка

    class list {

    private:

     Allocator alloc;// Распределитель памяти для объектов типа T

     struct ListNode{// Узлы связанного списка

      T data;

      ListNode *prev;

      ListNode *next;

     };

     …

    };

    При включении в список нового узла необходимо получить для него память от распределителя, однако нам нужна память не для

    T
    , а для структуры
    ListNode
    , содержащей
    T
    . Таким образом, объект
    Allocator
    становится практически бесполезным, потому что он выделяет память не для
    ListNode
    , а для
    T
    . Теперь становится понятно, почему
    list
    никогда не обращается к
    Allocator
    за памятью — последний просто не способен предоставить то, что требуется
    list
    .

    Следовательно,

    list
    нужны средства для перехода от имеющегося типа распределителя к соответствующему распределителю
    ListNode
    . Задача была бы весьма непростой, но по правилам распределитель памяти должен предоставить определение типа для решения этой задачи. Определение называется
    other
    , но не все так просто — это определение вложено в структуру с именем
    rebind
    , которая сама по себе является шаблоном, вложенным в распределитель, — причем последний тоже является шаблоном!

    Пожалуйста, не пытайтесь вникать в смысл последней фразы. Вместо этого просто рассмотрите следующий фрагмент и переходите к дальнейшему объяснению:

    template<typename T>

    class allocator {

    public:

     template<typename U>

     struct rebind{

      typedef allocator<U> other;

     };

     …

    }

    В программе, реализующей

    list<T>
    , возникает необходимость определить тип распределителя
    ListNode
    , соответствующего распределителю, существующему для
    T
    . Тип распределителя для
    T
    задается параметром
    allocator
    . Учитывая сказанное, тип распределителя для
    ListNode
    должен выглядеть так:

    Allocator::rebind<ListNode>::other

    А теперь будьте внимательны. Каждый шаблон распределителя 

    A
    (например,
    std::allocator, SpecialAllocator
    и т. д.) должен содержать вложенный шаблон структуры с именем
    rebind
    . Предполагается, что
    rebind
    получает параметр
    U
    и не определяет ничего, кроме определения типа
    other
    , где
    other
    — просто имя для
    A<U>
    . В результате
    list<T>
    может перейти от своего распределителя объектов
    T(Allocator)
    к распределителю объектов
    ListNode
    по ссылке
    Allocator::rebind<ListNode>::other.

    Может, вы разобрались во всем сказанном, а может, и нет (если думать достаточно долго, вы непременно разберетесь, но подумать придется — знаю по своему опыту). Но вам как пользователю STL, желающему написать собственный распределитель памяти, в действительности не нужно точно понимать суть происходящего. Достаточно знать простой факт: если вы собираетесь создать распределитель памяти и использовать его со стандартными контейнерами, ваш распределитель должен предоставлять шаблон

    rebind
    , поскольку стандартные шаблоны будут на это рассчитывать (для целей отладки также желательно понимать, почему узловые контейнеры
    T
    никогда не запрашивают память у распределителей объектов
    T
    ).

    Ура! Наше знакомство со странностями распределителей памяти закончено. Позвольте подвести краткий итог того, о чем необходимо помнить при программировании собственных распределителей памяти:

    • распределитель памяти оформляется в виде шаблона с параметром

    T
    , представляющим тип объектов, для которых выделяется память;

    • предоставьте определения типов

    pointer
    и
    reference
    , но следите за тем, чтобы pointer всегда был эквивалентен
    T*
    , а
    reference
    —
    T&
    ;

    • никогда не включайте в распределители данные состояния уровня объекта. В общем случае распределитель не может содержать нестатических переменных;

    • помните, что функциям

    allocate
    передается количество объектов, для которых необходимо выделить память, а не объем памяти в байтах. Также помните, что эти функции возвращают указатели
    T*
    (через определение типа
    pointer
    ) несмотря на то, что ни один объект
    T
    еще не сконструирован;

    • обязательно предоставьте вложенный шаблон

    rebind
    , от наличия которого зависит работа стандартных контейнеров.

    Написание собственного распределителя памяти обычно сводится к копированию приличного объема стандартного кода и последующей модификации нескольких функций (в первую очередь

    allocate
    и
    deallocate
    ). Вместо того чтобы писать базовый код с самого начала, я рекомендую воспользоваться кодом с web-страницы Джосаттиса [23] или из статьи Остерна «What Are Allocators Good For?» [24].

    Материал, изложенный в этом совете, дает представление о том, чего не могут сделать распределители памяти, но вас, вероятно, больше интересует другой вопрос — что они могут? Это весьма обширная тема, которую я выделил в совет 11.

    Совет 11. Учитывайте область применения пользовательских распределителей памяти

    Итак, в результате хронометража, профилирования и всевозможных экспериментов вы пришли к выводу, что стандартный распределитель памяти STL (то есть

    allocator<T>
    ) работает слишком медленно, напрасно расходует или фрагментирует память, и вы лучше справитесь с этой задачей. А может быть,
    allocator<T>
    обеспечивает безопасность в многопоточной модели, но вы планируете использовать только однопоточную модель и не желаете расходовать ресурсы на синхронизацию, которая вам не нужна. Или вы знаете, что объекты некоторых контейнеров обычно используются вместе, и хотите расположить их рядом друг с другом в специальной куче, чтобы по возможности локализовать ссылки. Или вы хотите выделить блок общей памяти и разместить в нем свои контейнеры, чтобы они могли использоваться другими процессами. Превосходно! В каждом из этих сценариев уместно воспользоваться нестандартным распределителем памяти.

    Предположим, у вас имеются специальные функции для управления блоком общей памяти, написанные по образцу

    malloc
    и
    free
    :

    void* mallocShared(size_t bytesNeeded);

    void freeShared(void *ptr);

    Требуется, чтобы память для содержимого контейнеров STL выделялась в общем блоке. Никаких проблем:

    template<typename T>

    class SharedMemoryAllocator {

    public:

     …

     pointer allocate(size_type numObjects, const void* localityHint=0) {

      return static_cast<pointer>(mal1ocShared(numObjects *szeof(T)));

     }

     void deallocate(pointer ptrToMemory, size_type numObjects) {

      freeShared(ptrToMemory);

     }

     …

    };

    За информацией о типе pointer, а также о преобразовании типа и умножении при вызове allocate обращайтесь к совету 10. Пример использования

    SharedMemoryAllocator
    :

    // Вспомогательное определение типа

    typedef

    vector<double, SharedMemoryAllocator<double> > SharedDoubleVec;

    …

    { // Начало блока

     SharedDoubleVec v;// Создать вектор, элементы которого

     …                 // находятся в общей памяти

    } // Конец блока

    Обратите особое внимание на формулировку комментария рядом с определением

    v
    . Вектор
    v
    использует
    SharedMemoryAllocator
    , потому память для хранения элементов
    v
    будет выделяться из общей памяти, однако сам вектор
    v
    (вместе со всеми переменными класса) почти наверняка не будет находиться в общей памяти. Вектор
    v
    — обычный стековый объект, поэтому он будет находиться в памяти, в которой исполнительная система хранит все обычные стековые объекты. Такая память почти никогда не является общей. Чтобы разместить в общей памяти как содержимое
    v
    , так и сам объект
    v
    , следует поступить примерно так:

    void *pVectorMemory =                   // Выделить блок общей памяти,

     mallocShared(sizeof(SharedOoubleVec)); // обьем которой достаточен

                                            // для хранения объекта SharedDoubleVec

    SharedDoubleVec *pv =                 // Использовать "new с явным

     new (pVectorMemory) SharedDoubleVec; // размещением" для создания

                                          // объекта SharedDoubleVec:

                                          // см. далее.

    … // Использование объекта (через pv)

    pv->~SharedDoubleVec(); // Уничтожить объект в общей памяти

    freeShared(pVectorMemory); // Освободить исходный блок

                               // общей памяти

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

    vector
    , использующий общую память для своих внутренних операций. После завершения работы с вектором мы вызываем его деструктор и освобождаем память, занимаемую вектором. Код не так уж сложен, но все-таки он не сводится к простому объявлению локальной переменной, как прежде. Если у вас нет веских причин для того, чтобы в общей памяти находился сам контейнер (а не его элементы), я рекомендую избегать четырехшагового процесса «выделение/конструирование/уничтожение/освобождение».

    Несомненно, вы заметили: в приведенном фрагменте проигнорирована возможность того, что

    mallocShared
    может вернуть
    null
    . Разумеется, в окончательной версии следовало бы учесть такую возможность. Кроме того, конструирование vector в общей памяти производится конструкцией «
    new
    с явным размещением», описанной в любом учебнике по C++.

    Рассмотрим другой пример использования распределителей памяти. Предположим, у нас имеются две кучи, представленные классами

    Heap1
    и
    Неар2
    . Каждый из этих классов содержит статические функции для выделения и освобождения памяти:

    class Heap1 {

    public:

     …

     static void* alloc(size t numBytes, const void* memoryBlockToBeNear);

     static void dealloc(void *ptr);

     …

    };

    class Heap2 {…}; // Тот же интерфейс alloc/dealloc

    Далее предположим, что вы хотите разместить содержимое контейнеров STL в заданных кучах. Сначала следует написать распределитель, способный использовать классы

    Heap1
    и
    Heap2
    при управлении памятью:

    template<typename T, typename Heap>

    SpecificHeapAllocator{

    public:

     …

     pointer allocate(size_type numObjects,const void *localityHint=0) {

      return static_cast<pointer>(Heap::alloc(numObjects*sizeof(T), localityHint));

     }

     void deallocate(pointer ptrToMemory, size_type numObjects) {

      Heap::dealloc(ptrToMemory);

     }

     …

    };

    Затем

    SpecialHeapAllocator
    группирует элементы контейнеров:

    vector<int, SpecificHeapAllocator<int, Heap1> > v; // Разместить элементы

    set<int, SpecificHeapAllocator<int, Heap1> > s; // v и s в Heapl


    list<Widget,

     SpecificHeapAllocator<Widget, Heap2> > L; // Разместить элементы

    map<int, string, less<int>,                // L и m в Heap2

    SpecificHeapAllocator<pair<const int, string>, Heap2> > m;

    В приведенном примере очень важно, чтобы

    Heap1
    и
    Неар2
    были типами, а не объектами. В STL предусмотрен синтаксис инициализации разных контейнеров STL разными объектами распределителей одного типа, но я не буду его приводить. Дело в том, что если бы
    Heap1
    и
    Неар2
    были бы объектами вместо типов, это привело бы к нарушению ограничения эквивалентности, подробно описанного в совете 10.

    Как показывают приведенные примеры, распределители приносят пользу во многих ситуациях. При соблюдении ограничения об эквивалентности однотипных распределителей у вас не будет проблем с применением нестандартных распределителей для управления памятью, группировки, а также использования общей памяти и других специализированных пулов.

    Совет 12. Разумно оценивайте потоковую безопасность контейнеров STL

    Мир стандартного C++ выглядит старомодным и не подверженным веяниям времени. В этом мире все исполняемые файлы компонуются статически, в нем нет ни файлов, отображаемых на память, ни общей памяти. В нем нет графических оконных систем, сетей и баз данных, нет и других процессов. Вероятно, не стоит удивляться тому, что в Стандарте не сказано ни слова о программных потоках. О потоковой безопасности в STL можно уверенно сказать только одно: что она полностью зависит от реализации.

    Конечно, многопоточные программы распространены весьма широко, поэтому большинство разработчиков STL стремится к тому, чтобы их реализации хорошо работали в многопоточных условиях. Но даже если они хорошо справятся со своей задачей, основное бремя остается на ваших плечах. Возможности разработчиков STL в этой области ограничены, и вы должны хорошо понимать, где проходят эти границы.

    «Золотой стандарт» поддержки многопоточности в контейнерах STL (которым руководствуется большинство разработчиков) был определен компанией SGI и опубликован на ее web-сайте, посвященном STL [21]. Фактически в нем сказано, что в лучшем случае можно надеяться на следующее:

    • безопасность параллельного чтения. Несколько потоков могут одновременно читать содержимое контейнера, и это не помешает его правильной работе. Естественно, запись в контейнер при этом не допускается;

    • безопасность записи в разные контейнеры. Несколько потоков могут одновременно производить запись в разные контейнеры.

    Обращаю ваше внимание: это то, на что вы можете надеяться, но не рассчитывать. Одни реализации предоставляют такие гарантии, другие — нет.

    Многопоточное программирование считается сложной задачей, и многие программисты желают, чтобы реализации STL изначально обеспечивали полную потоковую безопасность. Это избавило бы их от необходимости самостоятельно синхронизировать доступ. Конечно, это было бы очень удобно, однако добиться этой цели очень сложно. Рассмотрим несколько способов реализации полной потоковой безопасности контейнеров:

    • блокировка контейнера на время вызова любой функции;

    • блокировка контейнера в течение жизненного цикла каждого возвращаемого итератора (например посредством вызова

    begin
    или
    end
    );

    • блокировка контейнера на протяжении работы каждого алгоритма, вызванного для этого контейнера. В действительности это бессмысленно, поскольку, как будет показано в совете 32, алгоритм не располагает средствами идентификации контейнера, с которым он работает. Тем не менее, мы изучим этот вариант — будет поучительно увидеть, почему он в принципе неработоспособен.

    Рассмотрим следующий фрагмент, который ищет в

    vector<int>
    первое вхождение числа 5 и заменяет его нулем:

    vector<int> v;

    …

    vector<int>::iterator first5(find(v.begin(), v.end(), 5)); // Строка 1

    if (first5 != v.end()) { // Строка 2

     *first5 = 0; // Строка 3

    }

    В многопоточной среде существует вероятность того, что другой поток изменит содержимое

    v
    сразу же после выполнения строки 1. Если это произойдет, сравнение
    first5
    с
    v.end
    в строке 2 становится бессмысленным, поскольку содержимое
    v
    будет не тем, каким оно было в конце строки 1. Более того, такая проверка может привести к непредсказуемым результатам, поскольку третий поток может перехватить управление между строками 1 и 2 и сделать
    first5
    недействительным (например, при выполнении вставки вектор может заново выделить память, вследствие чего все итераторы данного вектора станут недействительными. За подробностями о перераспределении памяти обращайтесь к совету 14). Присваивание
    *first5
    в строке 3 тоже небезопасно, поскольку между строками 2 и 3 другой поток может удалить элемент, на который указывает (или, по крайней мере, указывал раньше) итератор
    first5
    .

    Ни одно из описанных выше решений с блокировкой не решает этих проблем. Вызовы

    begin
    и
    end
    в строке 1 сразу возвращают управление, сгенерированные ими итераторы остаются действительными только до конца строки, а
    find
    тоже возвращает управление в конце строки.

    Чтобы этот фрагмент был потоково-безопасным, блокировка

    v
    должна сохраняться от строки 1 до строки 3. Трудно представить, каким образом реализация STL могла бы автоматически придти к такому выводу. А если учесть, что использование примитивов синхронизации (семафоров, мьютексов[1] и т. д.) обычно сопряжено с относительно высокими затратами, еще труднее представить, каким образом реализация могла бы сделать это без значительного снижения быстродействия по сравнению с программами, которым априорно известно, что в строках 1-3 с
    v
    будет работать только один программный поток.

    Понятно, почему в решении проблем многопоточности не стоит полагаться на реализацию STL. Вместо этого в подобных случаях следует самостоятельно синхронизировать доступ. В приведенном примере это может выглядеть так:

    vector<int> v;

    …

    getMutexFor(v);

    vector<int>::iterator first5(find(v.begin(), v.end(), 5));

    if (first5 != v.end()) {// Теперь эта строка безопасна

     *first5 = 0; // И эта строка тоже

    }

    releaseMutexFor(v);

    В другом, объектно-ориентированном, решении создается класс

    Lock
    , который захватывает мьютекс в конструкторе и освобождает его в деструкторе, что сводит к минимуму вероятность вызова
    getMutexFor
    без парного вызова
    releaseMutexFor
    . Основа такого класса (точнее, шаблона) выглядит примерно так:

    template<typename Container> // Базовый шаблон для классов,

    class Lock{ // захватывающих и освобождающих мьютексы

    public:// для контейнеров: многие технические

           // детали опущены

     Lock(const Containers container) : c(container) {

      getMutexFor(с);// Захват мьютекса в конструкторе

     }

     ~Lock () {

      releaseMutexFor(c); // Освобождение мьютекса в деструкторе

     }

    private:

     const Container& с;

    Концепция управления жизненным циклом ресурсов (в данном случае — мьютексов) при помощи специализированных классов вроде

    Lock
    рассматривается в любом серьезном учебнике C++. Попробуйте начать с книги Страуструпа (Stroustrup) «The C++ Programming Language» [7], поскольку именно Страуструп популяризировал эту идиому, однако информацию также можно найти в совете 9 «More Effective C++». Каким бы источником вы ни воспользовались, помните, что приведенный выше класс
    Lock
    урезан до абсолютного минимума. Полноценная версия содержала бы многочисленные дополнения, не имеющие никакого отношения к STL. Впрочем, несмотря на минимализм, приведенная версия
    Lock
    вполне может использоваться в рассматриваемом примере:

    vector<int> v;

    …

    { // Создание нового блока

     Lock<vector<int> > lock(v); // Получение мьютекса

     vector<int>::iterator first5(find(v.begin(), v.end(), 5));

     if (first5 != v.end()) {

      *first5 = 0;

     }

    } // Закрытие блока с автоматическим

      // освобождением мьютекса

    Поскольку мьютекс контейнера освобождается в деструкторе

    Lock
    , важно обеспечить уничтожение
    Lock
    сразу же после освобождения мьютекса. Для этого мы создаем новый блок, в котором определяется объект
    Lock
    , и закрываем его, как только надобность в мьютексе отпадает. На первый взгляд кажется, что вызов
    releaseMutexFor
    попросту заменен необходимостью закрыть блок, но это не совсем так. Если мы забудем создать новый блок для
    Lock
    , мьютекс все равно будет освобожден, но это может произойти позднее положенного момента — при выходе из внешнего блока. Если забыть о вызове
    releaseMutexFor
    , мьютекс вообще не освобождается.

    Более того, решение, основанное на классе

    Lock
    , лучше защищено от исключений. C++ гарантирует уничтожение локальных объектов при возникновении исключения, поэтому
    Lock
    освободит мьютекс, даже если исключение произойдет при использовании объекта
    Lock
    . При использовании парных вызовов
    getMutexFor/releaseMutexFor
    мьютекс не будет освобожден, если исключение происходит после вызова
    getMutexFor
    , но перед вызовом
    releaseMutexFor
    .

    Исключения и управление ресурсами важны, но данный совет посвящен другой теме — потоковой безопасности в STL. Как говорилось выше, вы можете надеятьсяна то, что реализация библиотеки обеспечивает параллельное чтение из одного контейнера и одновременную запись в разные контейнеры. Не надейтесь, что библиотека избавит вас от ручной синхронизации и не рассчитывайте на поддержку многопоточности.

    Примечания:



    1

    В среде программистов данный термин (англ. mutex) встречается также в варианте «мутекс». — Примеч. ред.

    Главная | Контакты | Нашёл ошибку | Прислать материал | Добавить в избранное

    Все материалы представлены для ознакомления и принадлежат их авторам.