SAYNOT'S HOME

지난 시간에 STL에 대해 알아보았다.

이번시간은 STL 시퀸스 컨테이너 중 많이 활용되는 vector에 대해 공부해보려한다.

긴말필요없이 시작해보자. :)

1. vector란?

vector란 시퀸스 컨테이너 중 하나로 '메모리가 동적으로 할당되는 배열'이다.

이를 이용하여 C++에서 동적 배열을 쉽게 구현할 수 있다.

vector는 원소를 저장할 때 메모리에 연속적으로 저장되며, 이로인한 장점과 단점이 존재한다.

순차적이라 임의 접근시 속도는 빠른편이나, 원소를 삽입하거나 제거할때 모든 원소를 옮기는 과정을 거치다보니 속도가 느릴수있다.

vector를 사용하기 위해선 <vector> 헤더파일을 include 해주어야하며,

std::vector<[데이터타입]> [변수이름] 형식으로 선언해 사용할 수 있다.

(using namespace std;로 std 생략하여 편하게 작성가능)

2. vector - 생성자

vector 생성자는 다음과 같이 사용 가능하다.

• vector<int> vec
  • 빈 vector 컨테이너 vec을 생성
• vector<int> vec(3);
  • 3개의 원소를 갖는 vec을 생성(기본값 초기화)
• vector<int> vec(3, 4);
  • 4로 초기화된 3개의 원소를 갖는 vec을 생성
• vector<int> vec2(vec);
  • vec 컨테이너를 복사한 vec2를 생성
    
    
    

3. vector - 멤버 함수, 멤버 형식

다음은 vector 멤버 함수와 멤버 형식이다.

대표적인 몇몇개를 정리해보았으며 데이터타입이 int라고 가정하고 작성하겠다.

- 멤버 함수

• vec.assign(2, 3);
  • vec에서 3이란 값으로 2개의 원소를 할당
    
• vec.at(3);
  • vec의 3번 인덱스를 참조(범위 점검 > 안전함)
• vec[3];
  
  • vec의 3번 인덱스를 참조(범위 점검 X > 속도빠름)
• vec.front();
  • vec의 첫번째 원소를 참조
• vec.back();
  
  • vec의 마지막 원소를 참조
• vec.clear();
  • vec의 모든 원소를 제거하며 메모리는 그대로 내비둠
• vec.push_back(5);
  • vec에 5란 원소를 push(추가)
• vec.pop_push();
  • vec에 마지막 원소를 pop(제거)
• vec.insert(3, 4); vec.insert(3, 4, 2);
  • vec의 3번 인덱스에 4란 값 삽입
  • vec의 3번 인덱스부터 4개의 2란 값 삽입(밀림)
• vec.erase(iterator)
  • iterator가 가리키고 있는 원소를 제거
  • size는 줄지만 할당된 메모리는 그대로
• vec.clear();
  • vec의 모든 원소를 제거
  • size는 0이되며 할당된 메모리는 그대로
• vec.begin();
  • vec의 첫번째 원소를 가리킴
  • iterator와 같이 사용
• vec.end();
  • vec의 마지막 다음 주소를 가리킴
  • iterator와 같이 사용
• vec.size();
  • vec의 원소 갯수 참조
• vec.capacity();
  • vec이 할당된 공간 크기 리턴
  • 기존 메모리의 2배씩 증가하게 되며, 미리 정해둔 만큼 한번에 동적할당을 해두어 효율을 높이는 것이 목적
  • 원소갯수 = 1 -> capacity = 1, 2 -> 2, 3 -> 4, 4 -> 4, 5 -> 8...
• vec.empty();
  • vec의 size가 0이면 참, 0보다 크면 거짓
• vec.swap(vec2);
  • vec1와 vec2의 원소와 할당된 메모리를 맞바꿈
  • vector<int>().swap(vec); 형태로 할당된 메모리가 0인 임시 객체를 만들어 vec capacity 없앨때 사용 가능
    
    

- 멤버 형식

