Герб Саттер - Стандарты программирования на С++. 101 правило и рекомендация

[BoostLRG] • [Stroustrup00] §14.1, §14.6 • [Sutter04] §13

Мы знаем, что вы уже предпочитаете использовать стандартные контейнеры вместо написанных вручную. Но какой именно контейнер следует использовать? Что должно (и что не должно) храниться в контейнерах и почему? Как следует заполнять контейнеры? Какие важные идиомы надо знать?

В этом разделе имеются ответы на все перечисленные (и не только) вопросы. И не случайно, что три первые рекомендации в нем содержат слова "Используйте vector...".

В этом разделе мы считаем наиболее значимой рекомендацию 79 — "Храните в контейнерах только значения или интеллектуальные указатели". К ней мы добавим — если даже вы не планируете применять [Boost] и [C++TR104] для иных целей, все равно воспользуйтесь их интеллектуальным указателем shared_ptr.

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

Если конкретных предпочтений нет, возьмите vectorи спокойно работайте, зная, что вы сделали верный выбор.

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

• Следует писать в первую очередь корректный, простой и понятный код (см. рекомендацию 6). Предпочтителен выбор контейнера, который позволит вам написать наиболее понятный код. Так, если вам требуется вставка в определенную позицию, используйте последовательный контейнер (например, vector, list). Если вам нужен итератор произвольного доступа, выберите vector, dequeили string. Если нужен словарный поиск наподобие c[0]=42;, воспользуйтесь ассоциативным контейнером (например, set, map) — но если вам требуется упорядоченная ассоциативная коллекция, то вы не можете использовать контейнеры с использованием хеширования (нестандартные hash_… или стандартные unordered_… контейнеры).

• Вопросы эффективности при написании должны учитываться только тогда и там, где это действительно необходимо (см. рекомендацию 8). Если на основании проведенных измерений с реальными данными доказано, что скорость поиска действительно критична, можно воспользоваться контейнерами с использованием хеширования (нестандартными hash_… или стандартными unordered_… контейнерами), затем — отсортированным vector, затем — setили map, обычно в приведенном порядке. Даже в этой ситуации отличия асимптотического времени работы (с использованием "большого O ", например, линейное и логарифмическое время работы; см. рекомендацию 7) имеет значение, только если контейнеры достаточно велики, чтобы постоянные множители перестали играть роль. Для контейнеров, содержащих небольшие объекты наподобие double, для преодоления влияния постоянных множителей обычно требуется по крайней мере несколько тысяч элементов.

• Там, где это возможно и разумно, лучше писать транзакционный код со строгой гарантией безопасности код (см. рекомендацию 71), и не использовать некорректные объекты (см. рекомендацию 99). Если для вставки и удаления элементов вам требуется транзакционная семантика, или если необходимо минимизировать недействительность итераторов, лучше воспользоваться контейнерами на основе узлов (например, list, set, map).

В противном случае следуйте совету Стандарта: " vectorпредставляет собой тип последовательности, который нужно использовать по умолчанию" ([C++03] §23.1.1).

Если вы сомневаетесь в данном совете, спросите сами себя — действительно ли у вас есть непреодолимые причины не использовать стандартный контейнер vector, который обладает следующими свойствами.

• Гарантирует минимальные среди всех контейнеров накладные расходы памяти на хранение (ноль байтов на объект).

• Гарантирует наивысшую среди всех контейнеров скорость доступа к хранимым элементам.

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