정렬 된 벡터의 서브 세트 정렬

Question

여러 기준에 따라 배열을 정렬하는 가장 좋은 방법을 찾으려고합니다. 배열을 정렬 한 다음 첫 번째 조건에서 같으면 해당 배열의 하위 집합을 정렬합니다.

예 :

{ ("cat", 2), ("cat", 1), ("dog", 4), ("dog", 3) }

그런 다음 우리는 두 부분 집합을 분류 (설정 : { ("cat", 2), ("dog", 4), ("cat", 1), ("dog", 3) }

우리는 문자열의 알파벳 순서에 따라 첫 번째 분류 :

우리가 데이터를 말해봐 고양이와 개 세트)를 숫자의 순서대로 증가시킵니다.

왼쪽과 오른쪽

void quickSort(vector<Type*>, int left, int right) 

은 벡터 정렬해야하는 경계 지표입니다 :

또한, 나는 다음과 같은 헤더가 재귀 퀵 방법을 사용하고 있습니다.

정렬 메서드 자체에 코드를 추가해야합니까, 아니면 어떻게 든 정렬 메서드를 다시 호출해야합니까?

Answer 1

일반적으로 사용자 지정 비교 프로그램을 정렬해야합니다.

struct Foo { 
    std::string name; 
    int count; 
    struct Less { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     if ((int c = lhs.name.compare(rhs.name)) != 0) 
     return c < 0; 
     return lhs.count < rhs.count; 
    } 
    }; 
}; 

std::vector<Foo> foos; 
// ... 
std::sort(foos.begin(), foos.end(), Foo::Less()); 

단일 사용자 정의 연산자 만 사용할 수없는 경우 안정적인 정렬을 사용할 수 있습니다.

으로는 std::sort하지 안정적인 종류의 입니다 마크에 의해 지적했다. 대신 std::stable_sort을 사용해야합니다.

중요도가 증가하는 순서로 독립적으로 정렬하려고합니다. 그래서 숫자로 정렬 한 다음 문자열로 정렬합니다.

struct Foo { 
    std::string name; 
    int count; 
    struct NameLess { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     return lhs.name.compare(rhs.name) < 0; 
    } 
    }; 
    struct CountLess { 
    bool operator()(const Foo &lhs, const Foo &rhs) const { 
     return lhs.count < rhs.count; 
    } 
    }; 
}; 

std::vector<Foo> foos; 
// ... 
std::stable_sort(foos.begin(), foos.end(), Foo::CountLess()); 
std::stable_sort(foos.begin(), foos.end(), Foo::NameLess()); 

당신은 분명히 첫째을 선호하지만, 후자는 조합 유지를 위해 유용하게 및/또는 런타임 구성 알고리즘을 단순화 할 수 있습니다. vector.sort 다음

cplusplus.com C++ : Reference : STL Algorithms : stable_sort

cplusplus.com C++ : Reference : STL Algorithms : sort

Answer 2

당신이 vector<pair<string, int> >로 데이터를 저장하는 경우에 당신은 단지 std::sort(vec.begin(), vec.end());를 사용할 수 있으며 pair의 operator< 이미 정렬을 수행하는 객체의 두 부분을 사용하기 때문에 그냥 작동합니다.

Answer 3

당신이 다음 vector.unique을 (사용할 수 있습니다 귀하의 < 연산자를 오버로드 할 수있다)과 경우()

Answer 4

: 참고로

당신은 데이터를 믹싱하고 있기 때문에 사용자 정의 비교기가 필요합니다. 비교기가 비교할 수없는 타입은 동일한 데이터 타입만을 비교할 수 있습니다. 어떤 기준으로 당신을 알지 못합니다. 정렬 할 것입니다.