Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
#1

Сортировка индексов алгоритмом std::sort - C++

17.06.2011, 08:42. Просмотров 3923. Ответов 25
Метки нет (Все метки)

Есть два массива одинаковой размерности. В одном хоть что, во втором целые числа (индексы элементов первого массива). Нужно выполнить сортировку второго массива по заданным полям первого массива.
Используя STL, разумеется.
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив, но терзают смутные сомнения, что есть более элегантное решение. Тем более, что при сортировке первого массива, второй сортировать не поучится таким способом (думаю забить и использовать два индексных массива).
Есть умные идеи?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2011, 08:42     Сортировка индексов алгоритмом std::sort
Посмотрите здесь:

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

Сортировка списка с использованием std::sort - C++
Что-то не получается отсортировать целочисленные данные расположенные в списке, компилятор (VS10) жутко ругается. В чем может быть дело? ...

Сортировка вектора через std::sort - C++
Доброго времени суток, интересует сабж void Sort(list<int> &past) { sort(past.begin(), past.end()); } на такое выдает ...

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

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

std::sort() - C++
Доброго времени суток! Есть некая структура: struct member { int latency; std::vector<int>child; };

std::sort - C++
Достоинства и недостатки делаю таблицу, достоинств и недостатков std::Sort. собственно, не нащёл нечего про это в википедии

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 08:53  [ТС]     Сортировка индексов алгоритмом std::sort #16
Цитата Сообщение от AncinetHero Посмотреть сообщение
Почему нельзя скопировать массив
Конкретно, когда возникла эта задача, проблема была в следующем: двусторонний map. люч одновременно является значением и значение является ключём. Два мэпа использовать нельзя, т.к. значения не просто ищутся, но и изменяются. Причём, если с простыми типами это ещё возможно, то вот с объектами всё печальнее. Тип ключа и значения совпадает (он объект), но используются разные поля. Делать копию нельзя, т.к. после обнаружения объект модифицируется. А ещё он большой.
Сделать два мэпа с указателями на объекты тоже нельзя, потому что они хранятся в массиве (список и т.п. отвергнуты на этапе тестирования).
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
16.03.2012, 08:54     Сортировка индексов алгоритмом std::sort #17
Как я понял, нужно сортировать один массив, и одновременно по значениям первого сортировать второй.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:00  [ТС]     Сортировка индексов алгоритмом std::sort #18
Цитата Сообщение от Luke Посмотреть сообщение
все верно?
Ты правильно понял не правильное название темы.)
index используется для упорядоченного доступа к mass.

Добавлено через 48 секунд
Цитата Сообщение от taras atavin Посмотреть сообщение
Это сортировка индексов.
А теперь сделай то же самое, но с использованием std::sort.

Добавлено через 1 минуту
Цитата Сообщение от Luke Посмотреть сообщение
"сортируем" index как нам надо
Вот это не правильно. Понятие сортировки однозначно. В твоём примере входные и выходные данные будут идентичны (если сортировка по возрастанию используется).

Добавлено через 2 минуты
Цитата Сообщение от Luke Посмотреть сообщение
это наверно от привычки думать открытыми циклами
У меня нет никакого желания писать реализацию бинарной сортировки. Поэтому STL.
Если не можешь использовать стандартные алгоритмы, значит что-то не так с архитектурой.
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:00     Сортировка индексов алгоритмом std::sort #19
C++
1
2
3
4
5
6
7
8
9
10
int index [10] = {3,1,5,7,8,9,0,2,4,6};// не отсортированные индексы.
 
    int mass [10] = {11,22,33,44,55,66,77,88,99,00}; //произвольный массив
 
//int realdata [10] = {44,22,66,88,99,00,11,33,55,77}; данные на выходе берут из mass
// используя индекс.
    //реалдата как бы нет, его держим в уме.
 
 
int value = mass[index[3]]; //это перемещение по реалдата.
при любой перестановке в индексе. на выходе будут соответсвующие новым позициям данный взятые из масс.
при этом масс - константен и не трогается
C++
1
std::sort(index,index+10);//сортируя индекс чем угодно, "сортируем" реалдата не трогая масс
задача сводится не к сортировке а к написанию процедуры взятия значения из масс соответственно индексу.
а для сортировки индекс - пожалуйста, используй тот сорт который душе угоден
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:01  [ТС]     Сортировка индексов алгоритмом std::sort #20
Цитата Сообщение от AncinetHero Посмотреть сообщение
нужно сортировать один массив, и одновременно по значениям первого сортировать второй.
Да. Эта одна из двух задач. Одно из ограничений - использование std::sort.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 09:04     Сортировка индексов алгоритмом std::sort #21
Сорт вроде просит функцию сравнения. Ну так и надо передать такую функцию сравнения, у которой больше тот индекс большего элемента.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:05  [ТС]     Сортировка индексов алгоритмом std::sort #22
Цитата Сообщение от Luke Посмотреть сообщение
при любой перестановке в индексе. на выходе будут соответсвующие новым позициям данный взятые из масс.
Совершенно верно. Только вот перестановки в index выполняются в соответствии со значениями в mass, а не хоть как.

