Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3892105 Tue, 20 Jun 2023 20:49:18 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3892105 Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3892103 Tue, 20 Jun 2023 19:22:16 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3892103 Цитата tumanovalex @ 16.06.23, 18:54

Я просил вариант попроще - сортировка по 2 элементу пары (без учета сортировки по первой).

По-моему, так гораздо лучше (приблизительно):

Скрытый текст

#include <iomanip>

#include <vector>

#include <map>

#include <algorithm>

using namespace std;

// сортируемый объект - состоит из строки и индекса

class PMSTR

{

public:

static int state;

string str;

size_t index;

void operator=(const PMSTR& obj);

bool operator<(const PMSTR& obj);

};

int PMSTR::state=0;

void PMSTR::operator=(const PMSTR& obj)

{

str = obj.str;

index = obj.index;

}

// определим 4 варианта сортировки:

bool PMSTR::operator<(const PMSTR& obj)

{

switch(state)

{

case 0:

{

size_t size1 = strlen(str.c_str());

size_t size2 = strlen(obj.str.c_str());

if(size2 > size1) return true;

if(size1 > size2) return false;

for(size_t i=0;i<size1;++i)

{

if((obj.str)[i] < str[i]) return true;

}

}

break;

case 1:

{

size_t size1 = strlen(str.c_str());

size_t size2 = strlen(obj.str.c_str());

if(size2 < size1) return true;

if(size1 < size2) return false;

for(size_t i=0;i<size1;++i)

{

if((obj.str)[i] > str[i]) return true;

}

}

break;

case 2:

if(index < obj.index) return true;

break;

case 3:

if(index > obj.index) return true;

break;

default:state=0;break;

}

return false;

}

int __cdecl _tmain(int argc, TCHAR **argv)

{

setlocale(LC_ALL, "Russian");

vector<PMSTR> strA;

const char* pStrs [] = { "строка", "01строка", "09строка", "04строка", "03строка", "01строка",

"09строка", "05строка", "03строка", "строка", "01строка", "06строка",

"03строка", "06строка", "09строка", "строка", "01строка", "05строка",

"строка", "04строка", "строка", "09строка" , NULL};

size_t size =0;

for(size=0;;++size)

{

if(pStrs[size]==NULL) break;

}

// заполним массив и выведем его:

for(size_t i=0;i<size;++i)

{

PMSTR tmp;

tmp.str = pStrs[i];

tmp.index = i;

strA.push_back(tmp);

}

for(size_t i=0;i<size;++i) { printf("%s\n",strA[i].str.c_str()); } printf("-----\n");

// сортируем по убыванию

sort(strA.begin(), strA.end());

for(size_t i=0;i<size;++i) { printf("%s\n",strA[i].str.c_str()); } printf("-----\n");

// сортируем по возрастанию

strA[0].state=1;

sort(strA.begin(), strA.end());

for(size_t i=0;i<size;++i) { printf("%s\n",strA[i].str.c_str()); } printf("-----\n");

// сортируем по возрастанию индекса

strA[0].state=2;

sort(strA.begin(), strA.end());

for(size_t i=0;i<size;++i) { printf("%s\n",strA[i].str.c_str()); } printf("-----\n");

// сортируем по убыванию индекса

strA[0].state=3;

sort(strA.begin(), strA.end());

for(size_t i=0;i<size;++i) { printf("%s\n",strA[i].str.c_str()); } printf("-----\n");

return 0;

}

Дело в том, что типов сортируемых объектов может быть очень много,
и каждый тип может иметь множество полей.
При этом требуются самые разннобразные сортировки.
Пусть сортируемый объект сам определяет стратегии своей сортировки.
Можно и так сказать, что реакция объекта на сортировку - это форма
его уникального поведения.
---
Сортировка основана на двух операциях - сравнения и обмена (мест элементов в массиве).
(Это не обязательно. Можно не менять объекты местами, можно манипулировать указателями.)
Значит, определив для объекта операции operator< и operator= можно обеспечить работу
алгоритма сортировки. При этом метод operator< будет определять "стратегию" конкретной сортировки.
Сделаем в методе автомат состояний - получим возможность изменения стратегии.
Легко обеспечим любой, самый экзотический вариант - мы же сами пишем этот алгоритм.]]> ЫукпШ C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891984 Fri, 16 Jun 2023 18:54:41 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891984 Цитата Qraizer @ 16.06.23, 18:14

Та тут вообще непонятно, что он просил. Мож он хотел сортировку по второму элементу, не нарушая уже имеющейся сортировки по первому.

Я просил вариант попроще - сортировка по 2 элементу пары (без учета сортировки по первой). Я не знал, как это сделать. Теперь знаю.]]> tumanovalex C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891980 Fri, 16 Jun 2023 18:14:00 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891980 Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891978 Fri, 16 Jun 2023 17:34:19 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891978 Mr.Delphist, сортировка по первому элементу пары, в случае равенства вторых элементов - это дополнительное условие, о котором автор не просил. На больших данных, если таковое условие не ставилось, может вызвать неоправданный перерасход электричества планеты!]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891977 Fri, 16 Jun 2023 17:24:50 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891977 Цитата Qraizer @ 16.06.23, 16:09

Стандартно сравнение для std::pair<> реализовано по std::pair<>::first, и если и только если они равны, что сравниваются std::pair<>::second.

Кстати, очень важное уточнение - случай равенства забывать нельзя. Тогда вариант Majestio можно уточнить как-то так:

Цитата Majestio @ 16.06.23, 12:30

// C++14
sort(vsn.begin(), vsn.end(), [](auto a, auto b) {
return (a.second == b.second) ? (a.first < b.first) : (a.second < b.second); // если ключевые поля равны, сравниваем вспомогательные, иначе сравниваем ключевые
});

]]> Mr.Delphist C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891971 Fri, 16 Jun 2023 16:09:05 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891971 Цитата tumanovalex @ 16.06.23, 12:06

А как можно после обработки первых элементов пар отсортировать вектор по второму элементу пары?

Что ты под этим подразумеваешь? Стандартно сравнение для std::pair<> реализовано по std::pair<>::first, и если и только если они равны, что сравниваются std::pair<>::second. Т.е. твой простой вызов уже учёл second в парах, если их first были равны. Но в целом ты можешь в std::sort передать произвольный предикат, лишь бы он удовлетворял критерию ...строгой квазиупорядоченности, вроде бы, не помню точно термина.]]> Qraizer C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891954 Fri, 16 Jun 2023 13:02:45 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891954 tumanovalex C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891952 Fri, 16 Jun 2023 12:30:07 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891952 Цитата tumanovalex @ 16.06.23, 12:06

А как можно после обработки первых элементов пар отсортировать вектор по второму элементу пары?

// C++14

sort(vsn.begin(), vsn.end(), [](auto a, auto b) {

return a.second < b.second;

});

]]> Majestio C/C++: Общие вопросы https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891943 Fri, 16 Jun 2023 12:06:51 +0000 Сортировка вектора с парой https://forum.sources.ru/index.php?showtopic=435775&view=findpost&p=3891943

#include <iomanip>

#include <vector>

#include <map>

#include <algorithm>

using namespace std;

int main(int argc, char* argv[])

{

setlocale(LC_ALL, "Russian");

vector<string> str = { "строка", "01строка", "09строка", "04строка", "03строка", "01строка",

"09строка", "05строка", "03строка", "строка", "01строка", "06строка",

"03строка", "06строка", "09строка", "строка", "01строка", "05строка",

"строка", "04строка", "строка", "09строка" };

vector < pair<string, unsigned int>> vsn;

for (int i = 0; i < str.size(); i++)

vsn.push_back(make_pair(str[i], i));

sort(vsn.begin(), vsn.end());

for (int i = 0; i < str.size(); i++)

cout << vsn[i].first << '\t' << vsn[i].second << endl;

// здесь будет преобразование первого элемента пары

system("pause");

return 0;

}

после сортировки вектора пары выстраиваются по первому элементу пары, в данном случае по строке. А как можно после обработки первых элементов пар отсортировать вектор по второму элементу пары?]]> tumanovalex C/C++: Общие вопросы