ACM / STL - 용기 set 의 소개 / 각종 조작 (코드 예) / 응용

41423 단어 ACM-STL
용기 설정
본문 은 사람 을 아 끼 는 고양이 의 글 을 참고 하 였 다
C + + STL 은 광범 위 한 찬 사 를 받 았 고 많은 사람들 이 사용 했다. vector, string, list 등 편리 한 용 기 를 제공 할 뿐만 아니 라 더욱 중요 한 것 은 STL 은 복잡 한 데이터 구조 알고리즘 과 대량의 상용 데이터 구조 조작 을 봉인 했다.vector 패 키 징 배열, list 는 링크, map 와 set 는 이 진 트 리 등 을 패 키 징 했 습 니 다. 이 데이터 구 조 를 패 키 징 할 때 STL 은 프로그래머 의 사용 습관 에 따라 구성원 함수 방식 으로 자주 사용 하 는 동작 입 니 다. 예 를 들 어 삽입, 정렬, 삭제, 찾기 등 입 니 다.사용자 로 하여 금 STL 사용 과정 에서 낯 설 지 않 게 하 다.
set 에 대해 설명 해 야 할 것 은 set 관련 용기 입 니 다.set 는 하나의 용기 로 서 같은 데이터 형식의 데이터 형식 을 저장 하고 하나의 데이터 집합 에서 데 이 터 를 꺼 낼 수 있 으 며 set 에서 모든 요소 의 값 이 유일 하 며 시스템 은 요소 의 값 에 따라 자동 으로 정렬 할 수 있 습 니 다.주의해 야 할 것 은 set 에서 수 원소 의 값 이 직접적 으로 바 뀔 수 없다 는 것 이다.C + STL 에서 표준 관련 용기 set, multiset, map, multimap 내부 에서 사용 하 는 것 은 매우 효율 적 인 균형 검색 이 진 트 리: 빨 간 검 은 나무 도 RB 트 리 (Red - Black Tree) 가 된다.RB 트 리 는 일반 밸 런 스 트 리 보다 통계 성능 이 좋아 STL 에서 관련 용기 의 내부 구조 로 선택 됐다.
특징: 1. set 의 삽입 삭제 효율 이 다른 시퀀스 용기 보다 높 습 니 다.
관련 용기 에 있어 서 메모리 복사 와 메모리 이동 이 필요 하지 않 기 때문이다.맞다, 확실히 그렇다.set 용기 안의 모든 요 소 는 노드 의 방식 으로 저장 되 고 노드 구조 와 링크 의 차이 가 많 지 않 으 며 부모 노드 와 서브 노드 를 가리킨다.
2. 데이터 요소 가 증가 할 때 set 의 삽입 과 검색 속 도 는 여전히 빠르다.
로그 2 의 관 계 를 알 고 있다 면 그 답 을 철저히 알 아야 합 니 다.set 에서 찾 는 것 은 2 분 으로 찾 는 것 이다. 즉, 16 개의 요소 가 있 으 면 최대 4 번 비교 해 야 결 과 를 찾 을 수 있 고 32 개의 요소 가 있 으 며 최대 5 번 비교 할 수 있다 는 것 이다.그럼 10000 개 는 요?최대 비교 횟수 는 log 10000, 최대 14 회 입 니 다. 20000 개의 요소 라면 요?기껏해야 15 번 에 불과 하 다.보 셨 죠? 데이터 양 이 배로 늘 었 을 때 검색 횟수 는 1 회 에 불과 하고 1 / 14 의 검색 시간 이 늘 었 을 뿐 입 니 다.네가 이 이 치 를 알 게 되면 안심 하고 안에 원 소 를 넣 을 수 있 을 것 이다.
set 상세 설명:
1. 정의 방법:
헤더 파일: set 용 기 를 정의 합 니 다:
set<int> s1;
set<double> s2;

