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

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

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

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

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

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

Сортировка массива 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 От std::qsort - C++
Пишу доклад по программированию, собственно выбрал тему сортировок. вот сейчас хочу расписать отлчиие + и - двух сортировок. но инфу...

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

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

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

Добавлено через 2 минуты
Цитата Сообщение от Luke Посмотреть сообщение
это наверно от привычки думать открытыми циклами
У меня нет никакого желания писать реализацию бинарной сортировки. Поэтому STL.
Если не можешь использовать стандартные алгоритмы, значит что-то не так с архитектурой.
0
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:00 #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);//сортируя индекс чем угодно, "сортируем" реалдата не трогая масс
задача сводится не к сортировке а к написанию процедуры взятия значения из масс соответственно индексу.
а для сортировки индекс - пожалуйста, используй тот сорт который душе угоден
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:01  [ТС] #20
Цитата Сообщение от AncinetHero Посмотреть сообщение
нужно сортировать один массив, и одновременно по значениям первого сортировать второй.
Да. Эта одна из двух задач. Одно из ограничений - использование std::sort.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
16.03.2012, 09:04 #21
Сорт вроде просит функцию сравнения. Ну так и надо передать такую функцию сравнения, у которой больше тот индекс большего элемента.
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
16.03.2012, 09:05  [ТС] #22
Цитата Сообщение от Luke Посмотреть сообщение
при любой перестановке в индексе. на выходе будут соответсвующие новым позициям данный взятые из масс.
Совершенно верно. Только вот перестановки в index выполняются в соответствии со значениями в mass, а не хоть как.

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

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

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

уже большая часть понятна. осталась "самая малость" по какому принципу будет сортироваться индекс?
0
fasked
Эксперт С++
4942 / 2522 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.03.2012, 09:23 #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;
}
2
Luke
39 / 39 / 1
Регистрация: 21.02.2012
Сообщений: 95
16.03.2012, 09:32 #25
Цитата Сообщение от fasked Посмотреть сообщение
с лямбдой
ну если не лямбда то придется просто написать соответствующий функтор да и все.

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


Цитата Сообщение от fasked Посмотреть сообщение
с лямбдой
Элегантнее, да. Спасибо.)
Но мне нужна поддержка 2005,2008,2010 студий.(
Оставлю компаранд, уж скоро год, как с ним всё работает... Но хочется няшнее.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.03.2012, 10:37
Привет! Вот еще темы с ответами:

std::sort + std::lower_bound - C++
тема такая: есть класс person: class Person{ private: string name_; string adress_; long phone_; есть вектор объектов...

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

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

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


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

Или воспользуйтесь поиском по форуму:
26
Yandex
Объявления
16.03.2012, 10:37
Ответ Создать тему
Опции темы

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