Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
8 / 8 / 0
Регистрация: 16.07.2013
Сообщений: 148
1

Доступ к нужному члену массива после сортировки std::sort

15.09.2020, 09:01. Показов 1124. Ответов 21
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Приветствую всех.

Допустим, есть у меня массив объектов. Я знаю индекс нужного объекта в массиве, и через этот индекс могу ссылаться на объект.
Сортирую массив посредством std::sort и все, что дальше? Теперь я не знаю где нужный мне объект, так как теперь по его индексу может находится любой другой.

Как правильно поступать в таком случае?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.09.2020, 09:01
Ответы с готовыми решениями:

Использование std::sort() для сортировки числового массива
Выбивает ошибка что sort перегружены #include <iostream> #include <algorithm> using namespace...

std::sort/qSort. Реализация сортировки с заданной функцией сортировки в классе. must use '.*' or '->*' to call
Доброго времени суток. Столкнулся с проблемой. Необходимо отсортировать элементы в списке Qt (то...

Алгоритм сортировки std::sort
Какой алгоритм сортировки используется в std::sort? #include <vector> #include <algorithm> ...

Сравнение алгоритмов сортировки Хоара и std::sort
Собственно в универе было дано задание, написать программу которая принимает на вход из файла в...

21
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 09:06 2
MikeNew,
Цитата Сообщение от MikeNew Посмотреть сообщение
Как правильно поступать в таком случае?

Я бы перед сортировкой получал указатель/адресс на этот элемент, тогда после сортировки к нему можно будет получить доступ по тому же адресу, по идее так.
0
Вездепух
Эксперт CЭксперт С++
11694 / 6373 / 1723
Регистрация: 18.10.2014
Сообщений: 16,059
15.09.2020, 09:10 3
Цитата Сообщение от MikeNew Посмотреть сообщение
Как правильно поступать в таком случае?
Правильно поступать чтоб сделать что? Найти, куда переместился объект после сортировки?

Способ 1

Если ключи в массиве уникальны, то вы можете просто найти новое место элемента в массиве после сортировки.

Способ 2

* Отсортировать при помощи std::sort не сам массив, а дополнительный массив индексов, ссылающихся на исходный массив. Исходный массив при этом останется нетронутым.

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

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

Добавлено через 24 секунды
Цитата Сообщение от SkYMaaN Посмотреть сообщение
получал указатель/адресс на этот элемент, тогда после сортировки к нему можно будет получить доступ по тому же адресу, по идее так
Это как это?
1
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 09:13 4
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Это как это?
C++
1
int* = &arr[index];
Я вижу это так, но могу ошибаться.
0
Вездепух
Эксперт CЭксперт С++
11694 / 6373 / 1723
Регистрация: 18.10.2014
Сообщений: 16,059
15.09.2020, 09:14 5
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Я вижу это так, но могу ошибаться.
И что дальше? Как это вам поможет ответить на поставленный вопрос?
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
15.09.2020, 09:16 6
Цитата Сообщение от MikeNew Посмотреть сообщение
Допустим, есть у меня массив объектов. Я знаю индекс нужного объекта в массиве, и через этот индекс могу ссылаться на объект.
Сортирую массив посредством std::sort и все, что дальше? Теперь я не знаю где нужный мне объект, так как теперь по его индексу может находится любой другой.
Как правильно поступать в таком случае?
MikeNew, если прошла сортировка массива объектов и у вас нет способа идентификации по значению (на крайний случай - числовой id) то связь с объектом утеряна.
Как вариант решения вопроса - сортировка указателей на элементы массива. Тогда сам массив не будет изменён и сохранённый адрес или ссылка на требуемый объект будут валидны и после сортировки. Доступ же к сортированной последовательности (например для бинарных алгоритмов) - через полученный прокси-массив указателей.
1
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 09:17 7
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Как это вам поможет ответить на поставленный вопрос?
Прошу прощения, я не верно воспринял вопрос. Пора спать
0
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
15.09.2020, 12:43 8
Сортировать не массив, а список уже предлагали?
Тогда все указатели и итераторы сохранятся.
2
1352 / 851 / 365
Регистрация: 26.02.2015
Сообщений: 3,799
15.09.2020, 12:50 9
Kuzia domovenok, ты прав.
https://en.cppreference.com/w/... /list/sort

preserves the values of all iterators
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <list>
 
 
 
int main() {
 
    std::list<int> list{ 5, 3, 1, 7, 4, 9 };
 
    auto it = list.begin();
 
    std::cout << "Before sorting: " << *it << '\n';
    list.sort();
    std::cout << "After sorting: " << *it << '\n';
 
    return 0;
 
}
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
15.09.2020, 12:50 10
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Сортировать не массив, а список уже предлагали?
Тогда все указатели и итераторы сохранятся.
Время дольше. И кеш-проблематично. Сортировка указателей или как предложено выше - индексов а уже потом самого массива, например (один алгоритм даст одно и то же размещение) решает вопрос но с дополнительном уровнем косвенности и дополнительной памятью пропорциональной O(N). А список и сортируется медленнее и ищется потом по сортированному - медленнее. Но если память - узкое место, а время резиновое, то список вполне подходит.
0
6105 / 3460 / 1405
Регистрация: 07.02.2019
Сообщений: 8,791
15.09.2020, 13:01 11
Цитата Сообщение от IGPIGP Посмотреть сообщение
Но если память - узкое место, а время резиновое, то список вполне подходит.
Список на каждый узел хранит ещё пару указателей, так же не забывайте про фрагментацию памяти и то, что система может выделять куски больше, чем нужно для размещения одного узла. Так что по памяти эффективнее будет как раз два массива(элементы и индексы/указатели).

Добавлено через 3 минуты
Хотя если память уже сильно фрагментирована и не удаётся выделить один кусок, но при этом отдельных маленьких кусочков хватит, что бы сформировать список, то да - в этом случае "эффективнее".
0
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 13:33 12
Цитата Сообщение от MikeNew Посмотреть сообщение
Теперь я не знаю где нужный мне объект, так как теперь по его индексу может находится любой другой.
Есть место быть такому коду?:
C++
1
2
3
4
5
6
7
8
9
10
11
....
int* ptr = &arr[index];
sort();
int newindex {0};
for(size_t i = 0; i < arrayelementscount;i++)
{
   if(&arr[i]==ptr)
   {
         newindex = i;
   }
}

P.S - не бейте, только учусь
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
15.09.2020, 13:42 13
Цитата Сообщение от zayats80888 Посмотреть сообщение
Список на каждый узел хранит ещё пару указателей, так же не забывайте про фрагментацию памяти и то, что система может выделять куски больше, чем нужно для размещения одного узла. Так что по памяти эффективнее будет как раз два массива(элементы и индексы/указатели).
Не горячитесь. Если размер элемента килобайт, то список может быть эффективнее так как хранит данные в динамической памяти. Накладные расходы на создание узла - там же. При этом массив хорошо работает когда он нужен весь и сразу, но ни цента больше. zayats80888, это case-depended вопрос. Мне интереснее гораздо, увидеть как стандартно реализуется:
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Далее применяем эту сортирующую перестановку к исходному массиву (готовой функции нет, но написать ее несложно), в результате чего исходный массив отсортируется.
Где-то это описано? По сути, индекс-цепочка, это произвольная последовательность Лемера. Как тут обстоит дело с дополнительной памятью, какие алгоритмы можно применить?
0
693 / 303 / 99
Регистрация: 04.07.2014
Сообщений: 846
15.09.2020, 14:10 14
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Есть место быть такому коду?:
Вот проверь и скажи нам, как результат? Изменилось ли значение ptr после sort?
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
15.09.2020, 14:19 15
Цитата Сообщение от современная детская сказочка-засыпалочка
Ударился массив о земь и враз обернулся саваном.
***
Цитата Сообщение от SkYMaaN Посмотреть сообщение
P.S - не бейте, только учусь
Не бейте, но задача не для новичка. Вот грубый возможный каркас:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
using namespace std;
 
template<class T> class
ArraySortedByIndexWrapper
{
    public:
    ArraySortedByIndexWrapper(T * array_begin_, size_t Size_)
    :array_begin(array_begin_)
    ,Size(Size_)
    ,index_array(new size_t[Size])
    {
        for(size_t i=0; i<Size; ++i) index_array[i]=i;
        sort(index_array, index_array+Size, [this](const size_t a, const size_t b){return array_begin[a]<array_begin[b];});
    }
    ~ArraySortedByIndexWrapper(){delete [] index_array ; }
 
    T &operator[](size_t ind){return array_begin[index_array[ind]];}
    const T &operator[](size_t ind)const {return array_begin[index_array[ind]];}
 
 
    private:
    T *array_begin;
    size_t Size;
    size_t *index_array;
};
 
 
int main()
{
    int a[]={3,1,5,2};
    int var=a[2];//5
    ArraySortedByIndexWrapper<int> arraySortedByIndexWrapper(a,4);
    for(size_t i=0; i<4; ++i) cout<<arraySortedByIndexWrapper[i]<<' ';
    cout<<'\n';
    for(size_t i=0; i<4; ++i) cout<<a[i]<<' ';
    cout<<'\n'<<var;//5
 
 
return 0;
}
SkYMaaN, подумайте о постановке задачи. Что-то говорит мне о том, что вам не нужны ссылки, пережившие перемещение или "обёрнутые" массивы.
0
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 14:22 16
Тестируя свою как оказалось глупую идею по следующему грязному коду:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
    setlocale(LC_ALL, ""); 
    srand(time(NULL));
    unsigned const int size = 12;
    int arr[size],index,newindex;
    for (size_t i = 0; i < size; i++)
    {
        arr[i] = 1 + rand() % 15;
    }
    cout << "Вывод неотсортированного массива" << endl;
    for (size_t i = 0; i < size; i++)
    {
        cout << i <<"::" << arr[i] << endl;
    }
    cout << "Введите индекс элемента" << endl; 
    cin >> index;
    int* ptr = &arr[index];
    cout << "Адресс элемента: " << ptr << endl;
    cout << "Сортировка массива..." << endl;
    int min = arr[0];
    for (size_t i = 0; i < size; i++)
    {
        for (size_t j = 0; j < size-1; j++)
        {
            if (arr[j] > arr[i])
            {
                swap(arr[i], arr[j]);
            }
        }
    }
    cout << "Вывод отсортированного массива" << endl;
    for (size_t i = 0; i < size; i++)
    {
        cout << i << "::" << arr[i] << endl;
    }
    for (size_t i = 0; i < size; i++)
    {
        if (&arr[i] == ptr)
        {
            newindex = i;
            cout << "Индекс элемента: " << i << " Значение: " << arr[i]  <<  " Aдресс элемента: " << &arr[i] << endl;
        }
    }
}
Я пришёл к выводу, что указатели на ячейку памяти не меняют ячейку в следствии сортировки массива. Значит сортируются значения внутри ячеек на которые указывают указатели, а не сами указатели.
0
Комп_Оратор)
Эксперт по математике/физике
8949 / 4703 / 629
Регистрация: 04.12.2011
Сообщений: 13,999
Записей в блоге: 16
15.09.2020, 14:28 17
Цитата Сообщение от SkYMaaN Посмотреть сообщение
Я пришёл к выводу, что указатели на ячейку памяти не меняют ячейку в следствии сортировки массива. Значит сортируются значения на которые указывают указатели, а не сами указатели.
Если только вы не отсортируете массив указателей. Но туда предикатик нужно написать и передать.
SkYMaaN, объясните зачем вам нужно сохранять доступ по индексу, на элемент отсортированного массива? После сортировки элементы умирают и создаются копированием (в общем разе). Там, строго говоря, уже нет тог что вы ищете. А значение - есть. Так вот, объясните, где вам это понадобилось.
0
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 14:33 18
IGPIGP, это не мне понадобилось, я не создатель темы.
Я попытался помочь, а по итогу теперь самому интересно, лишним знанием не будет.
Если я правильно понял, то у:
C++
1
int arr[size] = { 1,2,3,4,5 };
есть привязанный массив указателей которые указывают на ячейку индекса? ( извините за глупую формулировку ) по типу:
C++
1
{*i,*i,*i,*i,*i}
?
0
6105 / 3460 / 1405
Регистрация: 07.02.2019
Сообщений: 8,791
15.09.2020, 14:34 19
Цитата Сообщение от IGPIGP Посмотреть сообщение
Если размер элемента килобайт, то список может быть эффективнее так как хранит данные в динамической памяти.
Вектор там же хранит. Под массивом я подразумевал непрерывную последовательность, а не класс хранения.
Цитата Сообщение от IGPIGP Посмотреть сообщение
это case-depended вопрос.
Разумеется, иначе списки были бы не нужны. Но в вашем сообщении речь шла о эффективности по памяти списка из N объектов vs массива из N объектов + массива из N индексов/указателей.
Кликните здесь для просмотра всего текста