2. 기본 동작:
이 조작 들 은 다음 에 각각 예 를 들 어 설명 할 것 이다.
s.begin()	                  
s.clear()	 	       
s.count() 	 	           
s.empty()true( )
s.end()		 	                 ,        
s.equal_range()                       
s.erase() 		         
s.find() 		                 
s.get_allocator() //         
s.insert() 		         
s.lower_bound()         (   )            
s.key_comp() 	//                
s.max_size() 	                 
s.rbegin()		                     
s.rend()		                    
s.size() 		          
s.swap()		          
s.upper_bound()                
s.value_comp() 	//                 

1.insert( ),size(), max_size (), begin (), end (), clear (), empy () 함수
#include 
#include 
 
using namespace std;
 set<int>s;
    s.insert(1);
    s.insert(2);
    s.insert(4);
    s.insert(0);
    cout<<"set   size    :"<<s.size()<<endl;
    cout<<"set   maxsize    :"<<s.max_size()<<endl;
    cout<<"set          :"<<*s.begin()<<endl;// *          
     cout<<"set          :"<<*s.end()<<endl;
     if(s.empty())
     {
         cout<<"set    !!!"<<endl;
     }
     else cout<<"set   size    :"<<s.size()<<endl;
     s.clear();
     if(s.empty())
     {
         cout<<"set    !!!"<<endl;
     }
     else cout<<"set   size    :"<<s.size()<<endl;
     cout<<"set   size    :"<<s.size()<<endl;
     cout<<"set   maxsize    :"<<s.max_size()<<endl;
     return 0;
}


출력:
set 의 size 값 은: 4 set 의 maxsize 값 은: 214748364 set 의 첫 번 째 요 소 는: 0 set 의 마지막 요 소 는: 4 set 의 size 값 은: 4 set 가 비어 있 습 니 다!!set 의 size 값 은 0 set 의 maxsize 값 은 214748364 입 니 다.
2.s.upper_bound() s.lower_bound()
이 두 개 는 내 가 전에 상세 하 게 쓴 적 이 있다. 전송 문.
3.erase():
erase (iterator), 위치 추적 기 iterator 가 가리 키 는 값 erase (first, second) 를 삭제 하고 위치 추적 기 first 와 second 사이 의 값 erase (key value) 를 삭제 하 며 키 값 key 를 삭제 합 니 다.value 의 값
#include 
#include 

using namespace std;

int main(){
     set<int> s;
     set<int>::const_iterator iter;
     set<int>::iterator first;
     set<int>::iterator second;
     for(int i = 1 ; i <= 10 ; ++i)
     {
         s.insert(i);
     }
     for(iter = s.begin() ; iter != s.end() ; ++iter)
     {
         cout<<*iter<<" ";
     }
     cout<<endl;
     //     
     s.erase(s.begin());
     //     
     first=s.begin();
     second=s.begin();
     second++;
     second++;
     s.erase(first,second);
     //     
     s.erase(8);
    cout<<"    set      :"<<endl;
     for(iter = s.begin() ; iter != s.end() ; ++iter)
     {
         cout<<*iter<<" ";
     }
     cout<<endl;
    return 0;
}

결과: 1, 2, 3, 4, 5, 6, 7, 89 10 삭제 후 set 의 요 소 는 4, 5, 6, 7, 9 소결 입 니 다. set 의 삭제 작업 은 어떠한 오류 검사 도 하지 않 습 니 다. 예 를 들 어 위치 추적 기의 합 법 여부 등 이 있 으 므 로 사용 할 때 반드시 주의해 야 합 니 다.
4.insert()
1. insert (key value) 키value 를 set 에 삽입 하면 반환 값 은 pairset 입 니 다.: iterator, bool, bool 은 삽입 이 성 공 했 는 지, iterator 는 삽 입 된 위 치 를 표시 합 니 다. 만약 keyvalue 가 set 에 있 으 면 iterator 가 표시 하 는 keyvalue 가 set 에 있 는 위치 입 니 다.2. inset (first, second) 은 위치 추적 기 first 에서 second 사이 의 요 소 를 set 에 삽입 하고 반환 값 은 void 입 니 다.
#include 
#include 

