Последовательные контейнеры поддерживают указанный пользователем порядок вставляемых элементов.
Контейнер vector ведет себя как массив, но может автоматически увеличиваться по мере необходимости. Он поддерживает прямой доступ и связанное хранение и имеет очень гибкую длину. По этим и многим другим причинам контейнер vector является наиболее предпочтительным последовательным контейнером для большинства областей применения. Если вы сомневаетесь в выборе вида последовательного контейнера, начните с использования вектора.
Ассоциативные контейнеры
В ассоциативных контейнерах элементы вставляются в предварительно определенном порядке — например, с сортировкой по возрастанию.
Контейнер map, который часто называют словарем, хранит в узлах пару "ключ-значение". Ключ является уникальным и используется для упорядочивания последовательности, а значение связано с ключом. Например, map может содержать ключи, представляющие заголовки столбцов в таблице, и соответствующие значения, которые описывает тип данных в столбце и их максимальный размер в байтах.
Для map перегружена операция индексации. Она использует ключ в качестве индекса, а возвращает значение (адрес объекта). Поэтому её можно использовать как в правой, так и в левой части оператора присваивания, как в обыкновенном массиве.
Для хранения данных в контейнерах map обычно используется бинарное дерево (объект класса tree).
Бинарное дерево — это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве размещаются узлы с ключами, имеющими значения, меньшие, чем значение ключа данного узла, а в правом поддереве размещаются узлы с ключами, имеющими значения, большие, чем значение ключа данного узла.
При создании дерева создается один пустой узел, который будет корнем дерева.
Элементы добавляются в дерево согласно приведенному выше правилу.
Запишем в бинарное дерево элементы массива
int arr[]={7, 3, 11, 1,0, 2, 5, 9, 6, 4, 13, 14, 8, 10, 12};
Мы получим приведенное на рисунке дерево.
2 LnhtbEyPwU7DMBBE70j8g7VIvVGbqE5LiFOVSogzLZfenHhJIuJ1iN02/D3LCW472tHMm3I7+0Fc cIp9IAMPSwUCqQmup9bA+/HlfgMiJkvODoHQwDdG2Fa3N6UtXLjSG14OqRUcQrGwBrqUxkLK2HTo bVyGEYl/H2HyNrGcWukme+VwP8hMqVx62xM3dHbEfYfN5+HsDRxfvZrr1O+RvtZqd3rWOZ20MYu7 efcEIuGc/szwi8/oUDFTHc7kohgM6JVi9MRHnoFgg35c5yBqA5tMg6xK+X9B9QMAAP//AwBQSwEC LQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNd LnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8u cmVsc1BLAQItABQABgAIAAAAIQD/DVmG8QEAAOcDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJv RG9jLnhtbFBLAQItABQABgAIAAAAIQADETpU3AAAAAkBAAAPAAAAAAAAAAAAAAAAAEsEAABkcnMv ZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVAUAAAAA " strokecolor="black [3200]" strokeweight=".5pt"> 7
3 11
4 bWxMj8FOwzAMhu9IvENkJG4s6bRlpTSdxiTEmY3Lbmlj2orGKU22lbfHnOBo+9Pv7y+3sx/EBafY BzKQLRQIpCa4nloD78eXhxxETJacHQKhgW+MsK1ub0pbuHClN7wcUis4hGJhDXQpjYWUsenQ27gI IxLfPsLkbeJxaqWb7JXD/SCXSmnpbU/8obMj7jtsPg9nb+D46tVcp36P9LVRu9PzWtNpbcz93bx7 ApFwTn8w/OqzOlTsVIczuSgGA3qVa0YNLDOuwIDeZLyoDawec5BVKf83qH4AAAD//wMAUEsBAi0A FAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVzXS54 bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMvLnJl bHNQSwECLQAUAAYACAAAACEAjXUm8O8BAADpAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uyb0Rv Yy54bWxQSwECLQAUAAYACAAAACEAR7s/atwAAAAJAQAADwAAAAAAAAAAAAAAAABJBAAAZHJzL2Rv d25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFIFAAAAAA== " strokecolor="black [3200]" strokeweight=".5pt"> u eG1sTI/BTsMwEETvSPyDtUjcqN20aUOaTVUqIc60XHpz4iWJGq9D7Lbh7zEnOK72aeZNsZ1sL640 +s4xwnymQBDXznTcIHwcX58yED5oNrp3TAjf5GFb3t8VOjfuxu90PYRGxBD2uUZoQxhyKX3dktV+ 5gbi+Pt0o9UhnmMjzahvMdz2MlFqJa3uODa0eqB9S/X5cLEIxzerpip0e+KvtdqdXtIVn1LEx4dp twERaAp/MPzqR3Uoo1PlLmy86BEW6XoZUYRkHjdFYJElzyAqhGWWgCwL+X9B+QMAAP//AwBQSwEC LQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlwZXNd LnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVscy8u cmVsc1BLAQItABQABgAIAAAAIQD4Aent8AEAAOcDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMvZTJv RG9jLnhtbFBLAQItABQABgAIAAAAIQBhUa593QAAAAkBAAAPAAAAAAAAAAAAAAAAAEoEAABkcnMv ZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVAUAAAAA " strokecolor="black [3200]" strokeweight=".5pt"> 1 5 9 13
0 2 4 6 8 10 12 14
При записи данных в дерево выполняется их сортировка.
Обход дерева выполняется с помощью итератора.