Не по теме:

Цитата Сообщение от IGPIGP Посмотреть сообщение
Не горячитесь.
Да я тут мёрзну так то... :)

0
25 / 19 / 8
Регистрация: 05.04.2019
Сообщений: 338
15.09.2020, 14:44 20
Цитата Сообщение от SkYMaaN Посмотреть сообщение
указывают на ячейку индекса?
фигню написал...
указывают на ячейку внутри массива***
0
15.09.2020, 14:44
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.09.2020, 14:44
Помогаю со студенческими работами здесь

Какой алгоритм сортировки использует std::sort();
Сколько пользуюсь но не знаю как он работает. Читал что сложность этой сортировки примерно О(n*lgn)

Почему стандартная сортировка вектора std::sort намного быстрее сортировки вставками/пузырьком?
Здравствуйте, объясните, пожалуйста, как реализована std::sort. Ясно, что через итераторы, но...

Сортировка массива c++ std :: sort()
Дан двумерный массив символов char M, надо отсортировать его при помощи std :: sort(), построчно,...

Сортировка массива структур по выбранному полю с помощью алгоритма std::sort
Не знаю, как правильно передать функцию сравнения в std::sort. Кроме того в моей структуре...

HLSL Шейдер: не могу получить доступ к члену массива, используя переменную как индекс
Здравствуйте, форумчане. Изучаю Directx 11. Пишу на C++. Возникла проблема при написании кода...

Почему сбрасываются ключи при сортировки массива ф-ей sort?
Пример: $array=array(1=&gt;1,a=&gt;7,b=&gt;3,4=&gt;5); sort($array); print_r($array);// выведет Array ( ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru