контейнеры — Вставка и удаление из последовательностей Переполнение стека
Я прочитал это в книге и точно вставил текст. Я сделал скриншот, но репутации не хватает, так что …
Последовательности
Вы можете уточнить основную концепцию контейнера, добавив требования.
последовательность является важным уточнением, потому что некоторые из STL
типы контейнеров — deque, forward_list (C ++ 11), список, очередь,
priority_queue, stack и vector — это последовательности. (Напомним, что очередь
позволяет добавлять элементы сзади и снимать с
front.A двусторонняя очередь, представленная deque, позволяет добавлять и
удаление на обоих концах.) Требование, чтобы итератор был как минимум
прямой итератор гарантирует, что элементы расположены в
определенный порядок, который не меняется от одного цикла итерации к
следующий. Класс массива также классифицируется как контейнер последовательности,
хотя он не удовлетворяет всем требованиям. Последовательность также
требует, чтобы его элементы были расположены в строгом линейном порядке.
есть первый элемент, есть последний элемент, и каждый элемент
но первый и последний имеет ровно один элемент перед ним
и один элемент сразу после него. Массив и связанный список
примеры последовательностей, тогда как ветвящаяся структура (в которой каждый
узел указывает на два дочерних узла) нет.Поскольку элементы в последовательности имеют определенный порядок, такие операции, как
вставка значений в определенном месте и стирание определенного
Диапазон становится возможным. В таблице 16.7 перечислены эти и другие операции.
требуется для последовательности. В таблице используются те же обозначения, что и в таблице.
16.5, с добавлением t, представляющего значение типа T, то есть тип значения, хранящегося в контейнере, n, целое число и p,
q, i и j, представляющие итераторы.
В начале второго абзаца говорится, что последовательности имеют определенный порядок сохранения, поэтому вставка и удаление элементов возможный. Разве это не разрушает все о поддержании определенного порядка? Пожалуйста помоги. Это сводит меня с ума. Благодарю.
Решение
Некоторые контейнеры заказаны, некоторые отсортированы, некоторые оба, некоторые нет. Например:
std::list а также std::vector являются приказал, но не отсортировано (если вы не выходите из своего пути, чтобы сделать это).
std::map а также std::set оба отсортированный а также приказал.
std::unordered_map а также std::unordered_set являются неупорядоченный а также несортированный (это хеш-карты в основном)
Функции вставки, удаления, push, pop и т. Д. Учитывают эти требования к контейнерам. Для отсортированных контейнеров вставка должна гарантировать, что элемент вставлен в правильном положении, а остальные элементы отрегулированы по мере необходимости.
Последовательность должна быть упорядочена, но не обязательно отсортирована.
Поэтому, когда вы говорите, что хотите вставить элемент e по указателю iЭта концепция имеет смысл только для заказанных контейнеров, потому что неупорядоченные контейнеры не имеют понятия индексов или позиций.
Одна вещь, с которой вы должны быть осторожны (среди прочего), это то, что если у вас есть итератор для контейнера, часто изменение контейнера (вставка, удаление и т. Д.) Может привести к аннулированию этого итератора, что вызывает стереть-удалить идиому
Вот (неполная) диаграмма, которая показывает свойства различных контейнеров стандартной библиотеки C ++.
создано Дэвид Мур а также лицензированный CC BY-SA 3.0
Другие решения
Вставка элементов в последовательности требует в качестве аргумента положение, в которое вы хотите поместить его (то же самое для стирания),
Для того чтобыith позиция «имеет смысл, должен быть порядок
Не надо путать упорядоченные с отсортированными … для сортировки нам нужен компаратор, упорядоченный также может означать индексированный (я думаю)
последовательность: 4 5 2 упорядочен, сначала идет 4, затем 5, затем 2
и последовательность 5 2 4 также упорядочена