[TIL 28장] STL 개론(feat. 자료구조), 컨테이너, 시간 복잡도, 벡터

오늘의 TIL 목차 (22. 09. 14)

STL 개론 ( 컨테이너, 알고리즘, 함수 객체, 조건자 )
시간 복잡도
벡터

STL ; Standard Template Library

[ STL ]

: 반복자를 가지고 동작하는 C++ 표준 템플릿 라이브러리, 표준에 맞게 어떠한 도구들을 모아놓은 것

[ STL 구성 요소 ]
1. 컨테이너 ( 클래스 템플릿 )
2. 알고리즘 ( 함수 템플릿 )
3. 함수 객체 ( 함수처럼 사용할 수 있는 객체 ) 
4. 반복자(=이터레이터) ( STL을 가리키는 포인터와 유사한 객체 ) * 매우 중요 *

* 라이브러리란?
: 소프트웨어를 개발하기 쉽게 어떤 기능을 제공하는 도구들
: 다른 프로그램들과 링크되기 위하여 존재하는 하나 이상의 서브루틴이나 함수들의 집합 파일,
함께 링크될 수 있도록 보통 컴파일된 형태인 목적코드 형태로 존재 
- 코드 재사용을 위한 기법
- 암호화를 통해 중요 기술의 유출 방지
- 개발자들은 라이브러리를 통한 개발 시간 단축

■ 기능 / 주의

자료구조 클래스와 알고리즘 등을 미리 만들어 놓은 라이브러리이다.
STL은 파일 저장 방식으로 헤더파일은 반드시 제공, 함수의 정의부는 바이너리화하여 암호화해서 제공한다.
- 함수의 정의부를 암호화하여 제공하는 것을 라이브러리라고 함

[ 자료구조 ]

: 무수히 많은 자료들을 어떻게 정리할 것인지에 대한 학문적인 생각/측면

=> 자료를 정렬, 삽입, 삭제, 탐색

[ 기초적인 자료구조 ]
1. 리스트 ( 동적 배열 ) * 매우 중요 *

2. 스택 ( LIFO 기법 )

3. 큐 ( FIFO 기법 )

4. 트리

컨테이너

[ 컨테이너 ]

: 자료구조를 미리 구현해놓은 객체, 템플릿 클래스 집합 (동일한 타입의 객체를 저장/관리할 목적으로 만든 추상화 클래스)

[ 컨테이너 분류 기준 ] * 매우 중요 *
1. 원소 배치 방식에 따른 분류
	- 표준 시퀀스 컨테이너 : vector, deque(doubled ended queue), list
    - 표준 연관 컨테이너 : set, multiset, map, multimap (multi가 붙으면 중복 허용, 아니면 미허용)
    
2. 메모리 방식에 따른 분류
	- 배열 기반의 컨테이너 : vector, deque
    - 노드 기반의 컨테이너 : list, set, multiset, map, multimap
    
 [ 컨테이너는 아니지만 관련된 것 ]
1. 컨테이너 어댑터 ( 어댑터 : ~를 지원하다, 전환하다 )
: 추가 기능 없이 자료구조의 기능만 가지고 있는 것
: queue, priority queue(우선순위 큐), stack

2. 근사 컨테이너 
: 컨테이너에 근사하지만 템플릿의 조건을 100% 충족하지 못한 컨테이너
: string, wstring (만약 string이 컨테이너였다면 표준 시퀀스 컨테이너, 배열 기반의 컨테이너로 분류)

[ 분류별 컨테이너에 대한 자세한 설명 ]
1. 원소 배치 방식에 따른 분류
- 표준 시퀀스 컨테이너 (시퀀스 : 순차열/순열)
: 원소를 나열할 떄 일정한 방향성을 가지고 순차적인 특성을 가진 컨테이너

@ vector : 반개 특성을 가짐
@ deque : 뒤뿐만 아니라 앞으로도 삽입이 되지만, 읽는 순서가 순차적이라 시퀀스 컨테이너
@ list : 반개 특성으로 순차적으로 데이터가 삽입됨

* 반개 특성 [ , )
[ 앞으로 들어올 가능성이 없고
) 뒤로 들어올 가능성은 있다

- 표준 연관 컨테이너
: 특정 정렬 기준에 따라 원소가 자동 정렬되는 컨테이너

@ tree : 한 노드의 값을 가지고 크고 작음을 기준으로 정렬해나감
@ set, multiset, map, multimap

* 연관 컨테이너는 순차적인(시퀀스) 정렬을 할 수 없음
무작위 수를 순서대로 넣었을 때 무작위 수의 크기에 따라 크고작음을 기준으로 자동 정렬해버림

