C++에서 4 중 구조체를 효율적으로 정렬하려면 어떻게해야합니까?

Question

회원 x, y, z 및 w가있는 구조체가 있습니다. 어떻게 효율적으로 정렬합니까 x에 의해 다음 y에 의해 z에 의해 그리고 마지막으로 승에 의해 C + +에서?

Answer 1

사전 식 순서를 구현하려면 가장 간단한 방법은 std::tie을 사용하여보다 작거나 큰 비교 연산자 또는 펑터를 구현 한 다음 구조체 컬렉션에 std::sort을 사용하는 것입니다. Foo의 자연 순서가없는 경우

struct Foo 
{ 
    T x, y, z, w; 
}; 

....  
#include <tuple> // for std::tie 

bool operator<(const Foo& lhs, const Foo& rhs) 
{ 
    // assumes there is a bool operator< for T 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

.... 

#include <algorithm> // for std::sort 

std::vector<Foo> v = ....; 
std::sort(v.begin(), v.end()); 

, 대신 비교 연산자를 구현하는 비교 펑터를 정의하는 것이 더있을 수 있습니다. 그런 종류의 이러한 전달할 수 있습니다 : 당신이 C++ 11 tuple 지원이없는 경우

bool cmp_1(const Foo& lhs, const Foo& rhs) 
{ 
    return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w); 
} 

std::sort(v.begin(), v.end(), cmp_1); 

, 당신이 사용 std::tr1::tie (사용 헤더 <tr1/tuple>) 또는 boost.tuple library에서 boost::tie를 사용하여 구현할 수 있습니다.

Answer 2

std::tie을 사용하여 구조체를 std::tuple으로 바꿀 수 있으며 사전 식 비교 std::tuple::operator<을 사용할 수 있습니다. 여기 std::sort

#include <algorithm> 
#include <tuple> 
#include <vector> 

struct S 
{ 
    // x, y, z, w can be 4 different types! 
    int x, y, z, w; 
}; 

std::vector<S> v; 

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) { 
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w); 
}); 

이 예 즉석 비교 연산자 std:sort 공급 람다를 사용하는 예이다. 사전 편집 비교를 항상 사용하려는 경우 std::sort으로 자동 선택되거나 std::set 및 std::map과 같은 정렬 된 연관 컨테이너로 비회원 bool operator<(S const&, S const&)을 작성할 수 있습니다. online reference에서 효율 대하여

:

모든 비교 연산자 단락; 비교 결과를 결정하는 데 필요한 것 이상의 튜플 에 액세스하지 않습니다.

C++ 11 환경을 사용하는 경우 여기에 제시된 직접 작성 솔루션보다 std::tie을 선호합니다. 그들은 오류가 발생하기 쉽고 읽기 쉽지 않습니다.

Answer 3

비교 연산자를 굴리면 객체를 std::map으로 자유롭게 던지거나 std::sort을 호출 할 수 있습니다. 이 구현은 단순하도록 설계되었으므로 필요한 경우 쉽게 확인하고 수정할 수 있습니다. operator<을 x, y, z 및 w와 비교하는 것만으로 변수가 이미 비교 가능하지 않은 경우 구현해야 할 연산자 수를 최소화합니다 (예 : int, double, std가 아닌 자신의 구조체 인 경우). 문자열 등).

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    if (lhs.x < rhs.x) return true; 
    if (rhs.x < lhs.x) return false; 
    if (lhs.y < rhs.y) return true; 
    if (rhs.y < lhs.y) return false; 
    if (lhs.z < rhs.z) return true; 
    if (rhs.z < lhs.z) return false; 
    if (lhs.w < rhs.w) return true; 
    return false; 
} 

때때로 유형 ==, <=, <의 구현을 지원하기 위해보다 작음 방법으로 모두 동일하거나보다 큰 나타낼 -1, 0 또는 1을 반환 비교 함수를 정의하고, != , >= 및 > 일 때와 마찬가지로 <을 수행하면 != 또는 >이 많은 작업을 반복합니다 (마지막 문자 만 다른 긴 텍스트 문자열 비교를 고려하십시오).x가, y는, Z와 w는 유형이 될 일이 더 높은 성능의 기능을 비교하는 경우, 당신은 아마도 전반적인 성능을 향상시킬 수

bool operator<(const Q& lhs, const Q& rhs) 
{ 
    int c; 
    return (c = lhs.x.compare(rhs.x) ? c : 
      (c = lhs.y.compare(rhs.y) ? c : 
      (c = lhs.z.compare(rhs.z) ? c : 
      lhs.w < rhs.w; 
} 

Answer 4

이 솔루션을 당 대부분 4 개 비교에서 요소-비교 정렬 특히 _efficient_가 (당신이 요청으로) 정렬 된 값의 범위에 따라 얼마나 많은 것은 그들에 대해 알려진하는 방법을 결정하는 모든 종류의와 마찬가지로

// using function as comp 
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b) 
{ 
    if (a.x != b.x) 
     return a.x < b.x; 

    if (a.y != b.y) 
     return a.y < b.y; 

    if (a.z != b.z) 
     return a.z < b.z; 

    return a.w < b.w; 
});