cdeclog

std::sort 는 qsort 보다 빠르다 #

1. 비교 함수의 리턴값
   
   • <qsort>
     
     qsort의 비교함수 리턴 값은 int type 입니다.
     그러므로 결과는 3가지 종류이죠
     
     a < b -> -1
     a > b -> 1
     a = b -> 0
     
     그러므로 적어두 2번을 비교 해야 합니다.
     
     
     
   • <sort>
     
     sort의 비교함수 리턴 값은 bool type이입니다.
     그러므로 1번만 비교 하면 되는것이져
     
     

        template <typename T>
        bool comp(const T &a, const T &b) {
            return a < b  // a가 b보다 작으면 참 아니면 거짓 
        }
     

     
     
     
2. 비교함수의 inlining
   
   • <qsort>
     
     비교자를 함수로 밖에 못넘기기때문에 함수호출로 인한 오버헤드는 불가피 합니다.
     만약 비교함수를 inline으로 선언해도 함수 포인터를 사용 하므로 무시됩니다.
     (inline및 register는 힌트이기 때문에 컴파일러의 사정에 따라 무시될수 있습니다. 야속하게도 ...)
     
     
   • <sort>
     
     비교함수및 sort함수가 template으로 구성되어서 함수및 함수객체(functor)를 비교자로서 넣을수 있습니다.
     함수로 넣으면 qsort와 같은 오버헤드가 발생 하겠지만 함수객체로 만들면 inlining이 가능하게 만듭니다.
     
     
     

     
     
3. swap 함수의 대입
   
   • <qsort>
     
     qsort의 swap함수는 void*로 인수를 받기 때문에 실제 데이터의 크기과 정보를 알수가 없습니다
     그래서 qsort함수의 3번째 인자(데이터의 크기)를 기준으로 객체의 혹은 타입의 크기만큼 전체 복사를
     하게 구현 됩니다.
     
     
     
   • <sort>
     
     sort함수의 경우는 복사입니다 (template 때문에 가능하져)
     
     

        template <typename T>
        void swap(T &a, T &b) {
            T t = a;
            a = b;
            b = a'
        }
     

     
     그러기 때문에 프로그래머의 데이터 객체의 대입연산자 구현에 따라
     성능은 많이 나아질 여지가 충분한것이져
     
     거기다가 데이터 자체가 Reference Counting이 된는 객체라면
     그 성능은 월등할것 입니다.