STL - set - 용법

7872 단어 학습 노트STL
set 집합 용 기 는 빨 간 검 은 나무 (Red - Black Tree) 의 균형 적 인 이 진 트 리 의 데이터 구 조 를 실현 합 니 다. 요 소 를 삽입 할 때 이 진 트 리 의 배열 을 자동 으로 조정 하고 이 요 소 를 적당 한 위치 에 두 어 모든 하위 트 리 노드 의 키 가 왼쪽 트 리 의 모든 노드 의 키 보다 크 고 오른쪽 트 리 의 모든 노드 의 키 보다 작 도록 합 니 다.또한 뿌리 노드 의 왼쪽 서브 트 리 의 높이 가 글자 수의 높이 와 같 도록 확보 해 야 한다. 그러면 이 진 트 리 의 높이 가 가장 작 아 검색 속도 가 가장 빠르다.주의해 야 할 것 은 같은 키 의 요 소 를 반복 해서 삽입 하지 않 고 무시 하 는 것 입 니 다.
        균형 이 잡 힌 이 진 트 리 검색 은 중간 순서 로 알고리즘 을 사용 하고 검색 효율 은 vector, deque, list 용기 보다 높 습 니 다.또한, 중간 순서 로 알고리즘 을 사용 하면 키 값 을 작은 것 에서 큰 것 으로 옮 겨 다 닐 수 있 기 때문에 균형 적 인 이 진 트 리 가 요 소 를 삽입 할 때 요소 버튼 값 을 작은 것 에서 큰 순서 로 배열 하 는 것 으로 이해 할 수 있 습 니 다.
        set 집합 을 구성 하 는 주요 목적 은 빠 른 검색 을 위해 set 를 사용 하기 전에 프로그램 헤더 파일 에 '\ # include' 라 는 성명 을 포함해 야 합 니 다.
set 의 각 구성원 함수 목록 은 다음 과 같 습 니 다.
c + stl 용기 set 구성원 함수: begin () -- 첫 번 째 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: clear () -- 모든 요 소 를 제거 합 니 다.
c + stl 용기 set 구성원 함수: count () -- 특정한 값 요소 의 개 수 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: empty () -- 집합 이 비어 있 으 면 true 로 돌아 갑 니 다.
c + stl 용기 set 구성원 함수: end () -- 마지막 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: equalrange () -- 집합 에서 주어진 값 과 같은 상하 한 을 되 돌려 주 는 두 개의 교체 기
c + stl 용기 set 구성원 함수: erase () -- 집합 요소 삭제
c + stl 용기 set 구성원 함수: find () - 찾 은 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: getallocator () -- 집합 을 되 돌려 주 는 분배 기
c + stl 용기 set 구성원 함수: insert () -- 집합 에 요 소 를 삽입 합 니 다.
c + stl 용기 set 구성원 함수: lowerbound () - 특정한 값 보다 큰 첫 번 째 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: keycomp () - 요소 간 값 비교 에 사용 할 함 수 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: maxsize () -- 집합 에 수용 할 수 있 는 요소 의 최대 한 도 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: rbegin () -- 집합 에서 마지막 요 소 를 가리 키 는 역방향 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: rend () -- 집합 에서 첫 번 째 요 소 를 가리 키 는 역방향 교체 기 를 되 돌려 줍 니 다.
c + stl 용기 set 구성원 함수: size () - 집합 요소 의 수
c + stl 용기 set 구성원 함수: swap () -- 두 개의 집합 변 수 를 교환 합 니 다.
c + stl 용기 set 구성원 함수: upperbound () -- 어떤 값 보다 큰 요 소 를 되 돌려 주 는 교체 기
c + stl 용기 set 구성원 함수: valuecomp () -- 원소 간 의 값 을 비교 하 는 함수 되 돌려 주기
1. set 집합 대상 만 들 기
           set 대상 을 만 들 때 요소 의 종 류 를 지정 해 야 합 니 다. 이 점 은 다른 용기 와 같 습 니 다.
4. 567913. 2. 요소 의 삽입 과 중간 순 서 를 옮 겨 다 닌 다.
        inset () 방법 으로 요 소 를 집합 에 삽입 합 니 다. 삽입 규칙 은 기본 적 인 비교 규칙 에서 요소 값 에 따라 작은 것 부터 큰 것 까지 삽입 합 니 다. 만약 에 자신 이 비교 규칙 함 수 를 지정 하면 사용자 정의 비교 규칙 함수 에 따라 삽입 합 니 다.앞 방향 교체 기 를 사용 하여 집합 중 순 서 를 옮 겨 다 녔 는데 결 과 는 바로 요소 정렬 후의 결과 입 니 다.
원소 의 방향 이 널리 퍼지다
        역방향 교체 기 reverse 사용iterator 는 역방향 으로 집합 할 수 있 습 니 다. 출력 결 과 는 집합 요소 의 역방향 정렬 결과 입 니 다.rbegin () 과 rend () 두 가지 방법 을 사용 해 야 합 니 다. 각각 역 주 행 의 시작 위치 와 끝 위 치 를 보 여 줍 니 다.
#include
#include
using namespace std;
int main()
{
	set s;
	return 0;
}

4. 원소 의 삭제
        요 소 를 삽입 하 는 처리 와 마찬가지 로 집합 은 효율 적 인 삭제 처리 기능 을 가지 고 내부 의 붉 은 검 은 나무의 균형 을 자동 으로 재 조정 한다.삭 제 된 대상 은 어떤 교체 기 위치 에 있 는 요소, 키 값 과 같은 요소, 한 구간 에 있 는 요소 와 비 운 집합 일 수 있 습 니 다.
