순서 사전 체인 (예 : std :: sort)

StackOverflow https://stackoverflow.com/questions/274951

문제

함수 포인터, 함수 객체 (또는 람다 부스트 람다)를 std :: 정렬하여 정렬하려는 컨테이너 요소의 엄격한 약한 순서를 정의 할 수 있습니다.

그러나 때로는 (여러 번 이번에도 쳤을 정도로) "원시적"비교를 체인 할 수 있기를 원합니다.

연락처 데이터를 나타내는 객체 모음을 정렬하는 경우 사소한 예입니다. 때때로 당신은 분류하고 싶을 것입니다 

last name, first name, area code
. 다른 시간 
first name, last name
- 아직 다른 시간 
age, first name, area code
... 등

이제 각 사례에 대해 추가 기능 객체를 쓸 수 있지만, 특히 각 비교가 덜 사소한 경우 건조 원칙을 위반합니다.

비교 함수의 계층 구조를 작성할 수 있어야하는 것 같습니다. 낮은 레벨은 단일, 원시적 비교 (예 : 이름 <이름)를 수행하면 더 높은 레벨을 연속적으로 호출합니다 (아마 && 단락 평가를 사용하려면 복합 기능을 생성합니다.

이 접근법의 문제점은 STD :: 정렬이 이진 술어를 가져옵니다. 술어는 부울 만 반환 할 수 있다는 것입니다. 따라서 구성하는 경우 "거짓"이 평등을 나타내는 지 또는 더 큰지 알 수 없습니다. 당신은 당신의 하위 레벨 predicates가 3 개의 상태로 INT를 반환하게 할 수 있지만, std :: 정렬과 함께 사용되기 전에 더 높은 수준의 곤경에 처한 사람들을 포장해야합니다.

전혀, 이것들은 극복 할 수없는 문제가 아닙니다. 그것은 단지 더 어려워 보입니다. 그리고 확실히 도우미 라이브러리 구현을 초대합니다.

따라서 여기서 기존 도서관 (STD 또는 부스트 라이브러리라면)을 도울 수있는 도서관 (esp.)을 아는 사람이 있습니까?

업데이트

일부 의견에서 언급했듯이 - 나는 이것을 관리하기 위해 수업의 구현을 계속 작성했습니다. 상당히 최소화되어 있으며 일반적으로 몇 가지 문제가있을 수 있습니다. 그러나 관심있는 사람이라면 누구나 수업이 여기에 있습니다.

http://pastebin.com/f52a85e4f

그리고 일부 도우미 기능 (템플릿 Args를 지정할 필요가 없음)은 다음과 같습니다.

http://pastebin.com/fa03d66e

도움이 되었습니까?

해결책

그렇게 작은 체인 시스템을 구축 할 수 있습니다.

struct Type {
  string first, last;
  int age;
};

struct CmpFirst {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.first < rhs.first; }
};

struct CmpLast {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.last < rhs.last; }
};

struct CmpAge {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.age < rhs.age; }
};

template <typename First, typename Second>
struct Chain {
  Chain(const First& f_, const Second& s_): f(f_), s(s_) {}

  bool operator () (const Type& lhs, const Type& rhs) {
    if(f(lhs, rhs))
      return true;
    if(f(rhs, lhs))
      return false;

    return s(lhs, rhs);
  }

  template <typename Next>
  Chain <Chain, Next> chain(const Next& next) const {
     return Chain <Chain, Next> (*this, next);
  }

  First f;
  Second s;
};

struct False { bool operator() (const Type& lhs, const Type& rhs) { return false; } };

template <typename Op>
Chain <False, Op> make_chain(const Op& op) { return Chain <False, Op> (False(), op); }

그런 다음 사용하십시오 :

vector <Type> v;  // fill this baby up

sort(v.begin(), v.end(), make_chain(CmpLast()).chain(CmpFirst()).chain(CmpAge()));

마지막 줄은 약간의 장점이지만 의도 한 것이 분명하다고 생각합니다.

다른 팁

이것을 처리하는 한 가지 기존의 방법은 여러 패스로 정렬하고 안정적인 종류를 사용하는 것입니다. 그것을주의해라 std::sort 일반적으로 ~ 아니다 안정적인. 그러나 거기 있습니다 std::stable_sort.

즉, 나는 트리 스테이트를 반환하는 함수 주위에 래퍼를 쓸 것입니다 (더 적은, 평등, 더 큰).

당신은 이것을 시도 할 수 있습니다 :

용법:

struct Citizen {
    std::wstring iFirstName;
    std::wstring iLastName;
};

ChainComparer<Citizen> cmp;
cmp.Chain<std::less>( boost::bind( &Citizen::iLastName, _1 ) );
cmp.Chain<std::less>( boost::bind( &Citizen::iFirstName, _1 ) );

std::vector<Citizen> vec;
std::sort( vec.begin(), vec.end(), cmp );

구현:

template <typename T>
class ChainComparer {
public:

    typedef boost::function<bool(const T&, const T&)> TComparator;
    typedef TComparator EqualComparator;
    typedef TComparator CustomComparator;

    template <template <typename> class TComparer, typename TValueGetter>
    void Chain( const TValueGetter& getter ) {

        iComparers.push_back( std::make_pair( 
            boost::bind( getter, _1 ) == boost::bind( getter, _2 ), 
            boost::bind( TComparer<TValueGetter::result_type>(), boost::bind( getter, _1 ), boost::bind( getter, _2 ) ) 
        ) );
    }

    bool operator()( const T& lhs, const T& rhs ) {
        BOOST_FOREACH( const auto& comparer, iComparers ) {
            if( !comparer.first( lhs, rhs ) ) {
                return comparer.second( lhs, rhs );
            }
        }

        return false;
    }

private:
    std::vector<std::pair<EqualComparator, CustomComparator>> iComparers;
};

std::sort 안정적인 종류는 일반적으로 안정적인 것보다 느리기 때문에 안정성이 보장되지 않습니다 ... 따라서 안정적인 종류를 여러 번 사용하는 것은 성능 문제를위한 레시피처럼 보입니다 ...

그리고 그렇습니다. 정렬이 술어를 요구하는 것은 정말 부끄러운 일입니다. 나는 Tristate 함수의 벡터를 받아들이는 기능을 만드는 것 외에 다른 방법을 본다 ...

사슬 솔루션은 장점입니다. std :: logical_와 함께 boost :: bind를 사용하여 정렬 술어를 구축 할 수도 있습니다. 자세한 내용은 링크 된 기사를 참조하십시오. Boost 바인드 라이브러리가 C ++ 프로그램을 향상시킬 수있는 방법

C ++ 11의 변수 템플릿은 더 짧은 옵션을 제공합니다.

    #include <iostream>
    using namespace std;

    struct vec { int x,y,z; };

    struct CmpX {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.x < rhs.x; }
    };

    struct CmpY {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.y < rhs.y; }
    };

    struct CmpZ {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.z < rhs.z; }
    };

    template <typename T>
    bool chained(const T &, const T &) {
      return false;
    }

    template <typename CMP, typename T, typename ...P>
    bool chained(const T &t1, const T &t2, const CMP &c, P...p) {
      if (c(t1,t2)) { return true;          }
      if (c(t2,t1)) { return false;         }
      else          { return chained(t1, t2, p...); }
    }

    int main(int argc, char **argv) {
      vec x = { 1,2,3 }, y = { 2,2,3 }, z = { 1,3,3 };
      cout << chained(x,x,CmpX(),CmpY(),CmpZ()) << endl;
      return 0;
    }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top