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

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

Последовательности

Вы можете уточнить базовую концепцию контейнера, добавив требования. Последовательность является важным уточнением, поскольку несколько типов контейнеров STL — deque, forward_list (C++11), list, queue, priority_queue, stack и vector — являются последовательностями. (Вспомним, что очередь позволяет добавлять элементы в конце и удалять их в начале. Двусторонняя очередь, представленная deque, позволяет добавлять и удалять элементы в обоих концах.) Требование, чтобы итератор был как минимум прямым итератором. гарантирует, что элементы расположены в определенном порядке, который не меняется от одного цикла итерации к другому. Класс массива также классифицируется как контейнер последовательности, хотя и не удовлетворяет всем требованиям. Последовательность также требует, чтобы ее элементы были расположены в строгом линейном порядке. То есть есть первый элемент, есть последний элемент, и каждый элемент, кроме первого и последнего, имеет ровно один элемент непосредственно перед ним и один элемент сразу после него. it. Массив и связанный список являются примерами последовательностей, тогда как ветвящаяся структура (в которой каждый узел указывает на два дочерних узла) таковыми не являются.

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

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


person Krishna Keshan    schedule 18.06.2015    source источник
comment
там написано есть, не надо поддерживать   -  person Othman Benchekroun    schedule 18.06.2015
comment
Какая разница? Если вы подразумеваете, что порядок просто существует и его не нужно поддерживать, зачем вообще упоминать об этом?   -  person Krishna Keshan    schedule 18.06.2015
comment
Поскольку вы процитировали много текста, пожалуйста, добавьте ссылку на источник. Это может быть полезно для других, и это вежливо по отношению к правообладателю.   -  person Kif    schedule 18.06.2015
comment
@user3143420 user3143420 Существует порядок, поэтому, когда вы хотите добавить элемент после i-го элемента, мы можем найти i-й элемент   -  person Othman Benchekroun    schedule 18.06.2015
comment
Это из книги C++ Primer Plus 6th Edition.   -  person Krishna Keshan    schedule 18.06.2015
comment
@OthmanBenchekroun В нем говорится, что элементы можно вставлять, а диапазоны можно удалять откуда угодно, а не только с первого или последнего   -  person Krishna Keshan    schedule 18.06.2015
comment
вам нужно прочитать предложение целиком: вставка значений в определенное место (а не просто вставка) и стирание определенного диапазона (а не просто удаление элементов). Это конкретное местоположение и конкретные аспекты диапазона, которые становятся доступными при заказе.   -  person Sander De Dycker    schedule 18.06.2015
comment
@SanderDeDycker Particular просто добавляет конкретное место и ничего не обобщает. Не уверен, что вы поняли мой вопрос.   -  person Krishna Keshan    schedule 18.06.2015
comment
@user3143420 user3143420 Я ничего не говорил о последнем или первом ... я думаю, вы не понимаете, что они имеют в виду под порядком   -  person Othman Benchekroun    schedule 18.06.2015
comment
@OthmanBenchekroun Именно поэтому я пришел сюда   -  person Krishna Keshan    schedule 18.06.2015
comment
@ user3143420 упорядоченный означает последовательность, имеющую порядок, вы можете сказать, что этот узел первый, этот узел i'й, я думаю, вы путаете его с отсортированным   -  person Othman Benchekroun    schedule 18.06.2015
comment
Как насчет аналогии. Если люди стоят в очереди, они располагаются последовательно (в линию). У всех (кроме первого и последнего) есть один человек непосредственно впереди и один сразу позади. Человек может встать в очередь между двумя людьми или выйти из очереди. Ни одно из этих действий не изменяет упорядоченное свойство линии. С другой стороны, учтите, что все эти люди просто сгруппированы случайным образом. В таком случае порядка нет, и человек не может поставить себя между двумя другими людьми, потому что нет такого понятия, как между.   -  person Sander De Dycker    schedule 18.06.2015
comment
@OthmanBenchekroun Нет, нет. Я понимаю, что такое сортировка. Я имею в виду, что каждый элемент имеет одни и те же элементы позади и перед ним все время. Ничего общего с сортировкой.   -  person Krishna Keshan    schedule 18.06.2015
comment
@SanderDeDycker, ссылаясь на вашу аналогию, будь то линия или группа, удаление людей в нее и добавление людей в нее все еще возможно. Означает ли порядок просто линию, например, что-то впереди и что-то сзади? Это ваша точка зрения?   -  person Krishna Keshan    schedule 18.06.2015
comment
@user3143420 user3143420 Я не знаю, что вы имеете в виду под словом «все время», но это не похоже на хорошее понимание порядка, посмотрите на мой ответ   -  person Othman Benchekroun    schedule 18.06.2015
comment
@user3143420 user3143420: в этом и смысл, да. Вы можете добавить человека как в группу, так и в линию. Но только линия позволяет вам добавить человека на определенную позицию в линии (т.е. между двумя другими людьми). В этом разница между упорядоченным набором людей и неупорядоченным набором людей.   -  person Sander De Dycker    schedule 18.06.2015
comment
Хм. Думаю, я понял. Спасибо за ответы, ребята.   -  person Krishna Keshan    schedule 18.06.2015
comment
Но эй, прочитай текст еще раз. В нем говорится, что порядок определен и не меняется от одного цикла итерации к другому. Что об этом?   -  person Krishna Keshan    schedule 18.06.2015
comment
@ user3143420: свойство упорядочения не исчезает только потому, что вы сделали последовательность длиннее или короче. Конечно, позиции элементов в последовательности могут меняться по отношению к позициям других элементов (например, они могут быть ближе друг к другу или дальше друг от друга), но в целом последовательность остается упорядоченной, независимо от того, сколько вы добавляете или удалить. Другими словами, не сосредотачивайтесь на относительном/абсолютном положении элементов (которое может меняться со временем), а скорее на том факте, что они ИМЕЮТ положение с самого начала.   -  person Sander De Dycker    schedule 18.06.2015
comment
Да, я понял это. Я считал, что положение элементов по отношению друг к другу остается неизменным. Большое спасибо.   -  person Krishna Keshan    schedule 18.06.2015


