STL 시리즈 의 6 set 와 hashset

set 와 hashset 는 STL 에서 비교적 중요 한 용기 이 므 로 이 를 깊이 이해 할 필요 가 있다.STL 에서 set 는 빨 간 검 은 나무 (RB - tree) 를 바 텀 데이터 구조 로 하 는 'hash' 입 니 다.set 는 Hash table (해시 표) 을 바 텀 데이터 구조 로 합 니 다.set 는 시간 복잡 도가 O (logN) 인 상황 에서 데 이 터 를 삽입, 삭제, 찾 을 수 있 습 니 다.hash_set 작업 의 시간 복잡 도 는 비교적 복잡 하 다. 이것 은 해시 함수 와 해시 표 의 부하 상황 에 달 려 있다.다음은 set 와 hashset 의 상용 함수: set 와 haseset 의 더 많은 함 수 는 MSDN 을 찾 아 보 세 요.
set 의 사용 사례 는 다음 과 같 습 니 다 (hash set 유사).

// by MoreWindows( http://blog.csdn.net/MoreWindows )
#include 
#include 
#include 
using namespace std;

int main()
{
    printf("--set   by MoreWindows( http://blog.csdn.net/MoreWindows ) --

");
    const int MAXN = 15;
    int a[MAXN];
    int i;
    srand(time(NULL));
    for (i = 0; i < MAXN; ++i)
        a[i] = rand() % (MAXN * 2);

    set<int> iset;   
    set<int>::iterator pos; 

    //     insert()     
    iset.insert(a, a + MAXN);

    //               
    printf("       : %d            : %d
", iset.size(), iset.max_size());

    //    
    printf("           -------
");
    for (pos = iset.begin(); pos != iset.end(); ++pos)
        printf("%d ", *pos);
    putchar('
');

    //  
    int findNum = MAXN;
    printf("   %d    -----------------------
", findNum);
    pos = iset.find(findNum);
    if (pos != iset.end())
        printf("%d   
", findNum);
    else
        printf("%d    
", findNum);

    //         ，          ，                
    pos  = iset.insert(--iset.end(), MAXN * 2); 
    printf("    %d
", *pos);

    //  
    iset.erase(MAXN);
    printf("    %d
", MAXN);

    //    
    printf("           -------
");
    for (pos = iset.begin(); pos != iset.end(); ++pos)
        printf("%d ", *pos);
    putchar('
');
    return 0;
}

실행 결 과 는 다음 과 같 습 니 다.
set 에서 클래스 를 사용 해 보 겠 습 니 다.이 종 류 는 매우 간단 합 니 다. 하나의 구성원 변수 와 이 구성원 변 수 를 설정 하고 가 져 오 는 구성원 함수 만 있 습 니 다.

// set       ‘
// by MoreWindows( http://blog.csdn.net/MoreWindows )
#include 
#include 
#include 
using namespace std;
class Node
{
public:
    Node(int nAge = 0)
    {
        m_nAge = nAge;
    }
    Node(const Node &na)  //      
    {
        m_nAge = na.GetAge();
    }
    int GetAge()
    {
        return m_nAge;
    }
private:
    int m_nAge;
};
//          
inline bool operator < (const Node &na, const Node &nb) 
{
    return na.GetAge() < nb.GetAge();
}
int main()
{
    int i;
    set nset;
    for (i = 0; i < MAXN; ++i)
        nset.insert(Node(i));
    return 0;
}

컴 파일, 바로 세 개의 오 류 를 신 고 했 습 니 다!!1 개 는 구조 함 수 를 복사 하고 2 개 는 operator 에서 3 개의 오 류 는 모두 같 습 니 다.
error C2662: "Node: GetAge": "this" 지침 을 "const Node" 에서 "Node &" 로 변환 할 수 없습니다.
이거 어떻게 된 거 야?분석 하에 복사 구조 함수 와 operator

       int GetAge()  const //    const
       {
              returnm_nAge;
       }

다시 번역 하면 잘못 보고 하지 않 는 다.자 료 를 다시 찾 아 보 세 요. 그 이 유 는 다음 과 같 습 니 다. 그 두 함수 가 모두 const 수식 대상 을 사 용 했 기 때 문 입 니 다. 그러나 GetAge () 는 const 를 추가 하지 않 아 대상 을 수정 하지 않 았 습 니 다. 컴 파일 러 는 이러한 쓰기 가 안전 하지 않다 고 생각 하여 오 류 를 보고 하 는 것 을 주저 하지 않 았 습 니 다.
이런 잘못 을 직접 체험 하지 않 으 면 필기시험 면접 에서 잘못된 절 차 를 썼 을 가능성 이 높 고 자신 은 아직 아무것도 모 르 는 상태 에 처 해 있다.또한 VC 6.0 을 사용 하면 '잃 어 버 린 한정 자 변환' 이라는 상세 한 오류 정 보 를 알려 주지 않 습 니 다.
STL 은 set 에 집합 연산 함수 도 제공 합 니 다. 예 를 들 어 집합 setintersection (), 집합 setunion (), 차 집합 setdifference () 와 대칭 차 집합 setsymmetric_difference()。이것들 은 상세 하 게 소개 하지 않 겠 으 니, 흥미 가 있 으 면 직접 해 봐 도 된다.
다음은 set 와 hashset 개성 테스트 (Win 7 + VS 2008 Release 아래).
테스트 코드 는 다음 과 같 습 니 다:

// by MoreWindows( http://blog.csdn.net/MoreWindows )
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
using namespace stdext;  //hash_set

// MAXN    MAXQUERY   
const int MAXN = 10000, MAXQUERY = 5000000;
int a[MAXN], query[MAXQUERY];

void PrintfContainertElapseTime(char *pszContainerName, char *pszOperator, long lElapsetime)
{
    printf("%s  %s      %d  
", pszContainerName, pszOperator, lElapsetime);
}

int main()
{
    printf("set VS hash_set           %d       %d 
", MAXN, MAXQUERY);
    const int MAXNUM = MAXN * 4;
    const int MAXQUERYNUM = MAXN * 4;
    printf("        [0, %d)       [0, %d)
", MAXNUM, MAXQUERYNUM);
    printf("--by MoreWindows( http://blog.csdn.net/MoreWindows ) --

");

    //     [0, MAXNUM)    MAXN  
    int i;
    srand(time(NULL));
    for (i = 0; i < MAXN; ++i)
        a[i] = (rand() * rand()) % MAXNUM;
    //     [0, MAXQUERYNUM)    MAXQUERY  
    srand(time(NULL));
    for (i = 0; i < MAXQUERY; ++i)
        query[i] = (rand() * rand()) % MAXQUERYNUM;

    set<int>       nset;
    hash_set<int> nhashset;
    clock_t  clockBegin, clockEnd;


    //insert
    printf("-----    -----------
");

    clockBegin = clock();  
    nset.insert(a, a + MAXN); 
    clockEnd = clock();
    printf("set    %d 
", nset.size());
    PrintfContainertElapseTime("set", "insert", clockEnd - clockBegin);

    clockBegin = clock();  
    nhashset.insert(a, a + MAXN); 
    clockEnd = clock();
    printf("hash_set    %d 
", nhashset.size());
    PrintfContainertElapseTime("hase_set", "insert", clockEnd - clockBegin);


    //find
    printf("-----    -----------
");

    int nFindSucceedCount, nFindFailedCount; 
    nFindSucceedCount = nFindFailedCount = 0;
    clockBegin = clock(); 
    for (i = 0; i < MAXQUERY; ++i)
        if (nset.find(query[i]) != nset.end())
            ++nFindSucceedCount;
        else
            ++nFindFailedCount;
    clockEnd = clock();
    PrintfContainertElapseTime("set", "find", clockEnd - clockBegin);
    printf("      ： %d          ： %d
", nFindSucceedCount, nFindFailedCount);

    nFindSucceedCount = nFindFailedCount = 0;
    clockBegin = clock();  
    for (i = 0; i < MAXQUERY; ++i)
        if (nhashset.find(query[i]) != nhashset.end())
            ++nFindSucceedCount;
        else
            ++nFindFailedCount;
    clockEnd = clock();
    PrintfContainertElapseTime("hash_set", "find", clockEnd - clockBegin);
    printf("      ： %d          ： %d
", nFindSucceedCount, nFindFailedCount);
    return 0;
}

데이터 용량 100 만, 조회 횟수 500 만 시 프로그램 실행 결 과 는 다음 과 같 습 니 다. 조회 실패 횟수 가 너무 많 기 때문에 이번 에는 조회 범 위 를 작 게 사용 하고 테스트 합 니 다.
결점 이 너무 많 고 80 여 만 개의 결점 으로 인해 set 의 붉 은 검 은 나무 높이 는 약 19 (2 ^ 19 = 524288, 2 ^ 20 = 1048576) 이 므 로 조회 하기 에는 시간 이 비교적 걸린다.hash_set 는 시간 성능 이 set 보다 좋 고 조회 성공 확률 이 높 으 면 hashset 가 더 잘 할 거 예요.왜 hashset 는 우수한 성능 을 나 타 낼 수 있 습 니 다. 계 집 인 을 보십시오.
주 1 MSDN 에서 set 의 erase () 는 반환 값 이 있 지만 VS 2008 에서 set 의 소스 코드 를 보 았 습 니 다. erase () 함수 의 세 개의 리 셋 버 전에 서 두 개의 반환 값 은 모두 void 즉 반환 값 이 없 으 며 다른 하 나 는 size 를 되 돌려 줍 니 다.type。 통과 가능http://msdn.microsoft.com/zh-cn/library/8h4a3515(v = VS. 90). aspx 는 MSDN 에서 set 에 대한 erase () 설명 을 봅 니 다.
http://blog.csdn.net/morewindows/article/details/7029587