도전 프로 그래 밍 (알고리즘 과 데이터 구조) - 데이터 구조 (STL 총화)

STL (표준 템 플 릿 라 이브 러 리) 안내
글 목록

창고

대열

일반 대열

우선 대기 열

양 끝 대기 열

vector (동적 배열)

list (양 방향 링크)

set (집합)

map (키 쌍 집합)

창고.
헤더 파일 #include 사용 stack S; 구성원 함수
함수 명
표 기능
복잡 도
size()
스 택 의 원소 수 를 되 돌려 줍 니 다.
O(1)
top()
창고 꼭대기 의 원소 되 돌리 기
O(1)
pop()
스 택 에서 요 소 를 꺼 내 고 삭제 합 니 다.
O(1)
push(x)
창고 에 원소 추가 x
O(1)
empty()
스 택 이 비어 있 을 때 true 로 돌아 가기
O(1)
swap(s1,s2)
창고 s1 과 창고 s2 의 데 이 터 를 교환 하면 두 창고 의 이름 이 바 뀐 셈 이다. c++11 。 ！c++11 swap， 11 ， 。대열
일반 대기 열
헤더 파일 #include 사용 queue Q 구성원 함수
함수 명
표 기능
복잡 도
size()
대기 열의 요소 수 를 되 돌려 줍 니 다.
O(1)
front()
돌아 오 는 원소
O(1)
back()
열 끝 요소 되 돌리 기
O(1)
pop()
대기 열 에서 요 소 를 꺼 내 고 삭제 합 니 다.
O(1)
push(x)
대기 열 에 요소 추가 x
O(1)
empty()
열 이 비어 있 을 때 true 로 돌아 가기
O(1)
우선 순위 대기 열

헤더 파일: #include

먼저 대열 을 나 서 는 것 은 우선 순위 가 가장 높 은 요소 이다.

사용 priority_queue pq; (기본 값: 값 이 클 수록 우선 순위 가 높 습 니 다).

주의: 원 소 를 채취 하 는 방법 은 queue 의 front () 에서 top () 으로 변 합 니 다.

priority_queue, greater > pq; 값 이 작 을 수록 우선 순위 가 높 습 니 다. 마지막 두 개의 ">" 중간 에 빈 칸 이 있어 야 합 니 다.

사용자 정의 형식 은 우선 순위 비교 함 수 를 스스로 정의 해 야 합 니 다.

우선 대기 열 은 더미 구 조 를 사용 하여 이 루어 집 니 다. 더미 의 조작 복잡 도 는 O (logn) 입 니 다.

구체 적 인 상황 은 코드 참조:

struct cmp1{ 
    bool operator ()(int &a,int &b){ 
        return a>b;//      
    } 
}; 

struct node {     
　　int x, y;     
　　bool operator < (const node&a, const node& b) const 
　　{         
　　　　return a.x > b.x;    //    ，x       
　　}
};

priority_queue<int，vector<int>, cmp1 > pq;//   ，          。          。
priority_queue<node>q;   //    
//     ，y  , x    。
//     operator
//   ””，         

양 끝 대기 열
헤더 파일: #include 사용: deques1; 구성원 함수
함수 명
표 기능
복잡 도
size()
대기 열의 요소 수 를 되 돌려 줍 니 다.
O(1)
front()
돌아 오 는 원소
O(1)
back()
열 끝 요소 되 돌리 기
O(1)
pop_front()
대기 열의 맨 앞 에 있 는 요 소 를 삭제 합 니 다.
O(1)
pop_back()
대기 열의 맨 뒤에 있 는 요 소 를 삭제 합 니 다.
O(1)
push_front(x)
대기 열 첫 부분 에 요소 x 추가
O(1)
push_back(x)
대기 열 끝 에 요소 x 추가
O(1)
empty()
열 이 비어 있 을 때 true 로 돌아 가기
O(1)
clear()
대기 열 에 있 는 모든 요 소 를 비 웁 니 다.
O(n)