Добавлено через 1 минуту
Цитата Сообщение от taras atavin Посмотреть сообщение
ну так и надо передать функцию, сравнивающую элементы.
Цитата Сообщение от Deviaphan Посмотреть сообщение
Всё, что пока смог придумать, это сохранить в компаранде ссылку на первый массив
Но, увы...
Цитата Сообщение от Deviaphan Посмотреть сообщение
но терзают смутные сомнения, что есть более элегантное решение
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:17     Сортировка индексов алгоритмом std::sort #23
Deviaphan, итого получаем - индекс должен быть отсортирован по масс, значения из масс беруться по индекс. вопрос. масс не трогаем? его нельзя сортировать?

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

давай еще детализируй.

уже большая часть понятна. осталась "самая малость" по какому принципу будет сортироваться индекс?
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.03.2012, 09:23     Сортировка индексов алгоритмом std::sort #24
Цитата Сообщение от Deviaphan Посмотреть сообщение
есть более элегантное решение
Более элегантно это с лямбдой, но как я понимаю нужен С++03, попозже еще подумаю, как это сделать, пока тоже ничего не вижу, кроме сохранения в компараторе.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
   std::vector<int> idx = { 0, 1, 2, 3, 4 };
   std::vector<int> val = { 5, 1, 2, 8, 4 };
   
   std::sort(std::begin(idx), std::end(idx), 
      [val] (int a, int b) 
      {
         return val[a] < val[b];
      }
   );
   
   std::copy(std::begin(idx), std::end(idx), std::ostream_iterator<int>(std::cout, " "));
   std::cout << std::endl;
}
Luke
37 / 37 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:32     Сортировка индексов алгоритмом std::sort #25
Цитата Сообщение от fasked Посмотреть сообщение
с лямбдой
ну если не лямбда то придется просто написать соответствующий функтор да и все.

элегантное решение. можно закрыть думаю тему. много вопросов было от непонимания постановки задачи
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2012, 10:37     Сортировка индексов алгоритмом std::sort
Еще ссылки по теме:

algorithm std::sort - C++
Почему так делать нельзя? #include &lt;algorithm&gt; using namespace std; class T { private: int arr;

Абстрактный класс и std::sort - C++
Добрый день, Не компилируется строка: std::vector&lt;mtl::io::QtFile*&gt; *vec; ... mtl::misc::Sort(vec); // ЭТА СТРОКА ...

Std::sort - 3 аргумент другая функция - C++
Здравствуйте. Так все работает //вызывается из наследника sort(group.begin(), group.end(), ( MyClass&amp; obj1, MyClass&amp; obj2)...

Не работает std::sort со списком указателей - C++
Добрый день, товарищи! Делаю лабу по STL в VS 2015. имеется базовый класс и три от него унаследованных. делаю list указателей на базовый...

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


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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 10:37  [ТС]     Сортировка индексов алгоритмом std::sort #26
Цитата Сообщение от Luke Посмотреть сообщение
использовать их как индексы для индекс будет возможно не иначе как через хеш функцию
В начальной постановке нужно было искать объект по одному из двух полей.Поэтому я хотел отсортировать их по одному полю (для поиска по нему) и сделать массив индексов для поиска по второму полю. Отсюда возникла задача с одновременной сортировкой двух массивов. Однако, с увеличением сложности объекта и ростом количества полей, по которым его нужно было искать стало очевидно второе решение, с неизменным массивом объектов и сортировкой только массивов индексов. Сперва пугали накладные расходы, но это всего лишь десятки мегабайт, поэтому это решение и было выбрано как лучшее.


Цитата Сообщение от fasked Посмотреть сообщение
с лямбдой
Элегантнее, да. Спасибо.)
Но мне нужна поддержка 2005,2008,2010 студий.(
Оставлю компаранд, уж скоро год, как с ним всё работает... Но хочется няшнее.
Yandex
Объявления
16.03.2012, 10:37     Сортировка индексов алгоритмом std::sort
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru