sorting Archives - Page 3 of 12

사용자 정의 (즉, 사용자 정의) 객체를 포함하는 벡터를 정렬하는 방법은 무엇입니까?
아마도 표준 STL 알고리즘 정렬 은 사용자 정의 객체의 필드 중 하나에서 정렬 키로 작동하는 술어 (함수 또는 함수 객체)와 함께 정렬되어야합니다.
내가 올바른 길을 가고 있습니까?

답변

사용하는 간단한 예 std::sort

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

편집 : Kirill V. Lyadvinsky가 지적했듯이 정렬 조건자를 제공하는 대신 operator<for MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

이 방법을 사용하면 다음과 같이 벡터를 간단히 정렬 할 수 있습니다.

std::sort(vec.begin(), vec.end());

Edit2 : Kappa가 제안한 것처럼 >연산자 를 오버로드하고 정렬 호출을 약간 변경 하여 내림차순으로 벡터를 정렬 할 수도 있습니다 .

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

그리고 다음과 같이 sort를 호출해야합니다.

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

답변

적용 범위에 관심이 있습니다. 람다 식을 사용하여 구현을 진행했습니다 .

C ++ 11

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const MyStruct& lhs, const MyStruct& rhs )
{
   return lhs.key < rhs.key;
});

C ++ 14

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs )
{
   return lhs.key < rhs.key;
});

답변

functor를의 세 번째 인수로 사용 std::sort하거나 operator<클래스에서 정의 할 수 있습니다.

struct X {
    int x;
    bool operator<( const X& val ) const {
        return x < val.x;
    }
};

struct Xgreater
{
    bool operator()( const X& lx, const X& rx ) const {
        return lx.x < rx.x;
    }
};

int main () {
    std::vector<X> my_vec;

    // use X::operator< by default
    std::sort( my_vec.begin(), my_vec.end() );

    // use functor
    std::sort( my_vec.begin(), my_vec.end(), Xgreater() );
}

답변

이러한 유형 vector또는 기타 적용 가능한 (변경 가능한 입력 반복자) 범위의 사용자 정의 객체 범위를 정렬하는 것은 X다양한 방법, 특히 다음과 같은 표준 라이브러리 알고리즘을 사용하여 수행 할 수 있습니다

X요소의 상대적 순서를 얻기위한 대부분의 기술 이 이미 게시되었으므로 다양한 접근 방식을 사용하는 “왜”및 “언제”에 대한 참고로 시작하겠습니다.

“최상의”접근 방식은 다음과 같은 여러 요인에 따라 달라집니다.

X객체 범위를 정렬 하는 것이 일반적인 작업 입니까 아니면 드문 작업 입니까 (이러한 범위는 프로그램에서 또는 라이브러리 사용자별로 다양한 위치로 정렬됩니까?)
필요한 정렬이 “자연”(예상)이거나 유형을 자체와 비교할 수있는 여러 가지 방법이 있습니까?
성능에 문제가 X있습니까? 아니면 객체 범위를 완벽하게 분류해야 합니까?

정렬 범위 X가 일반적인 작업이고 달성 된 정렬이 예상되는 경우 (즉 X, 단일 기본 값을 래핑하는 경우) operator<퍼지없이 정렬 할 수 있으므로 (적절한 비교기를 올바르게 전달하는 등) 반복적으로 예상되는 수율 결과.

정렬이 일반적인 작업이거나 다른 상황에서 필요할 수 있지만 X객체 를 정렬하는 데 사용할 수있는 여러 기준이있는 경우 Functors ( operator()사용자 정의 클래스의 오버로드 된 함수) 또는 함수 포인터 (예 : 하나의 functor / 함수)를 사용합니다. 어휘 순서와 자연 순서에 대한 또 다른 순서).

유형의 정렬 범위 X가 흔하지 않거나 다른 상황에서 발생하지 않으면 더 많은 함수 또는 유형으로 네임 스페이스를 어지럽히는 대신 람다를 사용하는 경향이 있습니다.

정렬이 어떤 방식으로 “명확하지 않은”또는 “자연적인”것이 아닌 경우 특히 그렇습니다. 적절한 위치에 적용되는 람다를 볼 때 순서가 뒤에 논리를 쉽게 얻을 수 있지만 operator<처음에는 불투명하며 어떤 순서 논리가 적용 될지 알기 위해 정의를 찾아야합니다.

그러나 단일 operator<정의는 단일 장애 지점 인 반면 여러 람다는 다중 장애 지점이므로 더주의해야합니다.

operator<정렬이 완료된 곳 / 정렬 템플릿이 컴파일 된 곳에서에 대한 정의를 사용할 수없는 경우, 컴파일러는 객체를 비교할 때 심각한 단점이 될 수있는 순서 논리를 인라인하는 대신 함수 호출을 수행해야 할 수 있습니다 (적어도 링크 시간 최적화 / 코드 생성은 적용되지 않습니다).

`class X`표준 라이브러리 정렬 알고리즘을 사용하기 위해 비교할 수있는 방법

하자 std::vector<X> vec_X;및std::vector<Y> vec_Y;

1. 비교 기능이 필요하지 않은 표준 라이브러리 템플릿을 오버로드 `T::operator<(T)`하거나 `operator<(T, T)`사용하십시오.

과부하 멤버 operator<:

struct X {
  int i{};
  bool operator<(X const &r) const { return i < r.i; }
};
// ...
std::sort(vec_X.begin(), vec_X.end());

또는 무료 operator<:

struct Y {
  int j{};
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());

2. 정렬 기능 매개 변수로 사용자 정의 비교 기능이있는 함수 포인터를 사용하십시오.

struct X {
  int i{};
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);

3. `bool operator()(T, T)`비교 함수로 전달할 수있는 사용자 정의 유형에 대한 과부하를 만듭니다 .

struct X {
  int i{};
  int j{};
};
struct less_X_i
{
    bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
    bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// sort by i
std::sort(vec_X.begin(), vec_X.end(), less_X_i{});
// or sort by j
std::sort(vec_X.begin(), vec_X.end(), less_X_j{});

이러한 함수 객체 정의는 C ++ 11 및 템플릿을 사용하여 좀 더 일반적으로 작성할 수 있습니다.

struct less_i
{
    template<class T, class U>
    bool operator()(T&& l, U&& r) const { return std::forward<T>(l).i < std::forward<U>(r).i; }
};

멤버 i지원으로 모든 유형을 정렬하는 데 사용할 수 있습니다 <.

4. 분류 함수에 대한 비교 매개 변수로 익명 클로저 (lambda)를 전달하십시오.

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

C ++ 14가보다 일반적인 람다 식을 가능하게하는 경우 :

std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });

매크로에 싸여있을 수 있습니다

#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }

일반적인 비교기 생성을 매우 부드럽게 만듭니다.

// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

답변

당신은 올바른 길을 가고 있습니다. 기본적으로 비교 기능으로 std::sort사용 operator<됩니다. 따라서 객체를 정렬하려면 다음과 같이 과부하를 수행 bool operator<( const T&, const T& )하거나 비교를 수행하는 펑터를 제공해야합니다.

 struct C {
    int i;
    static bool before( const C& c1, const C& c2 ) { return c1.i < c2.i; }
 };

 bool operator<( const C& c1, const C& c2 ) { return c1.i > c2.i; }

 std::vector<C> values;

 std::sort( values.begin(), values.end() ); // uses operator<
 std::sort( values.begin(), values.end(), C::before );

functor를 사용하면 클래스의 비공개 멤버에 액세스하여 함수를 사용할 수 있다는 장점이 있습니다.

답변

std :: sort를 호출 할 수있는 다양한 방법 사이에서 성능에 측정 가능한 영향이 있는지 궁금 해서이 간단한 테스트를 만들었습니다.

$ cat sort.cpp
#include<algorithm>
#include<iostream>
#include<vector>
#include<chrono>

#define COMPILER_BARRIER() asm volatile("" ::: "memory");

typedef unsigned long int ulint;

using namespace std;

struct S {
  int x;
  int y;
};

#define BODY { return s1.x*s2.y < s2.x*s1.y; }

bool operator<( const S& s1, const S& s2 ) BODY
bool Sgreater_func( const S& s1, const S& s2 ) BODY

struct Sgreater {
  bool operator()( const S& s1, const S& s2 ) const BODY
};

void sort_by_operator(vector<S> & v){
  sort(v.begin(), v.end());
}

void sort_by_lambda(vector<S> & v){
  sort(v.begin(), v.end(), []( const S& s1, const S& s2 ) BODY );
}

void sort_by_functor(vector<S> &v){
  sort(v.begin(), v.end(), Sgreater());
}

void sort_by_function(vector<S> &v){
  sort(v.begin(), v.end(), &Sgreater_func);
}

const int N = 10000000;
vector<S> random_vector;

ulint run(void foo(vector<S> &v)){
  vector<S> tmp(random_vector);
  foo(tmp);
  ulint checksum = 0;
  for(int i=0;i<tmp.size();++i){
     checksum += i *tmp[i].x ^ tmp[i].y;
  }
  return checksum;
}

void measure(void foo(vector<S> & v)){

ulint check_sum = 0;

  // warm up
  const int WARMUP_ROUNDS = 3;
  const int TEST_ROUNDS = 10;

  for(int t=WARMUP_ROUNDS;t--;){
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
  }

  for(int t=TEST_ROUNDS;t--;){
    COMPILER_BARRIER();
    auto start = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
    auto end = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    auto duration_ns = std::chrono::duration_cast<std::chrono::duration<double>>(end - start).count();

    cout << "Took " << duration_ns << "s to complete round" << endl;
  }

  cout << "Checksum: " << check_sum << endl;
}

#define M(x) \
  cout << "Measure " #x " on " << N << " items:" << endl;\
  measure(x);