주의: vector 와 유사 한 무 작위 접근 지원 (O (1): int x=Q[3];

vector (동적 배열)
헤더 파일 #include 사용 vector V 구성원 함수
함수 명
표 기능
복잡 도
size()
벡터 의 원소 수 를 되 돌려 줍 니 다.
O(1)
begin()
벡터 시작 을 가리 키 는 교체 기 를 되 돌려 줍 니 다.
O(1)
end()
벡터 끝 을 가리 키 는 교체 기
O(1)
push_back(x)
벡터 끝 에 요소 x 추가
O(1)
pop_back()
벡터 의 마지막 요 소 를 삭제 합 니 다.
O(1)
empty()
벡터 가 비어 있 을 때 true 를 되 돌려 줍 니 다.
O(1)
insert(p,x)
벡터 위치 p 에 요소 x 삽입 (이 p 는 교체 기)
O(n)
erase( p)
벡터 의 위치 p 요 소 를 삭제 합 니 다 (이 p 는 교체 기 입 니 다)
O(n)
clear()
벡터 의 모든 요 소 를 삭제 합 니 다.
O(n)
vector 기술 1. 초기 화 (5 가지) vectorvec; / / 초기 화 비 어 있 음vectorvec(v1); / / 다른 vector 로 초기 화, 즉 복사 본 을 만 드 는 것 입 니 다.vectorvec(n, i); / / 크기 는 n 이 고 모두 요소 i 로 초기 화 합 니 다 (상용)vector(n); / / 구조 크기 가 n 인 용기 로 안의 요 소 를 초기 화하 지 않 았 습 니 다.vector{1,2,3,4}; / / 구조 크기 가 4 이 고 안의 각 요 소 를 초기 화 합 니 다.
2. 용기 옮 겨 다 니 기

vector<int>::iterator it;
for(it=vec.begin();it!=vec.end();it++){
	vec[it]=0;
}

3. 공간 조절

vec.capacity();//           ，   vec.size()
vec.resize(n+m);//  vec     n+m，                      

4. vector 에서 자주 사용 하 는 함수 기능 입 니 다. 헤더 파일 #include 을 추가 해 야 합 니 다.

sort(vec.begin(),vec.end());//     
reverse(vec.begin(), vec.end());//    
swap(vec[i],vec[j]);//    

C + + 용기 vector 에서 자주 사용 하 는 구성원 함수 참조
list (양 방향 링크)
헤더 파일 #include 사용 list L 구성원 함수
함수 명
표 기능
복잡 도
size()
표 의 요소 수 를 되 돌려 줍 니 다.
O(1)
begin()
시계 시작 을 가리 키 는 교체 기 를 되 돌려 줍 니 다.
O(1)
end()
표 끝 을 가리 키 는 교체 기
O(1)
push_front(x)
표 의 시작 에 요소 x 를 추가 합 니 다.
O(1)
push_back(x)
표 의 끝 에 요소 x 를 추가 합 니 다.
O(1)
pop_front()
표 시작 에 있 는 요 소 를 삭제 합 니 다.
O(1)
pop_back()
표 끝 에 있 는 요 소 를 삭제 합 니 다.
O(1)
empty()
벡터 가 비어 있 을 때 true 를 되 돌려 줍 니 다.
O(1)
insert(p,x)
표 의 위치 p 에 요소 x 를 삽입 합 니 다 (이 p 는 교체 기 입 니 다)
O(1)
erase（p）
표 의 위치 p 요 소 를 삭제 합 니 다 (이 p 는 교체 기 입 니 다)
O(1)
clear()
표 의 모든 요 소 를 삭제 합 니 다.
O(n)
set (집합)
헤더 파일 #include 사용 set S

set 는 요소 값 을 정렬 하 는 집합 입 니 다. 삽 입 된 요 소 는 집합 에서 유일 하 며 중복 요 소 는 존재 하지 않 습 니 다. 구조 체 라면 다시 불 러 와 야 합 니 다. "

set 는 이 진 트 리 로 이 루어 지고 나 무 를 균형 적 으로 처리 하여 요소 가 나무 에 분포 되 어 있 기 때문에 검색 소, 삽입, 삭제 작업 의 복잡 도 를 O (logn) 에서 유지 할 수 있다.

구성원 함수:
함수 명
표 기능
복잡 도
size()
set 의 요소 수 를 되 돌려 줍 니 다.
O(1)
begin()
set 시작 을 가리 키 는 교체 기 를 되 돌려 줍 니 다.
O(1)
end()
set 끝 을 가리 키 는 교체 기
O(1)
clear()
set 의 모든 요소 삭제
O(n)
insert(x)
set 에 요소 x 삽입
O(logn)
count(x)
어떤 값 요소 x 의 개 수 를 되 돌려 줍 니 다.
erase（x）
x 가 함 유 된 요소 삭제
O(logn)
find(x)
x 와 일치 하 는 요 소 를 검색 하고 이 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다. x 와 일치 하 는 요소 가 없 으 면 끝 end () 를 되 돌려 줍 니 다.
O(logn)
또한 STL 에는 set 집합 과 교 집합 에 관 한 조작 set union 과 set intersection 이 있 습 니 다. 그리고 빈 집합 에 대한 성명 set() 도 있 습 니 다. 참고 제목: 12096 The SetStack Computer
map (키 쌍 집합)
헤더 파일 #include 사용 map T (string 을 키 로 하 는 int 형 요소)

map 집합 은 키 와 값 조합 을 요소 로 하고 집합 은 값 을 정렬 기준 으로 하 며 집합 에서 각 요소 의 키 가 유일 하고 중복 이 존재 하지 않 습 니 다.

"[]" 를 사용 하여 지정 한 키 에 대응 하 는 값 이나 교체 기 를 방문 하여 각 키 와 값 에 접근 할 수 있 습 니 다.

map 는 set 와 마찬가지 로 균형 이 잡 힌 이 진 트 리 를 통 해 이 루어 지기 때문에 요소 의 삽입, 삭제, 검색 과 '[]' 연산 의 복잡 도 는 모두 O (logn)

이다.

map 의 key 기본 값 은 less < > 오름차 순 으로 요소 정렬 (정렬 준칙 도 수정 가능) 입 니 다. 즉, key 는 operator 를 갖 춰 야 합 니 다. 구조 체 라면 다시 불 러 와 야 합 니 다. 예:

struct Puzzle
{
    int f[N2];
    int space;
    string path;
    bool operator < (const Puzzle &p) const {
        for(int i=0; i

구성원 함수: key 키, val 값
함수 명
표 기능
복잡 도
size()
맵 의 요소 수 를 되 돌려 줍 니 다.
O(1)
begin()
맵 의 시작 을 가리 키 는 교체 기 를 되 돌려 줍 니 다.
O(1)
end()
맵 끝 을 가리 키 는 교체 기
O(1)
clear()
맵 의 모든 요소 삭제
O(n)
insert((key,val))
맵 에 요소 삽입 (key, val)
O(logn)
erase（key）
키 를 포함 하 는 요소 삭제
O(logn)
count(key)
찾 은 요소 key 의 개 수 를 되 돌려 줍 니 다.
find(key)
key 와 일치 하 는 요 소 를 검색 하고 이 요 소 를 가리 키 는 교체 기 를 되 돌려 줍 니 다. key 와 일치 하 는 요소 가 없 으 면 끝 end () 를 되 돌려 줍 니 다.
O(logn)
확장: STL 의 구조 체 pair

헤더 없 는 파일

사용 pair T 으로 구조 체 요 소 를 초기 화하 거나 직접 사용 make_pair(x,y)

첫 번 째 요 소 는 first 로 접근 할 수 있 고 두 번 째 요 소 는 second 로 접근 할 수 있 습 니 다. eg: T. first 와 T. second

기타 지식 포인트:

산술 연산 을 할 수 있 는 교체 기 는 무 작위 로 교체 기 를 방문 하여 용기 요 소 를 연속 메모리 공간 에 저장 하도록 요구 합 니 다. vector, string, deque 의 교체 기 는 가감 법 이 있 지만 map, set, multimap, multiset 의 교체 기 는 가감 법 이 없 으 며 list 도 안 됩 니 다.