• allocator_type
  • 메모리 관리자
• iterator
  • 반복자
• pointer
  • value_type *
• refernce
  • value_type &
• reverse_iterator
  • 역 반복자
• size_type
  • 인덱스, 원소 갯수 등
• value_type
  • 원소 형식
    
    
    

4. vector - 연산자

마지막은 vector의 연산자이다.

• ==, != 
  • == : 두 vector 컨테이너의 모든 원소가 같으면 참, 아니면 거짓
  • != : 두 vector 컨테이너에서 하나라도 원소가 다르면 참, 아니면 거짓
• <, >, <=, >=
  
  • vector 컨테이너간 크기 비교
    
    
    
    

5. vector 구조 및 실습

위에서 설명한 vector의 구조는 다음 그림과 같다.

실습은 지난 vector 실습 소스를 수정하여 진행할 예정이다.

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	vector<int> vec; //빈 컨테이너 vec 생성
	vector<int>::iterator vecit;
	vec.assign(1, 10); //비어있는 vec에 10이란 값을 1개 원소 부여
	cout << "vec.at(0) : " << vec.at(0) << endl; //vec의 0번 인덱스 참조(범위점검O)
	cout << "vec[0] : " << vec[0] << endl; //vec의 0번 인덱스 참조(범위점검X)
	vec.push_back(20); //vec에 20 push
	vec.push_back(30); //vec에 30 push
	vec.push_back(40); //vec에 40 push
	cout << "vec의 첫번째 원소 " << vec.front() << endl;
	cout << "vec의 마지막 원소 " << vec.back() << endl;
	cout << "vec의 사이즈 " << vec.size() << endl;
	cout << "vec의 할당된 메모리 " << vec.capacity() << endl;
	
	for (vecit = vec.begin(); vecit != vec.end(); vecit++) { //연산자로 vec의 begin부터 end까지 출력
		cout << *vecit << endl; //참조하는 값 출력
	}
	
	vector<int> vec2(vec); //vec를 복사한 vec2 생성
	cout << "vec2.at(0) : " << vec2.at(0) << endl; //vec2의 0번 인덱스 참조(범위점검O)
	cout << "vec2[0] : " << vec2[0] << endl; //vec2의 0번 인덱스 참조(범위점검X)
	for (vecit = vec2.begin(); vecit != vec2.end(); vecit++) { //연산자로 vec2의 begin부터 end까지 출력
		cout << *vecit << endl; //참조하는 값 출력
	}
	cout << "vec2이 비어있는가? "<< vec2.empty() << endl; //vec2는 안비어있으므로 0
	cout << "vec2.clear 수행" << endl;
	vec2.clear(); //모든 원소 지움
	cout << "vec2이 비어있는가? " << vec2.empty() << endl; //vec2 원소는 모두 비어있으므로 1
	cout << "vec2의 사이즈 " << vec2.size() << endl; //모두 비어있기때문에 0
	cout << "vec2의 할당된 메모리 " << vec2.capacity() << endl; //clear해도 할당된 크기는 그대로
	cout << "vector<int>().swap(vec2) 수행" << endl;
	vector<int>().swap(vec2); //임시객체를 만들어 swap하며 vec2의 메모리 초기화
	cout << "vec2의 할당된 메모리 " << vec2.capacity() << endl; //clear해도 할당된 크기는 그대로
	return 0;
}

실행결과는 다음과 같다.

여기까지 vector 공부를 마친다. 이와같이 당분간 시퀸스 컨테이너 포스팅을 진행할 예정이다.

C++언어에서 빼놓을 수 없는 부분이있다. 바로 STL(Standard Template Library)이다.

매우 다양한 부분에서 STL을 이용할 수 있으며 이는 개발 능률과 바로 연결되므로 매우 유용하다고 볼 수 있다.

오늘부터 몇일간 STL에 있는 컨테이너에 대해 하나하나 공부할 계획이다.

1. STL(Standard Template Library)?

