UNSEEN 코테 Part. 4_2자료구조: 컨테이너 개념 요약

STL(라이브러리)

1. 반복자(iterator)

2. 컨테이너(container)

3. 알고리즘(algorithm)

1. 반복자(iterator)

1.입력 반복자(input iterator)-> 입력만

2. 출력 반복자(output iterator)-> 출력만

3. 순방향 반복자(forward iterator)->순방향 입출력

4. 양방향 반복자(bidirectional iterator)->양방향 입출력

5. 임의 접근 반복자(random access iterator)->포인터가 할 수 있는것 

---

2.컨테이너(container)

1. 시퀀스 컨테이너(sequence container)

2. 연관 컨테이너(associative container)

3. 컨테이너 어댑터(adapter container)

 

컨테이너 종류설명컨테이너

시퀀스 컨테이너	데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너	vector, deque, list, forwad_list
연관 컨테이너	데이터를 일정 규칙에 따라 조직화하여 저장하고 관리하는 컨테이너	set, multiset, map, multimap
컨테이너 어댑터	간결함과 명료성을 위해 인터페이스를 제한한 시퀀스나 연관 컨테이너의 변형 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없습니다.	stack, queue, priority_queue

 

시퀀스 컨테이너의 종류

시퀀스 컨테이너(sequence container)는 데이터를 선형으로 저장하며, 특별한 제약이나 규칙이 없는 가장 일반적인 컨테이너입니다.시퀀스 컨테이너에서는 삽입된 요소의 순서가 그대로 유지됩니다.

 

 

1. vector

 vector 헤더 파일

vector<템플릿인수> 객체이름(생성자인수);

객체는 요소가 추가되거나 삭제될 때마다 자동으로 메모리를 재할당하여 크기를 동적으로 변경합니다.

 

2. deque

양쪽에 끝이 있는 큐

양 끝에서 빠르게 요소를 삽입하거나 삭제

3. list

 이중 연결 리스트 탬플랫표

모든 요소에서 양방향 접근, 빠른 삽입과 삭제

임의 접근은 할 수는 없다

4. forward_list

단방향 연결 리스트(singly linked list)

든 요소에서 순방향으로 접근할 수는 있지만, 역방향으로 접근할 수는 없습니

---

연관 컨테이너의 종류

STL에서는 연관 컨테이너로 다음과 같은 클래스 템플릿을 제공합니다.

 

1. set 2. multiset

오름차순으로 정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.

집합(set)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.

하지만 멀티집합(multiset)은 키의 중복을 허용하므로, 같은 값을 여러 번 저장할 수 있습니다.

 

3. map4. multimap

정렬된 위치에 요소를 삽입하므로 검색 속도가 매우 빠릅니다.

맵(map)에서 키는 유일해야 하므로, 키의 중복을 허용하지 않습니다.

따라서 하나의 키에 하나의 값만이 연결될 수 있습니다.

하지만 멀티맵(multimap)은 값의 중복을 허용하므로, 하나의 키가 여러 개의 값과 연결될 수 있습니다.

이 두 컨테이너는 모두 map 헤더 파일에 정의되어 있습니다.

 

컨테이너 어댑터의 종류

인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너

 

1. stack

 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공

후입선출(LIFO)의 시멘틱을 따르는 자료 구조

2. queue

 deque 클래스의 인터페이스를 제한하여, 전형적인 큐 메모리 구조의 인터페이스를 제공

큐 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO)의 시멘틱을 따르는 자료 구조입니다

 

3. priority_queue( 우선순위큐)

가장 큰 값을 지닌 요소가 위치

deque 클래스를 기반으로 하는 것과는 달리, 우선순위 큐는 vector 클래스를 기반

---

 

3.알고리즘

 

1. 읽기 알고리즘(algorithm 헤더 파일)

•  find()
•  for_each()

2. 변경 알고리즘(algorithm 헤더 파일)

• copy()
•  swap()
•  transform()

 

3. 정렬 알고리즘(algorithm 헤더 파일)

•  sort()-비교 오름차순 정
•  stable_sort()
•  binary_search()

 

4. 수치 알고리즘(numeric 헤더 파일)

•  . accumulate() 요소

 

출처 및 참고

UNSEEN 코테 Part. 4_1자료구조: 컨테이너 개념