2. 메모리 방식에 따른 분류
- 배열 기반의 컨테이너
: 배열처럼 연속적인 형태의 메모리 저장 방식

@ vector, queue

- 노드 기반의 컨테이너
: 서로 관련 없는 각각의 메모리 공간 노드를 링크하여 읽어들이는 메모리 방식

@ list : 정적 배열처럼 연속된 저장 공간이 아닌 노드들을 포인터 객체로 링크하여 순차적으로 읽어들임
@ set, multiset, map, multimap

그 외 STL 구성요소

[ 알고리즘 ]

: 자료구조를 기반으로 정렬, 삽입, 삭제 등의 기능이 정리되어 있는 함수 템플릿, 동작하는 원리를 잡아놓은 체계

: 어떤 일을 해결하기 위한 방법이나 문제를 해결하기 위한 절차 등을 단계적으로 나열한 것

■ 기능 / 주의

알고리즘은 자료구조를 기반으로 한 수학적인 측면의 코드이다.
- 정렬 시 for문으로 복잡하게 짜야하는 코드를 STL 알고리즘인 sort()를 이용하면 한번에 정렬해준다.
- find, sort, search 등이 존재
알고리즘 사용시 <algorithm> 헤더파일을 포함시켜야 한다.

[ 함수 객체 ] = 함수자

: 함수처럼 동작하는 객체로 operator와 () 연산자를 통해 조건자를 만들기 위해 생성하는 문법, 주로 함수 템플릿의 함수 포인터 대신 조건자로 삽입해준다.

[ 반복자 ] = Iterator

: 포인터와 유사한 객체로 컨테이너에 저장되어 있는 요소를 순회하고 접근해서 읽기 쓰기를 가능하게 하는 객체나 클래스

[ 반복자의 성질 ]
1. 컨테어너 안의 요소에 접근
2. 컨테이너 안의 모든 요소 읽기, 쓰기, 순회가 가능

[ 반복자의 종류 ]
- 각 컨테이너는 자신만의 반복자를 가짐
1. 입력 반복자
2. 출력 반복자
3. 순방향 반복자
4. 양방향 반복자
5. 임의 접근 반복자

※ 포인터와 유사하나 포인터 아님

시간 복잡도

[ 시간 복잡도 ]

: 입력 값의 변화에 따른 연산 횟수에 따라 특정 알고리즘이 문제를 해결하는데 걸리는 시간

=> 빅오 표기법(최악의 경우), 오메가 표기법(최선의 경우), 세타 표기법(평균의 경우)으로 시간 복잡도를 표기

■ 빅-오(Big-O) 표기법

: 알고리즘의 성능을 수학적으로 표기해주는 표기법
: 시간 복잡도의 일반적인 표기법, 최악의 경우를 계산하는 방식

■ 빅-오(Big-O) 표기법 종류 4가지

1. 상수 시간 복잡도, O(1) // Best

: 원소 개수와 상관 없이 처리 시간은 동일하다.

// 인자의 크기와 상관없이 일정한 속도로 결과를 반환함
F(int[] n)
{
	// 삼항 연산자, ? 기준으로 참이면 :의 왼쪽, 거짓이면 : 오른쪽 반환
	return (n[0] == 0) ? true : false; 
}

2. 로그 시간 복잡도, O(log n) // Good

: 원소가 증가할수록 처리 시간이 조금씩 증가한다.

// 이진 검색 ; 원소를 기준으로 절반씩 제거하며 비교하는 검색 방법
F(k, arr, s, e)
{
	if (s > e) return -1;
	m = (s + e) / 2;
	if (arr[m] == k) return m;
	else if (arr[m] > k) return F(k, arr, s, m - 1);
	else return F(k, arr, m + 1, e);
}

3. 선형 시간 복잡도, O(n) //Bad

: 입력 데이터 n의 크기만큼 비례해서 n의 크기만큼 처리 시간이 증가한다.

// n의 원소의 개수가 많을수록 실행 횟수도 증가함
F(int[] n)
{
	for (i = 0; sizeof(n) / sizeof(int) > i; ++i)
	{
		cout << n[i] << endl;
	}
}

4. 지수 시간 복잡도, O(n^2) // Worst

: n의 크기가 증가할수록 n의 제곱만큼 처리 시간이 증가한다. ( for문, 버블 정렬 )

// 이중 for문처럼 원소의 개수가 많을수록 원소의 제곱만큼 실행 횟수가 증가하는 것
F(int[] n)
{
	for (int i = 0; sizeof(n) / sizeof(int) > i; ++i)
	{
		for (j = 0; sizeof(n) / sizeof(int) > j; ++j)
			cout << i + j << endl;
	}
}

