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

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

Войти
Регистрация
Восстановить пароль
 
kvendingoldo
0 / 0 / 0
Регистрация: 22.09.2013
Сообщений: 23
#1

Сортировка вектора структур - C++

11.02.2015, 19:21. Просмотров 859. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Сортировка вектора структур (C++):

Сортировка вектора структур - C++
Привет всем! Почему это не сортируется? Или как это правильно отсортировать? #include &lt;iostream&gt; #include &lt;vector&gt; #include...

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

Сортировка массива(вектора)структур по одному полю - C++
Код:#include &lt;iostream&gt; #include &lt;sstream&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; struct Person{ std::string surname,name; ...

Сортировка массива (вектора) структур по заданному полю - C++
Нужно отсортировать массив по полю структуры. Все поля типа string. struct DatabaseData{ std::string aPointOfDeparture;//Пункт...

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

Инициализация вектора структур - C++
Не могу инициализировать вектор. struct cmd{ QString name; qint16 code; }; QVector &lt;cmd&gt; commands={ ...

3
DU
1485 / 1131 / 45
Регистрация: 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
1485 / 1131 / 45
Регистрация: 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
Привет! Вот еще темы с ответами:

Индексация вектора структур - C++
Здравствуйте! Возник следующий вопрос: Почему при попытке создания массива индексов (indexArray) не выходит сохранить в него...

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

Почему не сортирует вектора структур? - C++
Почему не сортирует вектора структур по фамилии? #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;vector&gt; #include...

Считывние вектора структур из файла .txt - C++
Всем доброго времени суток. При выполнении задания, у меня возникла такая проблема: Имеется класс, одно из полей - вектор стуктур. Также...


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

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

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