STL이란 '표준 C++ 라이브러리'이다. 프로그램에 필요한 자료구조 및 알고리즘을 템플릿으로 제공한다.

STL의 구성요소는 여러가지가 있다.

• 컨테이너(Container)
• 반복자(Iterator)
• 알고리즘(Algorithm)
• 함수 오브젝트(Function Object) 등

자료들은 컨테이너에 있고 알고리즘은 하나의 수단이다. 이에 접근하기 위해선 반복자를 사용한다고 보면 된다.

이 구성요소를 크게 두개로 나누자면 컨테이너와 알고리즘으로 나눌 수도 있다.

그만큼 STL에서 중요한 요소인데 하나하나 살펴보도록하자.

2. STL - 컨테이너

STL 컨테이너는 객체(기본자료형과 사용자 정의 자료형)를 저장하는 자료구조이다.

클래스 템플릿으로 되어있으며 일반적으로 다음과 같이 나뉜다.

아래 컨테이너들의 자세한 내용에 대해선 추후 포스팅 해나갈 예정이다.

- 시퀀스 컨테이너(Sequence Container) : 일반적인 자료구조와 동일하며, 순차적으로 저장

• array : 배열
• vector : 동적 배열
• deque : 양방향 큐
• forward_list : 단방향 리스트
• list : 양방향 리스트

- 연관 컨테이너(Associative Container) : 일정규칙에 따라 조직화하여 자료를 정렬, 처리

• set : 중복아닌 key 집합
• map : 중복아닌 key, value 집합
• multiset : 중복되는 key 집합
• multimap : 중복되는 key, value의 집합

- 어댑터 컨테이너(Adepter Container) : 시퀀스 컨테이너를 변형하여 다음과 같이 저장

• stack : 스택
• queue : 큐
• priority_queue : 우선순위 큐
  
  
  

3. STL - 알고리즘

STL 알고리즘은 정렬과 같은 개발시 사용되는 기능을 함수 템플릿으로 만들어둔 것이다.

종류가 매우 다양하며 함수 몇몇개를 정리해보았다.

• sort() 알고리즘 : 지정된 정렬 기준에 따라 구간 요소들을 정렬
• find() 알고리즘 : 주어진 값에 일치하는 첫번째 요소 반환
• binary_search() 알고리즘 : 정렬된 컨테이너에 대한 이진 탐색 수행
• max() 알고리즘 : 두 객체 비교하여 큰 값 반환
• min() 알고리즘 : 두 객체 비교하여 작은 값 반환
• replace() 알고리즘 : 지정된 범위 내에 특정 값을 갖는 원소를 찾아 값을 변경
  
  
  

4. STL 반복자

STL 반복자를 사용하여 컨테이너에 저장되어있는 원소들을 접근할 수 있다.

컨테이너와 알고리즘이 함께 동작하도록 만들어주는 역할을 한다. 몇몇가지 연산들을 살펴보겠다.

• begin() 연산자 : 컨테이너에서 첫번째 요소를 반환
• end() 연산자 : 컨테이너의 끝을 표시하는 원소를 반환(마지막의 다음 주소를 가진다.)
• ++, -- 연산자 : ++는 컨테이너에서 다음 요소를 가리킴, --는 이전 요소를 가리킴
• !=, == 연산자 : !=, ==는 두개의 반복자가 같은 요소 가리키는지 확인
• * 연산자 : 반복자가 가리키는 요소의 값을 보여주는(역참조) 연산자
  
  
  

5. 실습

위 시퀸스 컨테이너중 하나인 vector와 연산자를 이용하여 실습을 진행한다.

vector는 뒷 포스팅에서 설명하겠지만 가변적인 배열을 사용하기 위해 사용한다.

순차적이기때문에 읽는 것은 빠르지만 배열 길이가 길어질수록 데이터 처리 속도가 느려진다는 단점이있다.

