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;
}