int main(){
  random_vector.reserve(N);

  for(int i=0;i<N;++i){
    random_vector.push_back(S{rand(), rand()});
  }

  M(sort_by_operator);
  M(sort_by_lambda);
  M(sort_by_functor);
  M(sort_by_function);
  return 0;
}

그것이하는 것은 랜덤 벡터를 생성 한 다음, 그것을 복사하고 그것을 복사하는 데 얼마나 많은 시간이 필요한지를 측정하는 것입니다 (그리고 너무 강력한 데드 코드 제거를 피하기 위해 체크섬을 계산하십시오).

g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)로 컴파일했습니다.

$ g++ -O2 -o sort sort.cpp && ./sort

결과는 다음과 같습니다.

Measure sort_by_operator on 10000000 items:
Took 0.994285s to complete round
Took 0.990162s to complete round
Took 0.992103s to complete round
Took 0.989638s to complete round
Took 0.98105s to complete round
Took 0.991913s to complete round
Took 0.992176s to complete round
Took 0.981706s to complete round
Took 0.99021s to complete round
Took 0.988841s to complete round
Checksum: 18446656212269526361
Measure sort_by_lambda on 10000000 items:
Took 0.974274s to complete round
Took 0.97298s to complete round
Took 0.964506s to complete round
Took 0.96899s to complete round
Took 0.965773s to complete round
Took 0.96457s to complete round
Took 0.974286s to complete round
Took 0.975524s to complete round
Took 0.966238s to complete round
Took 0.964676s to complete round
Checksum: 18446656212269526361
Measure sort_by_functor on 10000000 items:
Took 0.964359s to complete round
Took 0.979619s to complete round
Took 0.974027s to complete round
Took 0.964671s to complete round
Took 0.964764s to complete round
Took 0.966491s to complete round
Took 0.964706s to complete round
Took 0.965115s to complete round
Took 0.964352s to complete round
Took 0.968954s to complete round
Checksum: 18446656212269526361
Measure sort_by_function on 10000000 items:
Took 1.29942s to complete round
Took 1.3029s to complete round
Took 1.29931s to complete round
Took 1.29946s to complete round
Took 1.29837s to complete round
Took 1.30132s to complete round
Took 1.3023s to complete round
Took 1.30997s to complete round
Took 1.30819s to complete round
Took 1.3003s to complete round
Checksum: 18446656212269526361

함수 포인터 전달을 제외한 모든 옵션은 매우 유사하며 함수 포인터를 전달하면 + 30 %의 패널티가 발생합니다.

또한 operator <버전이 ~ 1 % 더 느린 것처럼 보입니다 (테스트를 여러 번 반복하고 효과가 지속됨). 생성 된 코드가 다르다는 것을 제안하기 때문에 약간 이상합니다 (분석 할 기술이 부족합니다 –save- 온도 출력).

답변

예, std::sort()세 번째 매개 변수 (함수 또는 객체)가 더 쉽습니다. 예 :
http://www.cplusplus.com/reference/algorithm/sort/

IT HOW

무엇이는 물어보세요

태그 보관물: sorting

사용자 객체의 벡터 정렬 정렬하는 방법은 무엇입니까? 아마도 표준 STL 알고리즘

답변

답변

답변

답변

`class X`표준 라이브러리 정렬 알고리즘을 사용하기 위해 비교할 수있는 방법

1. 비교 기능이 필요하지 않은 표준 라이브러리 템플릿을 오버로드 `T::operator<(T)`하거나 `operator<(T, T)`사용하십시오.

2. 정렬 기능 매개 변수로 사용자 정의 비교 기능이있는 함수 포인터를 사용하십시오.

3. `bool operator()(T, T)`비교 함수로 전달할 수있는 사용자 정의 유형에 대한 과부하를 만듭니다 .

4. 분류 함수에 대한 비교 매개 변수로 익명 클로저 (lambda)를 전달하십시오.

답변

답변

답변

답변

답변

답변

답변

class X표준 라이브러리 정렬 알고리즘을 사용하기 위해 비교할 수있는 방법

1. 비교 기능이 필요하지 않은 표준 라이브러리 템플릿을 오버로드 T::operator<(T)하거나 operator<(T, T)사용하십시오.

2. 정렬 기능 매개 변수로 사용자 정의 비교 기능이있는 함수 포인터를 사용하십시오.

3. bool operator()(T, T)비교 함수로 전달할 수있는 사용자 정의 유형에 대한 과부하를 만듭니다 .

4. 분류 함수에 대한 비교 매개 변수로 익명 클로저 (lambda)를 전달하십시오.

답변

답변

답변

`class X`표준 라이브러리 정렬 알고리즘을 사용하기 위해 비교할 수있는 방법

1. 비교 기능이 필요하지 않은 표준 라이브러리 템플릿을 오버로드 `T::operator<(T)`하거나 `operator<(T, T)`사용하십시오.

3. `bool operator()(T, T)`비교 함수로 전달할 수있는 사용자 정의 유형에 대한 과부하를 만듭니다 .