이제 vector를 이용하여 원소를 push, pop하고 연산자를 이용하여 출력하는 것을 실습해보자(주석 참고).

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	vector<int> vec; //동적 배열 vector
	vec.push_back(1); //vector에 1 push
	vec.push_back(2); //vector에 2 push
	vec.push_back(3); //vector에 3 push
	vector<int>::iterator vecit = vec.begin(); //연산자 선언과 동시에 vec의 첫번째 값 0을 가리킴
	cout << vec[0] << endl; //vec의 첫번째 값 1 출력
	vecit++; //연산자가 다음 요소 가리킴(0 -> 1)
	cout << *vecit << endl; //참조 값 출력
	vecit++; //연산자가 다음 요소 가리킴(1 -> 2)
	cout << *vecit << endl; //참조 값 출력
	//vec.pop_back(); //마지막 값 pop(3 out)

	for (vecit = vec.begin(); vecit != vec.end(); ++vecit) { //vec의 첫요소부터 끝까지 순환, 연산자 1씩 증가
		cout << *vecit << endl; //연산자가 참조하는 값 출력(1, 2, 3)
	}
	return 0;
}

여기까지 STL 공부를 마친다. 뒤부턴 vector부터 하나하나 STL에 대한 포스팅을 진행할 예정이다.

C++ 코드를 작성하다보면 클래스나 함수를 사용할때 다양한 자료형을 처리해야하는 경우가 생긴다.

이럴 경우 템플릿(Template)을 이용하면 쉽게 작성이 가능하다.

이번 시간엔 템플릿에 대해 알아보겠다.

1. 템플릿(Template)?

템플릿이란 여러 자료 형으로 클래스나 함수를 사용할 수 있도록 만들어 놓은 '틀'이다.

아래 그림과 같이 어떠한 자료형이 들어왔을때 템플릿을 이용하면 재선언없이

클래스나 함수를 해당 자료형으로 사용할 수 있게된다.

템플릿은 함수 템플릿과 클래스 템플릿으로 나누어지며 차근차근 설명해보록 하겠다.

2. 함수 템플릿

함수 템플릿은 말그대로 여러 함수를 만들어낼 수있는 틀과 같다.

일반적으로 다른 자료형을 함수에 적용시키고자 할때 함수 오버로딩을 사용하여 해결한다.

그러나 사용자가 직접 정의한 타입을 해당 함수에 적용시키기 위해선 함수 오버로딩 사용은 제한적이다.

이럴때 함수 템플릿을 사용한다.

자료형이 정해지지않은 두 수를 더하고 반환하는 함수를 만들어보자. 형태는 다음과 같다.

#include <iostream>
using namespace std;

template<typename T>
T Sum(T a, T b) {
	T tmp;
	tmp = a + b;
	return tmp;
}

int main(void) {
	int a = 3, b = 2;
	double c = 3.3, d = 2.2;
	int res1 = Sum(a, b);
	double res2 = Sum(c, d);
	cout << "res1 = " << res1 << ", res2 = " << res2 << endl;
	return 0;
}

코드를 보면 int 형과 double 형의 자료형 데이터들을 하나의 함수에서 더하기를 처리하고 받아오는 것을 볼 수 있다.

우선 template<typename T> 형태로 템플릿 사용을 선언한다.

typename(class로 작성 가능)을 정하고 자료형 부분에 해당 타입이름인 T를 넣어준다.

여기서 T는 템플릿 매게변수이며 template<typename T1, typename T2> 형태와 같이 여러개 선언도 가능하다.

이제 들어오는 값의 자료형에 따라 알맞게 해당 함수에서 데이터를 처리하게 된다.

실행 결과는 다음과 같다.

3. 클래스 템플릿

클래스 템플릿은 여러 클래스를 만들어낼 수 있는 틀이다.

함수 템플릿과 차이점이 있는데 클래스 템플릿은 함수 템플릿과 달리 오버로드가 되지않는다.

또하나의 차이점은 함수 템플릿은 완전 특수화만 가능하고 부분 특수화는 오버로드를 통해서 구현하는 수밖에없고,

클래스 템플릿은 완전 특수화와 부분 특수화가 모두 가능하다는 특징이 있다.