using namespace std;

int main()
{
     int a[] = {1,2,3};
     int t;
     set<int> s;
     set<int>::iterator iter;
     s.insert(a,a+3);//  2
     for(iter = s.begin() ; iter != s.end() ; ++iter)
     {
         cout<<*iter<<" ";
     }
     cout<<endl;
     pair<set<int>::iterator,bool> pr;
     cin>>t;
     pr = s.insert(t);//  1
     if(!pr.second)
     {
         cout<<"error"<<endl;
     }
     for(iter = s.begin() ; iter != s.end() ; ++iter)
     {
         cout<<*iter<<" ";
     }
     cout<<endl;
     return 0;
}

5.find()
find (Key) 의 기능 은 키 값 이 Key 인 요소 의 위 치 를 되 돌려 주 는 것 입 니 다. 되 돌려 주 는 값 은 교체 기 형식 입 니 다.
#include 
#include 
using namespace std;

int main()
{
    set<int>s;
    for(int i=0;i<10;i++)
        s.insert(i);
    set<int>::iterator it1=s.find(4);
    set<int>::iterator it2=s.find(11);//            ,   11        ,   end()。
    if(it1!=s.end())
        cout<<*(it1)<<endl;
    else cout<<"error"<<endl;
    if(it2!=s.end())
        cout<<*(it2)<<endl;
    else cout<<"error"<<endl;
    return 0;
}

출력: 4 error
6.swap()
두 집합의 교환 을 진행 하 다
#include 
#include 
using namespace std;

int main()
{
    set<int>s1;
    set<int>s2;
    for(int i=0;i<10;i++)
        s1.insert(i);
    for(int i=10;i<15;i++)
        s2.insert(i);
    cout<<"s1:";
    for(set<int>::iterator it =s1.begin();it!=s1.end();it++)
        cout<<*(it)<<" ";
    cout<<endl;
    cout<<"s2:";
    for(set<int>::iterator it =s2.begin();it!=s2.end();it++)
        cout<<*(it)<<" ";
    cout<<endl;
    s1.swap(s2);//    
    cout<<"s1:";
    for(set<int>::iterator it =s1.begin();it!=s1.end();it++)
        cout<<*(it)<<" ";
    cout<<endl;
    cout<<"s2:";
    for(set<int>::iterator it =s2.begin();it!=s2.end();it++)
        cout<<*(it)<<" ";
    cout<<endl;
    return 0;
}

출력: s10: 01 2 3 4 6 7 8 9 s2: 10 11 12 13 14 s1: 10 11 12 13 14 s2: 0 1 2 3 4 5 6 7 8 9
7.s.equal_range () / / 집합 에서 주어진 값 과 같은 상하 한 두 개의 교체 기 를 되 돌려 줍 니 다.
한 쌍 의 포 지 셔 닝 머 신 을 되 돌려 줍 니 다. 첫 번 째 는 주어진 관건 값 보다 크 거나 같은 요소 와 첫 번 째 는 주어진 관건 값 보다 큰 요 소 를 표시 합 니 다. 이 반환 값 은 pair 형식 입 니 다. 만약 에 이 포 지 셔 닝 머 신 에서 어떤 반환 이 실패 하면 end () 의 값 과 같 습 니 다.
#include 
#include 
using namespace std;

int main()
{
    set<int>s;
    set<int>::iterator ter;
    for(int i=1;i<5;i++)
        s.insert(i);
     pair<set<int>::const_iterator,set<int>::const_iterator> pr;
     pr = s.equal_range(3);
     cout<<"        3     :"<<*pr.first<<endl;
     cout<<"      3    : "<<*pr.second<<endl;
    return 0;
}

좋은 웹페이지 즐겨찾기