Ответы (2)


Какие-то контейнеры заказаны, какие-то отсортированы, какие-то и то и другое, а какие-то ни то, ни другое. Например:

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

std::map и std::set и отсортированы, и упорядочены.

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

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

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

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

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

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

Структура контейнера стандартной библиотеки C++создана Дэвид Мур и лицензия CC BY- SA 3.0

person Cory Kramer    schedule 18.06.2015
comment
Я немного запутался. Я ясно прочитал в тексте, что все последовательности упорядочены, в отличие от того, что вы сказали. - person Krishna Keshan; 18.06.2015
comment
Я был очень осторожен в своей терминологии, хотя мне следовало бы более четко указать различие. Последовательность — это подмножество контейнера. Все примеры, которые я привел, являются контейнерами, но только std::list и std::vector будут считаться последовательностью (как и std::string, std::deque и т. д.). - person Cory Kramer; 18.06.2015
comment
Ох, ладно. Но и векторы не имеют определенного порядка. Они действуют до тех пор, пока не будут изменены, но в этом и заключается вся суть изменения чего-либо. Если бы векторы имели определенный порядок, было бы невозможно каким-либо образом модифицировать элементы. - person Krishna Keshan; 18.06.2015
comment
@user3143420 user3143420 снова путает порядок с отсортированным - person Othman Benchekroun; 18.06.2015
comment
@OthmanBenchekroun Рассмотрим этот вектор: vector‹int› vec; vec.push_back (10); vec.push_back(4); vec.push_back (100); элементы никак не сортируются. Но если я вставлю элемент в вектор после 4, разве это не нарушит порядок? - person Krishna Keshan; 18.06.2015
comment
Мне особенно нравится эта блок-схема, есть ли источник этого изображения? - person shuttle87; 18.06.2015
comment
@shuttle87 shuttle87 Я позаимствовал это изображение из этой темы в частности от @zdan. Я добавлю оригинальную цитату для изображения, я, конечно, не имел в виду преднамеренный плагиат. - person Cory Kramer; 18.06.2015
comment
@КориКрамер, спасибо. Конечно, не выдвигая обвинений в плагиате, хотя я хотел избежать этого сам, поскольку это казалось действительно полезным образовательным инструментом для менее опытных разработчиков на С++, о котором я, возможно, хотел бы написать в блоге. - person shuttle87; 18.06.2015

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

Для того, чтобы "ith position" имело смысл, должен быть порядок

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

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

person Othman Benchekroun    schedule 18.06.2015
comment
Именно то, что я пытаюсь сказать. Итак, считается ли массив последовательностью с точки зрения порядка, т.е. имеет функцию индекса? - person Krishna Keshan; 18.06.2015