Редактирование std::set на примере переписывания и отсечения значений

Иногда могут возникать новичковатые вопросы вроде "как перемешать set или map", как поменять ключи местами, как отсортировать множество или карту и подобные им. Появление этих вопросов обусловлено непониманием внутреннего устройства ассоциативных контейнеров и что упорядоченный массив — это массив, которому предначертано быть упорядоченным непосредственно при создании, что определяется упорядочивание только один раз.

В листинге #1 приводится пример попытки переназначения. Проблема только в том, что переназначение будет означать, что одно только это действие потребует сортировки всего массива (множества) s. Т. е. каждое переназначение будет означать сортировку набора значений. А проведение сортировки будет означать, что заданная для создания сортировка не будет иметь смысла, ну, и ещё каждое присваивание требовало бы неоправдано много времени (это же не просто присваивание, а перестроение всего набора).
  • Ассоциативным массивам предначертано быть упорядочеными только в том порядке, в каком их просят быть упорядоченными в момент создания.
  • Любое вмешательство в ассоциативный массив, требующее престроения массива, — это создание нового массива.
  • Если вы используете ассоциативный массив, а у вас часто возникает потребность влиять на него изменением значения, переупорядочиванием или каким-то подобным редактированием, вам следует подумать, правильный ли вид контейнера был выбран.
Чтобы переписать значение, нужно удалить старое и вставить новое (ну или вставить новое и удалить старое). Нельзя просто взять и переписать прямым присваиванием.

Удалить и вставить значение как новое намного эфективнее, чем приходилось бы делать неоправданную сортировку на каждое присваивание. Эффективность связана и с тем, что и вставка, и удаление в set — это быстрые операции.
Бывает и так, что нужно задать свой порядок для упорядоченного массива, от чего как раз иногда и возникают вопросы, а как отсортировать.
  • Задавать свой порядок упорядоченным массивам можно, а нужно это делать в момент объявления массива. Для задействования своего порядка следует использовать функтор.

Иногда может быть нужно усечь set, сделать ему resize. Одно дело, если нужно сделать массив пустым, для этого достаточно использовать clear(), а другое, когда массив с десятком тысяч значений хочется усечь до, например, первых пятиста, и подавать значения порциями по пятьсот. Читающие эту тему уже могли и должны понимать или хотя бы догадываться, что для ассоциативных упорядоченных массивов прямое усечение невозможно, т. е. нельзя как вектору vector сделать resize для set, можно только создавать новый set на основании исходного. В создании нового set и внесении в него значений из старого нет ничего такого, с чем новичок бы не справился, но есть несколько способов: чисто новичковые и в духе STL.

Такое написать может быть сложно на уровне новичка. Но это не только сложно написать новичку, но и сам код относительно многословный: много текста, много переменных, циклы… А в попытках это написать можно столкнуться с обращением к невалидному итератору, с попыткой вытащить значение или из s.end(), или из s.begin(), с выходом за пределы массива, с удалением элементов через один и мало ли чем ещё. В общем, любопытным имеет смысл разобраться, как это работает, а вообще прямое отсечение удалением — это, наверное, самый худший способ решить такую задачу усечения, а #4.2 — яркий пример, как делать ни в коем случае нельзя.
Более продвинутый новичок имеет иной уровень мышления и использует удаление копированием: создаёт новый массив, копирует в него нужные значения, а потом либо использует полученный, либо меняет массивы местами и удаляет ненужный.
  • У set нет доступа по индексу, поэтому, чтобы попасть на элемент по порядковому номеру, можно использовать advance.

В #4.2 разумный подход, тут и кода меньше, и придумывать это проще, чем #4.1. И вообще так делать можно, но это всё же новичковое решение.
Наиболее лёгким и безболезным способом отсечения будет использование алгоритмов. В STL есть copy_n: алгоритм количественного копирования (примечание: он не имеет названия "количественного копирования", просто мне удобно сейчас использовать такую формулировку).

#4.3 — это практически то же самое, что и #4.2 (используется тот же подход), только занимает написание такого кода намного меньше времени. Если кто не знает, то существуют адаптеры итераторов, в которые входят итераторы вставки: вставки в начало, вставки в конец и вставки в указанную позицию. set так устроен, что у него не может быть операции вставки в начало или в конец, но может быть операция просто вставки, поэтому из адаптеров итераторов вставки — для set походит только итератор вставки inserter. Первый аргумент, нужный адаптеру — это контейнер, в который вставлятся элемент, а второй аргумент — это позиция. В случае с set можно указывать любую позицию из диапазона самого set — она служит подсказкой, а не позицией вставки и может игнорироваться компилятором. Само же понятие адаптеров в данном случае подразумевает, что используются такие виды итераторов в алгоритмах. Алгоритм копирования, использующий операторы вставки, будет не перезаписывать значения, а добавлять.
  • Итераторы вставки используются для того, чтобы дать алгоритмам возможность работать в режиме вставки, а не замены. В частности, итераторы вставки решают проблему, возникающую, когда в диапазоне назначения нет достаточного места: они позволяют увеличивать размер диапазона вставки.

Если эта статья кому-то помогла в чём-то разобраться, это замечательно.

Добавить комментарий

Ваш адрес email не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/devid-herron/node-js-razrabotka-servernyh-veb-prilozheniy-na-javascript/?lfrom=15589587
Яндекс.Метрика