C++ #10
STL
STL의 배경
- C언어는 CRT(C Runtime Library)라는 이름의 라이브러리를, C++은 C++ Standard Library를 가지고 있다.
- 각 언어는 기능을 제공하고 손쉽게 구현하며, 재사용을 하기 위한 목적이다.
- 1994년 8월 C++ 표준 라이브러리에 STL(Standard Template Library)이 추가되었다.
STL이란
- STL의 사전적 의미는 표준 템플릿 라이브러리이다.
- 템플릿의 철학은 누구나 공통적으로 사용하기 위한 일반화 프로그래밍(Generic Programming)을 기반으로 한다.
- 무분별한 여러 형태의 코드를 지양하고 표준화된 코드를 지향한다.
STL의 성능
- 템플릿 기반이라고 해서 느릴 것이라는 편견이 있지만, 전반적으로 성능 면에서는 어떤 라이브러리에 비해서 전혀 떨어지지 않는다.
- 각 자료구조마다 사용 용도에 따른 성능의 차이를 보이는데, 자료의 검색, 정렬, 삽입, 삭제에 최적화된 자료구조를 취사 선택해서 사용하면 된다.
컨테이너
- 컨테이너의 사전적 의미는 무언가를 담는 '용기'를 의미한다.
- 컨테이너는 배열처럼 동일한 요소들로 구성되어야 한다.
- 컨테이너는 크게 순차 컨테이너(Sequence Container)와 정렬 연관 컨테이너(Sorted Associactive Container)로 나눌 수 있다.
순차 컨테이너
- 순차 컨테이너는 동일한 객체가 선형으로 구성된 집합으로 벡터, 데크, 리스트 이렇게 총 3가지가 있다.
| 컨테이너 | 내용 |
|---|---|
| 벡터(vector) | 구성 요소에 임의 접근이 가능하다. 요소 끝에 삽입/삭제는 빠르지만, 처음이나 중간 삽입/삭제는 요소 개수에 따라 처리속도가 비례한다. |
| 데크(deque) | 벡터와 비슷하다. 차이점은 요소 양 끝에 삽입/삭제가 가능하다는 점이다. 성능 또한 벡터와 같이 요소 개수에 따라 처리속도가 비례한다. |
| 리스트(list | 구성 요소에 선형적으로 접근한다. 요소에 삽입과 삭제가 위치에 상관없이 같은 속도로 처리한다. |
정렬 연관 컨테이너
- 키(key)를 사용하여 데이터를 신속하게 찾아낼 수 있다.
- 순차 컨테이너와 마찬가지로 실행 시 크기를 동적으로 변경할 수 있다.
- 요소에는 셋, 멀티셋, 맵, 멀티맵 4가지로 구성되어 있다.
| 컨테이너 | 내용 |
|---|---|
| 셋(set) | 집합에는 키만 저장할 수 있는데, 키의 중복은 허용하지 않으므로 동일한 키가 2개 존재할 수 없으며, 원하는 키를 신속하게 빠르게 찾아낸다. |
| 멀티셋(multiset) | 셋과의 차이라면 키의 중복을 허용한다는 점이다. 따라서 2개 이상의 복사본을 가질 수 있다. |
| 맵(map) | 집합에 키와 데이터를 같이 관리하는데, 키의 중복은 허용하지 않으므로, 동일한 키가 2개 존재할 수 없으며, 키를 사용하여 원하는 객체를 빠르게 찾아낸다. |
| 멀티맵(multimap) | 맵과의 차이라면 키의 중복을 허용한다는 점이다. 따라서 2개 이상의 복사본을 가질 수 있다. |
반복자
- 컨테이너의 요소를 가리키는 객체로 컨테이너의 시작부터 끝까지 이동하면서 요소를 읽거나 쓰기 위해 사용한다.
- 컴파일러의 내부 알고리즘은 컴파일러 제작 회사마다 조금씩 다르다.
- 반복자의 제한적 규정을 통해 각기 다른 컨테이너의 성능을 보장하도록 하였다.
STL의 특징
장점
- 일반화를 지원한다. 일반화란 범용적, 공통적으로 사용할 수 있다는 말이다. 즉, 누구나 다 사용할 수 있도록 하는 것이 일반화의 기본 철학이다.
- 컴파일 타입의 매커니즘을 사용하므로 실행 시 효율의 저하가 거의 없다.
- 표준이므로 이식성이 좋다.
- 소스 공개로 확장성이 좋다.
단점
- 템플릿 기반이므로 함수와 클래스가 매번 구체화되어 소스가 비대해진다.
- 가독성이 떨어진다. 템플릿 기반 코드이므로 입문하기가 쉽지 않다.
- 예외 처리 적용이 쉽지 않다.
백터(vector)
백터란 (=동적 배열)
- 일반화된 컨테이너 중에서 가장 많이 사용한다.
- 필요한 크기만큼 메모리를 자동으로 재할당하여 늘릴 수 있다.
- 템플릿 기반으로 요소의 타입에 무관하게 만들 수 있다.
백터의 사용형태
- 백터의 형식으로 타입이 T형인 백터 객체를 선언한 형태이다.
vector<T> vec1;- 타입이 int형인 백터를 생성하려면?
vector<int> vec2;- 백터의 크기를 미리 지정할 수도 있다.
vector<int> vec1(5);크기를 5로 지정하였지만, 동적 메모리이므로 필요한 만큼 메모리를 늘릴 수 있다.
#include<iostream>
#include<vector>
using namespace std;
void main()
{
int num;
//cout << "배열의 크기 입력 : ";
//cin >> num;
vector<int>arr;
for (int i = 0; i < 3; i++)
{
arr.push_back(i + 1);
}
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << endl;
}
}출력결과
1
2
3
데크(deque)
데크란
- 데크(deque)는 양쪽 끝에서 데이터를 삽입 및 삭제할 수 있는 컨테이너이다. 벡터와의 차이점은 데이터를 끝에서만 삽입, 삭제하느냐 양쪽 끝에서 하느냐의 차이다.
- 그렇다고 벡터에서 앞쪽 삽입, 삭제가 안되는 것은 아니다. Insert를 사용하면 가능하지만 속도가 매우 느리기 때문에 잘 사용하지 않는다.
데크의 사용형태
- 데크의 형식으로 타입이 T형인 데크 객체를 선언한 형태이다.
deque<T> dq;
#include<iostream>
#include<deque>
using namespace std;
void main()
{
deque<int> arr;
for (int i = 0; i < 3; i++)
{
arr.push_back(i + 1);
}
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << endl;
}
}출력결과
1
2
3
#include<iostream>
#include<deque>
using namespace std;
void main()
{
deque<int> arr;
arr.push_back(5);
arr.push_back(4);
arr.push_back(3);
for (int i = 0; i < arr.size(); i++)
{
cout << arr[i] << endl;
}
}출력결과
5
4
3
리스트(list)
리스트란
- 리스트는 이중 연결 리스트로 구현되어 있는 컨테이너이다.
- 연결 리스트는 노드라는 것이 붙어있어서 데이터가 물리적으로 인접해있지 않고, 논리적인 순서를 기억하므로 데이터 삽입, 삭제의 속도가 상대적으로 빠르다.
리스트의 사용형태
- 리스트의 형식으로 타입이 T형인 리스트 객체를 선언한 형태이다.
list<T> lst;
단순 연결 리스트
배열과 연결 리스트의 비교
- 가변 크기를 가지는 자료구조로 연결 리스트(Linked List)가 있다.
- 연결 리스트와 동적 배열은 용도가 같지만 구성 원리나 관리 방법은 질적으로 다르다.
| 배열 | 연결리스트 |
|---|---|
| 인접한 메모리 영역에 연속적으로 배치 자신이 기억할 데이터 값만 갖는다. | 요소들이 메모리 도처에 흩어져서 존재 데이터 외에 연결 상태에 대한 정보인 링크를 추가로 가져야 한다. |
연결 리스트의 특징
- 링크를 하나만 가지는 것을 단순 연결 리스트(Single Linked List), 두 개의 링크를 가지는 것을 이중 연결 리스트(Double Linked List)라고 한다.
- 노드를 구성하는 데이터와 링크는 타입이 다르므로 구조체로 정의한다.
struct Node
{
int value; // 데이터
Node next; // 링크
};- value 멤버는 노드가 기억하는 정보의 실체인 데이터.
- next 멤버는 다음 노드에 대한 포인터를 가지는 링크.
#include<iostream>
#include<list>
using namespace std;
void main()
{
list<int> lst; // 리스트
lst.push_back(5);
lst.push_back(4);
lst.push_back(3);
list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); it++)
{
cout << *it << endl;
}
//for (int i = 0; i < arr.size(); i++)
//{
// cout << arr[i] << endl;
// 리스트의 노드들은 서로 근접한 곳에 위치하지 않고 뿔뿔이 흩어져 있으므로 출력X
//}
}출력
5
4
3
리스트를 출력하기 위해서는 노드를 가리키는 특별한 포인터인 반복자라는 객체를 사용하는데, 바로 iterator라는 녀석이다.
리스트는 데이터가 뿔뿔이 흩어져 있기 때문에 it라는 포인터 변수를 통해서 다음 변수를 찾아가야 한다.
알고 쓰자!