Сортировка векторов в C++

Question

Мне нужно отсортировать структуру данных vector<pair<unsigned, pair<vector<unsigned>, vector<unsigned> > > > sbp сначала с помощью sbp.second.second vector и для равных значений sbp.second.second by sbp.second.first - оба вектора сравниваются (i) размер векторов; (ii) если размер векторов равен, то векторы лексикографически сортируются. Для этого я написал следующий код. Но я не знаю, почему, но этот код застревает в бесконечном цикле. Может кто-то, пожалуйста, помогите мне в том, где я ошибаюсь.

#include <vector> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
typedef std::pair<std::vector<unsigned>, std::vector<unsigned> > vec_pair; 

bool sortingFunc(const pair<unsigned,vec_pair>& a, const pair<unsigned,vec_pair>& b) 
{ 
    if((a.second).second.size() == (b.second).second.size()) { 
     if(std::lexicographical_compare((a.second).second.begin(), (a.second).second.end(), (b.second).second.begin(), (b.second).second.end()))//a<b 
     { 
      return true; 
     }else{ 
      if((a.second).first.size() == (b.second).first.size()) { 
       return std::lexicographical_compare((a.second).first.begin(), (a.second).first.end(), (b.second).first.begin(), (b.second).first.end()); 
      } else { 
       // Sort by size. 
       return (a.second).first.size() < (b.second).first.size(); 
      }    
     } 
    } else { 
     // Sort by size. 
     return (a.second).second.size() < (b.second).second.size(); 
    } 
} 

int main() 
{ 
    vector<pair<unsigned, pair<vector<unsigned>, vector<unsigned> > > > sbp; 
    std::sort(sbp.begin(), sbp.end(), sortingFunc); 
} 

Я использую C++ 11 (GCC 4.8.2)

Answer 1

я хотел бы использовать std::tie или make_tuple с RValue:

bool sortingFunc(const pair<unsigned, vec_pair>& a, const pair<unsigned, vec_pair>& b) 
{ 
    return std::make_tuple(a.second.second.size(), std::ref(a.second.second), a.second.first.size(), std::ref(a.second.first)) 
     < std::make_tuple(b.second.second.size(), std::ref(b.second.second), b.second.first.size(), std::ref(b.second.first)); 
} 

Ваш случай не является правильным с

if(std::lexicographical_compare((a.second).second.begin(), (a.second).second.end(), (b.second).second.begin(), (b.second).second.end()))//a<b 
{ 
    return true; 
} 

, где он пропустил b < a состояние.

else if(std::lexicographical_compare((b.second).second.begin(), (b.second).second.end(), (a.second).second.begin(), (a.second).second.end()))//b < a 
{ 
    return true; 
} 

перед тем == состояние.

Answer 2

Проблема с кодом является то, что для этого условия:

if(std::lexicographical_compare((a.second).second.begin(), (a.second).second.end(), (b.second).second.begin(), (b.second).second.end()))//a<b 

Вы не правильно обрабатывать противоположное состояние. То есть указанная выше строка проверяет только if (a.second.second < b.second.second). Если это правда, вы возвращаете true из функции, что является правильным. Но если это неверно, вы затем продолжаете проверять условия более низкого приоритета, игнорируя возможный случай, который b.second.second может быть меньше a.second.second.

Кроме того, небольшая модификация метода std::tie Jarod42 в:

bool sortingFunc(const pair<unsigned, vec_pair>& a, const pair<unsigned, vec_pair>& b) 
{ 
    auto a1 = a.second.second.size(); 
    auto& a2 = a.second.second; 
    auto a3 = a.second.first.size(); 
    auto& a4 = a.second.first; 

    auto b1 = b.second.second.size(); 
    auto& b2 = b.second.second; 
    auto b3 = b.second.first.size(); 
    auto& b4 = b.second.first; 

    return std::tie(a1, a2, a3, a4) < std::tie(b1, b2, b3, b4); 
} 

Что std::tie делает сделать std::tuple ссылок на свои аргументы. И operator< перегружен для std::tuple, чтобы сделать лексикографическое сравнение с его элементами от первого до последнего.