STL Container

(기존 게시물 https://static-jsony.tistory.com/42 )

 

STL Container

컨테이너란 데이터를 모아서 저장해 둘 수 있는 제네릭 데이터 구조로, 템플릿(template)로 만들어져 있기에 어떤 데이터 타입이든 저장이 가능하다.

std::array와 std::bitset을 제외한 나머지 컨테이너들은 항목의 갯수에 따라 그 크기가 유동적으로 변하기 때문에 융통성 있게 사용할 수 있다.

 

<해당 컨테이너 클릭 시 설명으로 이동>

컨테이너 타입	종류	+ @
Sequence Container [ 시퀸스 컨테이너 ]	array	배열
	vector	가변배열
	list	양방향 연결 리스트
	forward_list	단방향 연결 리스트
	deque	앞뒤로 넣고 빼는 큐
	특징	선형적인 집합 자료를 저장하는 기본 임무에 충실한 일반적인 컨테이너 삽입 / 삭제에 큰 제약이 없음
Associative Container [ 연관 컨테이너 ] [이진 탐색 트리 기반 / 자동정렬]	set	key만 저장 ( key값 중복 불가)
	map	key / value 로 구성 ( key값 중복 불가)
	multiset	set + key값 중복 가능
	multimap	map + key값 중복 가능
	특징	자료저장 + 일정 규칙에 따라 자료를 조직화 하여 관리  신속한 검색을 위해 찾기 좋은 위치에 자동 삽입
Unordered Associative Container [ 정리되지 않은 연관 컨테이너 ] [ 해시 테이블]	unordered_set	set + 정렬되지 않음
	unordered_map	map + 정렬되지 않음
	unordered_multiset	multiset + 정렬되지 않음
	unordered_multimap	multimap + 정렬되지 않음
	특징	C++ 11 부터 추가된 컨테이너로, 과거 Hash Table을 기반으로 함. 요소의 추가 삭제가 연관 컨테이너 보다 빠르다. 단, 연관 컨테이너는 양방향 iterator를 지원하지만 이 컨테이너는 순방향 iterator만 지원한다.

 

Container adaptor

- stack (LIFO)

- queue (FIFO)

- priority_queue [우선순위 큐]

특징 : 특정 형태의 동작만 수행 / 반복자를 지원하지 않음 / FIFO & LIFO 등 미리 정한 규칙의 통제를 따름

단점 :  자료를 넣고 빼는 순서를 외부에서 마음대로 조작할수 없음

 

BitSet

Container adaptor

- stack (LIFO)

- queue (FIFO)

- priority_queue [우선순위 큐]

특징 : 특정 형태의 동작만 수행 / 반복자를 지원하지 않음 / FIFO & LIFO 등 미리 정한 규칙의 통제를 따름

단점 :  자료를 넣고 빼는 순서를 외부에서 마음대로 조작할수 없음

 

BitSet

 

Sequence Container

array ( C++ 11 이상 )

- 생성시 stack 영역에 메모리 할당

- 컴파일 타임에 생성이 되며, 고정된 크기를 가지고 생성된다( array< int, 10 > )

- C++ 이전에 존재했던 배열(C-Array) + 벡터의 장점을 더해 만들어진 컨테이너

( C-Array : int intArr[ 2 ] = { 0, 1 }; 형식으로 생성되던 배열. C언어에서 쓰이던 배열)

- array< int, 10 > arr;  초기화 하지 않았으므로 10개의 배열값 모두 쓰레기 값으로 생성됨.

- array< int, 10 > arr = { 1, 2, 3, };   arr[ 2 ] 이후로는 0으로 초기화 되어 생성됨.

	함수 이름	함수 설명
Iterators	begin( )	첫번째 원소를 리턴 ( iterator )
	end( )	마지막 원소의 다음 원소를 리턴 ( post-the-end )
	rbegin( )	배열 원소들의 순서를 거꾸로 한 다음, 첫번째 원소를 가리킴
	rend( )	배열을 거꾸로 한 다음, 마지막 원소의 다음 원소를 리턴
	cbegin( ), cend( )	begin( ) 과 end( )와 동일한 기능이지만 const가 붙어서 순회 불가능
	crbegin( ), crend( )	rbegin( ) 과 rend( )와 동일한 기능이지만 const가 붙어서 순회 불가능
Element Access	front( )	첫번째 원소의 값을 리턴
	back( )	마지막 원소의 값을 리턴
	data( )	원소의 주소 리턴 ( array [ nIndex ] 혹은 array.at( nIndex ) 처럼 쓸 수 있음. *( arr.data( ) ) 를 하면 첫번째 원소의 값을 리턴하고 *( arr.data( ) +1 ) 를 하면 두번째 원소의 값을 리턴한다.
	at( nIndex )	nIndex 번째 원소의 값을 반환 nIndex의 값이 배열의 크기를 벗어날 경우, 예외 처리를 해줌.( std::out_of_range )
	[ nIndex ]	nIndex 번째 원소의 값을 반환 nIndex의 값이 배열의 크기를 벗어나도, 예외처리를 해주지 않음 = 오버플로우 확률이 높다.
Operations	fill( value_type& rValue)	배열의 모든 원소의 값을 rValue로 변경
	swap( array< value_type >&target )	타입과 길이가 같은 target array를 입력 받아, target array로 swap됨.
Capacity	empty( )	배열이 비어 있는지 확인 array< int, 0 > arr1 일 경우 empty( ) = true; array< int, 10 > arr2 일 경우 empty( ) = false;
	max_size( )	배열의 max 사이즈를 리턴 ( = size( )와 동일 )
	size( )	배열의 사이즈(= 원소의 갯수)를 리턴 ( = max_size( )와 동일 )

장점	단점
임의 접근 가능	중간 삽입 삭제가 느림 런타임때는 크기를 변경 할 수 없음

vector

- 동적 배열을 확장시킨 형태의 컨테이너이자 가장 간단한 시퀸스 컨테이너

- 생성 시 Heap 영역 (혹은 free-store) 에 메모리를 할당

- 요소가 추가되거나 삭제될때 자동으로 메모리를 재할당하여 크기를 동적으로 변경

- 요소들을 인접한 메모리 위치에 연속적으로 저장하기에 요소를 빠르게 읽고 쓸 수 있다.

- 읽기 속도가 빠르기에 정렬이나 이분 검색등의 알고리즘에 대단히 효율적이다.

- 단, 중간에 요소 삽입/삭제 시 메모리를 밀고 당기는 작업을 해야하기에 삽입/삭제 속도는 deque나 list에 비해 느리다.

( 참고하는 자료마다 deque가 빠르냐 vector가 빠르냐 의견이 다른데 테스트 내용 추가 예정 )

	함수 이름	함수 설명
assign( size_type count, const value_type& rValue ) assign(  vector<value_type>::iterator start, vector<value_type>::iterator end )		1. count개의 원소를 rValue 값으로 할당. 2. iterator Start부터 End 의 범위에 있는 원소들로 대입 (보통 다른 vector의 원소를 범위로 가져올때 쓰는 방법)
Iterators	begin( )	첫번째 원소를 리턴 ( iterator)
	end( )	마지막 원소의 다음 원소를 리턴 ( post-the-end )
	rbegin( )	배열 원소들의 순서를 거꾸로 한 다음, 첫번째 원소를 가리킴
	rend( )	배열을 거꾸로 한 다음, 마지막 원소의 다음 원소를 리턴
	cbegin( ), cend( )	begin( ) 과 end( )와 동일한 기능이지만 const가 붙어서 순회 불가능
	crbegin( ), crend( )	rbegin( ) 과 rend( )와 동일한 기능이지만 const가 붙어서 순회 불가능
Element Access	front( )	첫번째 원소의 값을 리턴
	back( )	마지막 원소의 값을 리턴
	data( )	원소의 주소 리턴 ( array [ nIndex]혹은 array.at( nIndex )처럼 쓸 수 있음. *( arr.data( ) ) 를 하면 첫번째 원소의 값을 리턴하고 *( arr.data( ) +1 ) 를 하면 두번째 원소의 값을 리턴한다.
	at( nIndex )	nIndex 번째 원소의 값을 반환 nIndex의 값이 배열의 크기를 벗어날 경우, 예외 처리를 해줌.( std::out_of_range )
	[ nIndex ]	nIndex 번째 원소의 값을 반환 nIndex의 값이 배열의 크기를 벗어나도, 예외처리를 해주지 않음 = 오버플로우 확률이 높다.
Modifiers
	resize( )
	swap( vector< value_type >&target )	타입과 길이가 같은 target vector를 입력 받아, target vector로 swap됨.
Capacity	empty( )	배열이 비어 있는지 확인 array< int, 0 > arr1 일 경우 empty( ) = true; array< int, 10 > arr2 일 경우 empty( ) = false;
	max_size( )	배열의 max 사이즈를 리턴 ( = size( )와 동일 )
	size( )	배열의 사이즈(= 원소의 갯수)를 리턴 ( = max_size( )와 동일 )