=> 시간복잡도가 가장 낮은 알고리즘을 선택하여 코드를 설계해야 한다.

※ 알고리즘의 실제 러닝타임을 표시하는 것이 아닌 데이터나 사용자의 증가율에 따른 알고리즘 사용률을 예측

벡터

[ 벡터 ]

: 동적 배열을 기반으로 하는 컨테이너, 동적 배열의 메모리 해제 기능을 포함한 여러 기능을 지원하는 클래스 템플릿이다.

#include <vector> // 벡터를 사용하기 위해서 헤더파일 포함

void main(void) {
vector<자료형> vector(배열 개수); // 벡터 템플릿을 이용한 객체 생성

※ 수학의 벡터와 다름, 여기서의 벡터는 연속된 메모리 공간의 동적 배열로 메모리 해제 기능을 포함한 STL 컨테이너이다.

■ 기능 / 주의

인덱스 접근(임의 접근)이 가능하여 탐색에 용이하다.
- 컴퓨터는 원소의 개수와 상관없이 인덱스 위치로 바로 접근하기 때문에 탐색에 용이
반개 특성 [ , ) 으로 앞에서 삽입할 수 없으며 맨 끝에서부터 삽입이 가능하다
중간 삽입/삭제 시 원소 개수에 비례하여 실행 횟수가 증가하기 때문에 시간 복잡도가 증가한다.
일반 삽입/삭제 시 원소의 개수와 상관 없이 맨 끝, 맨 앞에서 이뤄지기 때문에 상수 시간 복잡도이다. (속도 빠름)
동적 배열이므로 원소가 추가될 때마다 재할당해야해서 정적 배열보다 속도가 느리다.
- 이를 보완하기 위해 원소를 삭제해도 메모리 공간을 삭제하지 않고 남겨둔다.
- 메모리 추가를 고려하여 이미 할당되었던 공간을 삭제하지 않고 해당 공간에 값을 채우기 위해서이다.
벡터는 중간 삽입/삭제 시 인덱스 재배치가 이뤄지기 때문에 시간 복잡도가 증가하여 용이하지 않다.
위와 같은 특성 때문에 벡터는 주로 개수가 정해져있는 것들을 이용해야 할 때 주로 사용된다.
- ex. 타일맵의 타일을 저장하는 용도 ( 타일은 개수가 정해져있는 경우가 많아 벡터를 이용하여 파일 관리에 용이)
벡터는 memset으로 0 초기화를 하면 안된다. 초기화 시 반복자까지 0으로 사라져 반복자 접근이 불가능해진다.

■ 예시

- STL에 정의된 vector를 직접 직접 구현해본다면?

#include "stdafx.h"
// #include <vector> // STL vecotor 컨테이너를 사용하려면 포함

// 원래는 이러한 vector라는 이름의 클래스 템플릿이 이미 정의되어 <vector> 헤더파일에 포함된 것
// 클래스는 정적 멤버를 제외하고 정의부를 선언부(헤더파일)에 같이 선언해줌
template<typename T>
class vector
{

public:
	vector(int _iSize) : m_iSize(_iSize) { m_vector = new T[m_iSize]{ 0 }; } // 생성자에서 매개변수로 받은 크기만큼 동적할당
	~vector() { SAFE_DELETE(m_vector); } // 벡터는 동적 배열의 메모리 누수를 방지해 메모리 해제 기능을 지원하는 듯함

public:
	// 동적 할당 해제는 매크로보다 템플릿을 이용할 것 (디버깅을 할 수 있다는 장점 떄문)
	void SAFE_DELETE(T* _vector) { if (_vector) { delete[] _vector; _vector = nullptr; } }

	int size(void) // 벡터의 배열 크기를 반환하는 함수
	{
		return m_iSize;
	}

	//void Intialize(T A) // 벡터 원소 삽입 방법을 모르겠어서 임시로 만든 함수
	//{
	//	m_vector[0] = A;
	//}
	void Intialize(T A, T B) // 벡터 원소 삽입 방법을 모르겠어서 임시로 만든 함수
	{
		m_vector[0] = A;
		m_vector[1] = B;
	}

	void emplace_back(T _input) // 삽입 시 끝에 원소가 추가되는 함수
	{
	
		// 왜 memset이 제대로 안 이뤄지는지 모르겠음 ( 1 증가된 배열은 잘 생성되서 주소 넘겨받음 )
		T* Temp = new T[++m_iSize]; // 크기가 1증가된 임시 동적 배열 생성, m_iSize도 1증가됨
		memcpy(Temp, m_vector, sizeof(m_vector)/sizeof(T)); // 기존 배열 확장된 배열에 삽입
		SAFE_DELETE(m_vector); // 기존의 배열 메모리 공간 해제

		/* 입력한 수만큼 추가하여 저장할 때 사용하는 바법
		if (nullptr == m_pInfo)	// 최초 시점
			m_pInfo = new INFO[iInput];

		else  // 기존에 데이터가 있던 경우
		{
			INFO*		pNewInfo = new INFO[m_iSize + iInput];

			memcpy(pNewInfo, m_pInfo, sizeof(INFO) * m_iSize);

			SAFE_DELETE_ARRAY(m_pInfo);

			m_pInfo = pNewInfo;
		}
		*/

		Temp[m_iSize] = _input; // 맨 끝 m_iSize 위치에 매개변수 값 넣어줌
		m_vector = Temp; // 확장된 메모리 공간의 주소를 받음
	}

	void print_vector(void)
	{
		for (int i = 0; m_iSize > i; ++i)
		{
			cout << m_vector[i] << endl;
		}
		cout << endl;
	}

private:
	int m_iSize;
	T* m_vector; // T 자료형의 동적 할당용 포인터
	//char* m_p; // 벡터의 끝 자료를 가리키기 위한 포인터, 필요한가?
};

void main(void)
{
	vector<int> v(2); // 배열 크기 2인 int형 벡터 생성
	v.Intialize(5, 10); // 배열 0, 1에 매개변수 삽입
	v.print_vector();
	v.emplace_back(15);
	v.print_vector();
}

[ deque ]

: 배열 기반 컨테이너(시퀀스), vector에서 앞 원소 삽입/삭제 기능이 추가된 컨테이너

[ deque보다 vector 선호 ]
deque는 정해진 메모리 블럭만큼 미리 할당,
중간 삽입/삭제 시 앞 뒤로 이동이 일어나 vector보다 느려서 잘 안 쓰임

'C++' 카테고리의 다른 글

[TIL 30장] 벡터 함수(feat. 2차원벡터), 알고리즘(feat. 조건자) (1)	2022.09.19
[TIL 29장] 컨테이너 함수(feat. deque), 반복자 (0)	2022.09.15
[TIL 27장] 템플릿(함수 템플릿, 클래스 템플릿), 템플릿 특수화(feat. static 템플릿) (0)	2022.09.13
[TIL 26장] 연산자 오버로딩, 함수 객체, 함수 포인터, inline (0)	2022.09.13
[TIL 25장] 캐스팅(업캐스팅, 다운캐스팅), 캐스팅 연산자 (0)	2022.09.08

다코딩_개발일지

[TIL 28장] STL 개론(feat. 자료구조), 컨테이너, 시간 복잡도, 벡터

STL ; Standard Template Library

[ STL ]

■ 기능 / 주의

[ 자료구조 ]

컨테이너

[ 컨테이너 ]

그 외 STL 구성요소

[ 알고리즘 ]

■ 기능 / 주의

[ 함수 객체 ] = 함수자

[ 반복자 ] = Iterator

시간 복잡도

[ 시간 복잡도 ]

■ 빅-오(Big-O) 표기법

■ 빅-오(Big-O) 표기법 종류 4가지

1. 상수 시간 복잡도, O(1) // Best

2. 로그 시간 복잡도, O(log n) // Good

3. 선형 시간 복잡도, O(n) //Bad

4. 지수 시간 복잡도, O(n^2) // Worst

벡터

[ 벡터 ]

■ 기능 / 주의

■ 예시

[ deque ]

'C++' 카테고리의 다른 글

티스토리툴바

[TIL 28장] STL 개론(feat. 자료구조), 컨테이너, 시간 복잡도, 벡터

STL ; Standard Template Library

[ STL ]

■ 기능 / 주의

[ 자료구조 ]

컨테이너

[ 컨테이너 ]

그 외 STL 구성요소

[ 알고리즘 ]

■ 기능 / 주의

[ 함수 객체 ] = 함수자

[ 반복자 ] = Iterator

시간 복잡도

[ 시간 복잡도 ]

■ 빅-오(Big-O) 표기법

■ 빅-오(Big-O) 표기법 종류 4가지

1. 상수 시간 복잡도, O(1) // Best

2. 로그 시간 복잡도, O(log n) // Good

3. 선형 시간 복잡도, O(n) //Bad

4. 지수 시간 복잡도, O(n^2) // Worst

벡터

[ 벡터 ]

■ 기능 / 주의

■ 예시

[ deque ]

'C++' 카테고리의 다른 글

'C++' Related Articles

티스토리툴바