*특수화 : 특정 타입에 대해서만 다르게 동작하도록 만드는 것

자료형이 정해지지않은 두 수를 더하고 출력하는 함수를 포함한 클래스를 만들어보자. 형태는 다음과 같다.

#include <iostream>
using namespace std;

template<typename T>
class Sum {
private:
	T res;
public:
	Sum(T a, T b) : res(a+b) {}
	void printSum() {
		cout << res << endl;
	}
};

int main(void) {
	int a = 3, b = 2;
	double c = 3.3, d = 2.2;
	Sum<int> isum(a, b);
	Sum<double> dsum(c, d);
	isum.printSum();
	dsum.printSum();
	return 0;
}

template<typename T>로 함수 템플릿과 같고 클래스를 선언한다.

이후 private으로 템플릿 매게변수로 res를 선언해주고 printSum()함수로 매게변수로 받아온 a와 b의 합을 출력한다.

참고로 Sum<int> isum(a, b)를 보면 알 수 있겠지만 클래스의 경우 함수 템플릿과 달리 자료형 정보를 담아줘야 한다.

실행 결과는 다음과 같다.

4. 장점과 단점

장점 : 타입별로 클래스나 함수를 일일히 만들 필요가 없어진다.

단점 : 실행파일 용량이 커질수도 있으며 컴파일 시간이 길어진다.

추가적으로 C++14부터 변수 템플릿이라는게 등장하는데 관심있는 독자분께선 추가로 찾아서 공부하시길 바란다.

여기까지 템플릿에 대한 공부를 마친다. 계속해서 사용해보며 익숙해지는 것이 우선인 것같다. 추후 포스팅은 해당 포스팅을 시작으로 STL에 대한 내용을 본격적으로 다뤄보려고 한다.

알고리즘을 평가할땐 수행시간과 메모리 사용량을 기준으로 두게되는데 시간복잡도가 수행시간에 해당하며, 공간 복잡도가 메모리 사용량에 해당된다. 본 포스팅에선 이 중 시간복잡도에 대해 알아보려고 한다.

1. 시간복잡도

시간복잡도란 '입력된 데이터가 출력될 때까지 걸리는 시간'이다. 곧 알고리즘이 수행되는 시간이다.

시간복잡도가 낮으면 말그대로 입력부터 출력까지의 속도가 빠르며, 시간복잡도가 높이면 속도가 느려지게 된다.

2. 점진적 표기법 3가지

시간복잡도를 표기할때 3가지 표기법이 존재한다.

(1) 오메가(Ω) 표기법 > 제일 좋은 경우

(2) 세타(Θ) 표기법 > 평균적인 경우

(3) 빅-오(O) 표기법 > 제일 나쁜 경우

이 중 알고리즘이 최악일 경우에 평균과 가까운 성능으로 예측이 가능하므로

일반적으로 빅-오 표기법을 많이 사용한다.

3. 시간복잡도 단계

시간복잡도 단계는 위 그래프와 같으며 이를 정리해보면 아래와 같다.

4. 시간복잡도 계산

만약 input으로 문자열을 2개 입력받아 2개의 문자열이 같은지 판단하는 함수를 짠다고 가정해보자.

대소문자는 구별하지 않을 것이다. 이 코드에서 시간복잡도는 얼마가 될까?

설명을 위하여 위와 같이 간단히 짜보았다. 빅-오로 표기할 것이기 때문에 최악의 경우를 판단해보자.

위 for문은 두 문자열의 길이만큼 n번씩 2번 돌며 실행이된다.

그럼 여기서 상수와 같은 부분은 모두 제외하고, 총 O(n^2)라는 시간 복잡도를 가지게 되는 것을 확인할 수 있다.

여기까지 시간복잡도에 대한 공부를 마쳤다. 과제를 드리자면 위의 코드의 복잡도를 O(nlogn) 복잡도 보다 낮게 만들 수 있다. 향후 함께 실습해보는 시간을 가지겠다.