Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
kvendingoldo
0 / 0 / 0
Регистрация: 22.09.2013
Сообщений: 23
1

Сортировка вектора структур

11.02.2015, 19:21. Просмотров 904. Ответов 3
Метки нет (Все метки)

Всем привет. При написании программы наткнулся на проблему: имею вектор структур, который нужно отсортировать(сортировкой Шелла) по определённому полю. Шаблон сортировки я написал, но как передавать поле для сортировки? Гуглил на тему, советуют лямбды. Я лямбд, пока что, не знаю ;(

Моя идея : передавать в функцию сортировки вектор, а там уже сортировать по определённому полю. Но как передать поле? Шаблон у меня не получилось написать так, как я хочу.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename field>// как добавить?
void shellSort( vector<myStruct> &arr, int size )
    {
 
    int step = size / 2;// шаг.
    while (step > 0)
    {
      for (int i = 0; i < (size - step); i++)
                {
                    int j = i;
                    while (j >= 0 && arr[j] > arr[j + step])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                        j--;
                    }
                }
                step = step / 2;
            }   
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.02.2015, 19:21
Ответы с готовыми решениями:

Сортировка вектора структур
Привет всем! Почему это не сортируется? Или как это правильно отсортировать? ...

Сортировка вектора структур за алфавитом
Разработать программу , которая выделяет все слова, встречающиеся в текстовом...

Сортировка массива(вектора)структур по одному полю
Код:#include &lt;iostream&gt; #include &lt;sstream&gt; #include &lt;vector&gt; #include...

Сортировка массива (вектора) структур по заданному полю
Нужно отсортировать массив по полю структуры. Все поля типа string. struct...

Блочная сортировка структур (Отсортировать массив структур по фамилии)
Подскажите алгоритм блочной сортировки структур на языке С++. Мне нужно...

3
DU
1486 / 1132 / 164
Регистрация: 05.12.2011
Сообщений: 2,279
11.02.2015, 20:06 2
while (j >= 0 && arr[j] > arr[j + step])
вот в этом условии сравнивайте поля, по которым сортируете. т.е:
C++
1
while (j >= 0 && arr[j].myfield > arr[j + step].myfield)
чтобы это было универсально, в шаблон нужно передать функтор, который будет
сравнивать для объекта типа myStruct
сигнатура такая:
C++
1
bool MyPredicate(const myStruct& lhs, const myStruct& rhs);
тогда шаблон с кодом может выглядеть так:


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
template <typename Pred>// как добавить?
void shellSort( vector<myStruct> &arr, int size, Pred pred )
    {
 
    int step = size / 2;// шаг.
    while (step > 0)
    {
      for (int i = 0; i < (size - step); i++)
                {
                    int j = i;
                    while (j >= 0 && pred(arr[j], arr[j + step]))
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                        j--;
                    }
                }
                step = step / 2;
            }   
}
 
bool MyPred(const myStruct& lhs, const myStruct& rhs)
{
   return lhs.myField > rhs.myField;
}
 
int main()
{
   std::vector<myStruct> vec;
   shellSort(vec, vec.size(), &MyPred);
 
   // либо с лямбдой:
   shellSort(vec, vec.size(), [] (const myStruct& lhs, const myStruct& rhs)
   {
      return lhs.myField > rhs.myField;
   });
 
   return 0;
}
если в функцию сортировки передается размер массива - то это лишний параметр.
размер можно взять из самого вектора. у него для этого есть метод size()
1
kvendingoldo
0 / 0 / 0
Регистрация: 22.09.2013
Сообщений: 23
11.02.2015, 20:22  [ТС] 3
Не совсем понял логику работы.

Мы в
C++
1
shellSort(...)
передаём массив, размерность(уже не передаём, ибо не нужно), и функтор. Далее в функторе какая-то магия уже.. Не объясните?

ps: а где можно прочесть ликбез по лямбдам и функторам?
0
DU
1486 / 1132 / 164
Регистрация: 05.12.2011
Сообщений: 2,279
11.02.2015, 20:45 4
функтор - указатель на функцию или объект, у которого переопределен оператор ()
вся ваша сортировка основана на операции > (while (j >= 0 && arr[j] > arr[j + step]));
допустим сортируются инты.
вы же можете написать вместо явного сравнения интов вызов функции, которая
будет это делать:

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
// вот у вас есть такая функция
void MyComparison(int lhs, int rhs)
{
   return lhs > rhs;
}
 
 
//и вот вы в своей сортировки вместо явного сравнения воткнули вызов
//этой функции
...
while (j >= 0 && MyComparison(arr[j], arr[j + step]))
...
 
 
 
// но т.к.  у вас сравниваться должны структуры по какому-то полю,
// для этого случая нужно написать функцию, которая принимает
// не инты, а эти структуры и сравнивает их нужным вам способом
// (по какому-то полю)
// вот у вас есть такая функция
void MyComparison(myStruct lhs, myStruct rhs)
{
   return lhs.someField > rhs.someField;
}
 
 
// код сравнения остался такой же, как и  в случае с интами.
// для срванения вызывается какая-то функция.
...
while (j >= 0 && MyComparison(arr[j], arr[j + step]))
...
в обоих случаях вызывается какая-то функция сравнения. чтобы это работало
в shellSort нужно передать указатель на функцию или лямбду или что-то похожее,
к чему можно применить оператор скобки передавая в них параметры (вот
указатель на функцию, лямбда и другие вещи - это все называют функтором).
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.02.2015, 20:45

Инициализация вектора структур
Не могу инициализировать вектор. struct cmd{ QString name; ...

Индексация вектора структур
Здравствуйте! Возник следующий вопрос: Почему при попытке создания массива...

Чтение вектора структур из файла
struct TRANSACTIONS { unsigned long long sender; unsigned long long...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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