#include
#include
using namespace std;
int main()
{
	set s;
	s.insert(5); //     5,    
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(5); //     5,    ,    
	set::iterator it; //       
	//            
	for(it = s.begin(); it != s.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	return 0;
}
//    :1 3 5 6

5. 원소 의 검색
          find () 방법 으로 집합 을 검색 하고 찾 은 키 값 을 찾 으 면 이 키 값 의 교체 기 위 치 를 되 돌려 줍 니 다.그렇지 않 으 면 마지막 요 소 를 집합 한 뒤의 위치, 즉 end () 를 되 돌려 줍 니 다.
#include
#include
using namespace std;
int main()
{
	set s;
	s.insert(5); //     5,    
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(5); //     5,    ,    
	set::reverse_iterator rit; //       
	//            
	for(rit = s.rbegin(); rit != s.rend(); rit++)
	{
		cout << *rit << " ";
	}
	cout << endl;
	return 0;
}
//    :6 5 3 1

6. 다음 과 같은 방법 으로 한 수의 집합 여 부 를 판단 할 수 있다.
#include
#include
#include 
#include 
using namespace std;
int main()
{
    set s;
    s.insert(5); //     5,    
    s.insert(1);
    s.insert(6);
    s.insert(3);
    s.insert(5); //     5,    ,    
    s.erase(6); //     6   
    set::reverse_iterator rit; //       
    //            
    for(rit = s.rbegin(); rit != s.rend(); rit++)
    {
        cout << *rit << " ";
    }
    cout << endl;
    set::iterator it;

    it = s.begin();
    for(int i = 0; i < 2; i++)
        s.erase(it++);
    for(it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    cout << endl;

    s.clear();
    cout << s.size() << endl;

    return 0;
}
/*
    :
5 3 1
5
0
*/


7. 사용자 정의 비교 함수
         insert 를 사용 하여 요 소 를 집합 에 삽입 할 때 집합 은 설 정 된 비교 함수 상 에 따라 이 요 소 를 놓 을 노드 에 올 립 니 다.집합 을 정의 할 때 비교 함 수 를 지정 하지 않 으 면 기본 적 인 비교 함수, 즉 버튼 값 을 작은 순서 로 요 소 를 삽입 합 니 다.그러나 많은 경우 에는 스스로 비교 함 수 를 만들어 야 한다.
비교 함 수 를 만 드 는 데 는 두 가지 방법 이 있다.
(1) 요소 가 구조 체 가 아니라면 비교 함 수 를 작성 할 수 있 습 니 다.아래 의 프로그램 비교 규칙 은 버튼 값 이 큰 순서 에서 작은 순서 로 집합 에 삽입 되 는 것 이다.
#include
#include
using namespace std;
int main()
{
	set s;
	s.insert(5); //     5,    
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(5); //     5,    ,    
	set::iterator it;
	it = s.find(6); //     6   
	if(it != s.end())
		cout << *it << endl;
	else
		cout << "not find it" << endl;
	it = s.find(20);
	if(it != s.end())
		cout << *it << endl;
	else
		cout << "not find it" << endl;
	return 0;
}
/*
    :
6
not find it   
*/

(2) 원소 가 구조 체 라면 비교 함 수 를 구조 체 내 에 직접 쓸 수 있다.
#include 
#include 
using namespace std;
int main() {
    set  s;
    int a;
    for(int i = 0; i < 10; i++)
        s.insert(i);
    for(int i = 0; i < 5; i++) {
        scanf("%d", &a);
        if(!s.count(a)) //   
            printf("does not exist
"); else printf("exist
"); } return 0; }

시퀀스 용기: (vector 와 list, deque)        erase 교체 기 는 삭 제 된 요 소 를 가리 키 는 교체 기 를 무효 화 할 뿐만 아니 라 삭 제 된 요 소 를 가리 키 는 모든 교체 기 를 무효 화 하기 때문에 erase (iter +) 방식 을 사용 할 수 없 지만 erase 의 반환 값 은 다음 효과 적 인 교체 기 입 니 다.
        그래서 정확 한 방법 은:        for( iter = c.begin(); iter != c.end(); )               iter = c.erase(iter); 연관 성 용기: (map 와 set 가 자주 사용)        erase 교체 기 는 삭 제 된 요소 의 교체 기 만 효력 을 잃 지만 반환 값 은 void 이기 때문에 erase (iter +) 방식 으로 교체 기 를 삭제 해 야 합 니 다.          그래서 정확 한 방법 은:        for( iter = c.begin(); iter != c.end(); )                c.erase(iter++);
Tips:        사실 list 에 대해 서 는 두 가지 방식 모두 정상적으로 일 할 수 있 습 니 다.
STL 의 용 기 는 요 소 를 삭제 하고 교체 기 를 사용 하 는 것 외 에 erase (key) 방식 도 사용 할 수 있다.
size_t rm_num = obj.erase(key);
rm_num 은 key 를 삭제 한 구성원 의 개 수 를 표시 합 니 다. map 에서 key 는 key 값 이 고 다른 용기 에서 key 는 value 입 니 다.
8. 구조 체 의 set, 그리고 그 찾기
#include
#include
using namespace std;
struct mycomp
{ //       ,  “()”   
	bool operator() (const int &a, const int &b)
	{
		if(a != b)
			return a > b;
		else
			return a > b;
	}
};
int main()
{
	set s; //      mycomp
	s.insert(5); //     5,    
	s.insert(1);
	s.insert(6);
	s.insert(3);
	s.insert(5); //     5,    ,    
	set::iterator it;
	for(it = s.begin(); it != s.end(); it++)
		cout << *it << " ";
	cout << endl;
	return 0;
}
/*
    :6 5 3 1  
*/

좋은 웹페이지 즐겨찾기