8 / 8 / 0
Регистрация: 16.07.2013
Сообщений: 148
|
|
1 | |
Доступ к нужному члену массива после сортировки std::sort15.09.2020, 09:01. Показов 1124. Ответов 21
Метки нет (Все метки)
Приветствую всех.
Допустим, есть у меня массив объектов. Я знаю индекс нужного объекта в массиве, и через этот индекс могу ссылаться на объект. Сортирую массив посредством std::sort и все, что дальше? Теперь я не знаю где нужный мне объект, так как теперь по его индексу может находится любой другой. Как правильно поступать в таком случае?
0
|
15.09.2020, 09:01 | |
Ответы с готовыми решениями:
21
Использование std::sort() для сортировки числового массива std::sort/qSort. Реализация сортировки с заданной функцией сортировки в классе. must use '.*' or '->*' to call Алгоритм сортировки std::sort Сравнение алгоритмов сортировки Хоара и std::sort |
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
|
15.09.2020, 09:06 | 2 |
MikeNew,
Я бы перед сортировкой получал указатель/адресс на этот элемент, тогда после сортировки к нему можно будет получить доступ по тому же адресу, по идее так.
0
|
Вездепух
11694 / 6373 / 1723
Регистрация: 18.10.2014
Сообщений: 16,059
|
|
15.09.2020, 09:10 | 3 |
Правильно поступать чтоб сделать что? Найти, куда переместился объект после сортировки?
Способ 1 Если ключи в массиве уникальны, то вы можете просто найти новое место элемента в массиве после сортировки. Способ 2 * Отсортировать при помощи std::sort не сам массив, а дополнительный массив индексов, ссылающихся на исходный массив. Исходный массив при этом останется нетронутым. * В массиве индексов после сортировки вы получите сортирующую перестановку. Она скажется вам, как нужно переставить элементы исходного массива, чтобы его отсортировать. Она же скажет вам, куда переместится любой элемент массива в процессе сортировки. * Далее применяем эту сортирующую перестановку к исходному массиву (готовой функции нет, но написать ее несложно), в результате чего исходный массив отсортируется. Добавлено через 24 секунды Это как это?
1
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
|
15.09.2020, 09:13 | 4 |
0
|
Вездепух
11694 / 6373 / 1723
Регистрация: 18.10.2014
Сообщений: 16,059
|
|
15.09.2020, 09:14 | 5 |
0
|
Комп_Оратор)
|
|
15.09.2020, 09:16 | 6 |
MikeNew, если прошла сортировка массива объектов и у вас нет способа идентификации по значению (на крайний случай - числовой id) то связь с объектом утеряна.
Как вариант решения вопроса - сортировка указателей на элементы массива. Тогда сам массив не будет изменён и сохранённый адрес или ссылка на требуемый объект будут валидны и после сортировки. Доступ же к сортированной последовательности (например для бинарных алгоритмов) - через полученный прокси-массив указателей.
1
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
|
15.09.2020, 09:17 | 7 |
0
|
1352 / 851 / 365
Регистрация: 26.02.2015
Сообщений: 3,799
|
||||||
15.09.2020, 12:50 | 9 | |||||
Kuzia domovenok, ты прав.
https://en.cppreference.com/w/... /list/sort
0
|
Комп_Оратор)
|
|
15.09.2020, 12:50 | 10 |
Время дольше. И кеш-проблематично. Сортировка указателей или как предложено выше - индексов а уже потом самого массива, например (один алгоритм даст одно и то же размещение) решает вопрос но с дополнительном уровнем косвенности и дополнительной памятью пропорциональной O(N). А список и сортируется медленнее и ищется потом по сортированному - медленнее. Но если память - узкое место, а время резиновое, то список вполне подходит.
0
|
6105 / 3460 / 1405
Регистрация: 07.02.2019
Сообщений: 8,791
|
|
15.09.2020, 13:01 | 11 |
Список на каждый узел хранит ещё пару указателей, так же не забывайте про фрагментацию памяти и то, что система может выделять куски больше, чем нужно для размещения одного узла. Так что по памяти эффективнее будет как раз два массива(элементы и индексы/указатели).
Добавлено через 3 минуты Хотя если память уже сильно фрагментирована и не удаётся выделить один кусок, но при этом отдельных маленьких кусочков хватит, что бы сформировать список, то да - в этом случае "эффективнее".
0
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
||||||
15.09.2020, 13:33 | 12 | |||||
Есть место быть такому коду?:
0
|
Комп_Оратор)
|
|
15.09.2020, 13:42 | 13 |
Не горячитесь. Если размер элемента килобайт, то список может быть эффективнее так как хранит данные в динамической памяти. Накладные расходы на создание узла - там же. При этом массив хорошо работает когда он нужен весь и сразу, но ни цента больше. zayats80888, это case-depended вопрос. Мне интереснее гораздо, увидеть как стандартно реализуется:
Где-то это описано? По сути, индекс-цепочка, это произвольная последовательность Лемера. Как тут обстоит дело с дополнительной памятью, какие алгоритмы можно применить?
0
|
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 846
|
|
15.09.2020, 14:10 | 14 |
0
|
Комп_Оратор)
|
||||||
15.09.2020, 14:19 | 15 | |||||
Сообщение от современная детская сказочка-засыпалочка
Не бейте, но задача не для новичка. Вот грубый возможный каркас:
0
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
||||||
15.09.2020, 14:22 | 16 | |||||
Тестируя свою как оказалось глупую идею по следующему грязному коду:
0
|
Комп_Оратор)
|
|
15.09.2020, 14:28 | 17 |
Если только вы не отсортируете массив указателей. Но туда предикатик нужно написать и передать.
SkYMaaN, объясните зачем вам нужно сохранять доступ по индексу, на элемент отсортированного массива? После сортировки элементы умирают и создаются копированием (в общем разе). Там, строго говоря, уже нет тог что вы ищете. А значение - есть. Так вот, объясните, где вам это понадобилось.
0
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
|||||||||||
15.09.2020, 14:33 | 18 | ||||||||||
IGPIGP, это не мне понадобилось, я не создатель темы.
Я попытался помочь, а по итогу теперь самому интересно, лишним знанием не будет. Если я правильно понял, то у:
0
|
6105 / 3460 / 1405
Регистрация: 07.02.2019
Сообщений: 8,791
|
|
15.09.2020, 14:34 | 19 |
Вектор там же хранит. Под массивом я подразумевал непрерывную последовательность, а не класс хранения.
Разумеется, иначе списки были бы не нужны. Но в вашем сообщении речь шла о эффективности по памяти списка из N объектов vs массива из N объектов + массива из N индексов/указателей.
0
|
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
|
|
15.09.2020, 14:44 | 20 |
0
|
15.09.2020, 14:44 | |
15.09.2020, 14:44 | |
Помогаю со студенческими работами здесь
20
Какой алгоритм сортировки использует std::sort(); Почему стандартная сортировка вектора std::sort намного быстрее сортировки вставками/пузырьком? Сортировка массива c++ std :: sort() Сортировка массива структур по выбранному полю с помощью алгоритма std::sort HLSL Шейдер: не могу получить доступ к члену массива, используя переменную как индекс Почему сбрасываются ключи при сортировки массива ф-ей sort? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |