Сортировка вектора с парой

[tumanovalex]

В программе

#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;
}

после сортировки вектора пары выстраиваются по первому элементу пары, в данном случае по строке. А как можно после обработки первых элементов пар отсортировать вектор по второму элементу пары?

[Majestio]

Цитата tumanovalex @ 16.06.23, 12:06

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

  // C++14
  sort(vsn.begin(), vsn.end(), [](auto a, auto b) {
    return a.second < b.second;
  });

[tumanovalex]

Спасибо!

[Qraizer]

Цитата tumanovalex @ 16.06.23, 12:06

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

Что ты под этим подразумеваешь? Стандартно сравнение для std::pair<> реализовано по std::pair<>::first, и если и только если они равны, что сравниваются std::pair<>::second. Т.е. твой простой вызов уже учёл second в парах, если их first были равны. Но в целом ты можешь в std::sort передать произвольный предикат, лишь бы он удовлетворял критерию ...строгой квазиупорядоченности, вроде бы, не помню точно термина.

[Mr.Delphist]

Цитата 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 - 16.06.23, 17:25

[Majestio]

Mr.Delphist, сортировка по первому элементу пары, в случае равенства вторых элементов - это дополнительное условие, о котором автор не просил. На больших данных, если таковое условие не ставилось, может вызвать неоправданный перерасход электричества планеты!

[Qraizer]

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

[tumanovalex]

Цитата Qraizer @ 16.06.23, 18:14

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

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

[ЫукпШ]

Цитата 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< будет определять "стратегию" конкретной сортировки.
Сделаем в методе автомат состояний - получим возможность изменения стратегии.
Легко обеспечим любой, самый экзотический вариант - мы же сами пишем этот алгоритм.

Сообщение отредактировано: ЫукпШ - 20.06.23, 20:15

[Majestio]

Извини, но Бритва Оккама просто рыдает Без обид