Вставка и удаление из последовательностей C++

Question

Я прочитал это в книге и точно вставляю текст. Я взял скриншот, но не хватает репутации так ...

Sequences

Вы можете уточнить основную концепцию контейнера путем добавления requirements.The последовательность является важным уточнение, потому что некоторые из STL контейнера types- deque, forward_list (C++ 11), список, очередь, sequence_queue, stack и vector-являются последовательностями. (Напомним, что очередь позволяет добавлять элементы на заднем конце и удаляться с фронта . Очередь с двумя концами, представленная deque, позволяет сложение и удаление с обоих концов.) Требование, чтобы итератор был как минимум a Итератор вперед гарантирует, что элементы расположены в определенном порядке, который не меняется от одного цикла итерации до . Класс массива также классифицируется как контейнер последовательности, , хотя он не удовлетворяет всем требованиям. Последовательность также требует, чтобы ее элементы располагались в строгом линейном порядке. То есть есть первый элемент, последний элемент и каждый элемент , но первый и последний имеют ровно один элемент, расположенный непосредственно перед ним и один элемент сразу после него. В массиве и связанном списке есть примеры последовательностей, тогда как структура ветвления (в которой каждый узел указывает на два дочерних узла) не является.

Поскольку элементы в последовательности имеют определенный порядок, такие операции, как вставка значения в определенном месте и стирать определенный диапазон стал possible.Table 16.7 списками этих и других операций, необходимых таблиц sequence.The использует то же самое обозначение как Таблица 16.5, с добавлением t, представляющего значение типа T, то есть тип значения, хранящегося в контейнере, n, целое число и p, q, i и j, представляющие итераторы ,

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

Answer 1

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

std::list и std::vector являются упорядоченный, но не сортируется (если вы не выходите из своего пути, чтобы сделать это).

std::map и std::set оба сортируются и приказал.

std::unordered_map и std::unordered_set являются неупорядоченный и несортированный (они хэш-карты в основном)

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

Последовательность заказывается, но необязательно сортируется.

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

Единственное, что вы должны быть осторожны (в том числе), - это если у вас есть итератор в контейнере, часто изменяющий контейнер (вставка, удаление и т. Д.), Может привести к аннулированию этого итератора, что приводит к таким вещам, как erase-remove idiom

Это (не полная) диаграмма, показывающая свойства различных контейнеров стандартной библиотеки C++.

_{создан David Moore и licensed CC BY-SA 3.0}

Answer 2

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

Для того, чтобы "i й позиции «имеет смысл, должен быть заказ

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

последовательность: 4 5 2 упорядочен, 4 приходит первый, то 5, то 2 и последовательность 5 2 4 также заказать