Map은 연관 컨테이너에 속하는 컨테이너의 한 종류이다. 파이썬의 Dictionary 사전과 같은 자료구조를 갖는다.
Map은 사전처럼 Key(단어)를 갖고, 그 Key에 해당하는 Value(뜻)를 갖는다. 왼쪽 그림처럼 Apple이라는 단어를 찾으면 사과라는 뜻이 나오 듯, key 값을 넣으면 value 값이 나오는 형태이다.
Map에 자료를 추가하거나, 자료를 찾기 위해서는 insert(), find() 등의 함수를 사용하지만 Map의 특성으로 인해서 추가와 탐색을 한 형태로 나타낼 수 있다.
my_map["apple"] = "핸드폰";
my_map["apple"];
"apple" key가 my_map내에 있을 경우 (value = "사과")
(1) "핸드폰" 값으로 대입 갱신.
(2) "사과"를 반환
"apple" key가 my_map내에 없을 경우
(3) key - apple / value - 핸드폰으로 map 컨테이너에 추가 됨.
(4) 반환되는 값이 없다.
첫 번째, 기존의 동일한 key가 map에 존재하는데, 동일한 key로 다시 value 값을 등록하는 경우는 갱신된다. 두 번째, 기존의 동일한 key가 map에 존재한다면, 기존의 key값에 해당하는 value 값을 반환시킬 수 있다. 세 번째, key가 map에 존재하지 않는데, key로 value 값을 등록하는 경우 map에 새롭게 추가된다. 네 번째, key가 map에 존재하지 않는다면, key 자체도 없고 그에 따라서 value도 없으므로 반환되는 값이 없다.
간단한 예제로 마무리 지을 것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// https://colorscripter.com/
#include<iostream>
#include<string>
#include<map>
usingnamespacestd;
int main(void)
{
map<string, string> my_map; // key에 해당하는 string, value에 해당하는 string
my_map["a"] ="apple";
my_map["b"] ="banana";
my_map["c"] ="carrot";
cout<<"--- key로 접근하여 value을 출력하기. "<<endl;
cout<< my_map["a"] <<endl;
cout<< my_map["b"] <<endl;
cout<< my_map["c"] <<endl;
cout<<"--- iterator 이용하여 key와 value 출력하기. "<<endl;
map<string, string>::iterator it;
for (it = my_map.begin(); it != my_map.end(); it++)
리스트는 벡터와 디큐와 마찬가지로 순차 선형 콘테이너이다. 그래서 외부에서 볼 때에는 벡터와 완전히 동일한 듯 보이지만, 구조 자체부터 크게 다르다.
벡터는 순차 배열 형태였다면, 리스트는 이중 연결 리스트로 구현된다. 다음 그림과 같이 말이다.
위와 같은 이중 연결 리스트로 구현되어 있기 때문에 벡터에서의 순회 방법에서 아주 조금의 차이가 있다. begin() 부터 end() 까지 주소 값 비교를 통한 순회가 의미가 없기 때문이다. 무조건 노드의 링크를 타고 가는 방식의 포인터 연산으로 접근해야한다. ( 이는 연산자들이 오버로딩되어 자동으로 포인터 연산 되도록 구현되어 있음.)
또한 링크드 리스트로 구현되어 있기 때문에 인덱스가 없다. 그렇단 소리는 임의 접근이 불가능하다는 소리이고, 탐색을 할 때는 모든 노드를 링크를 타고 순회해야한다.
다만, 삽입이나 삭제를 할 때, 벡터에서는 요소들의 인덱스 재 조정 그리고 추가 메모리 공간 확장 및 복사/확장이 필요하지만 리스트에서는 링크를 변경하면 되므로 삽입/삭제 시에는 속도가 빠르다는 장점이 있다.
결국, 중간에서의 삽입 및 삭제가 빈번한 경우 사용하면 적합할 것 같다.
s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<list>
usingnamespacestd;
void print_list(list<int>& l)
{
list<int>::iterator list_it;
for (list_it = l.begin(); list_it != l.end(); list_it++) // 링크드리스트이기 때문에 <, > 연산이 의미가 없다.
cout<<"list iterator value : "<<*list_it <<endl;
return;
}
bool cond(int n) // 기본 조건에 의한 삭제를 위한 함수.
{
return n >901;
}
bool desc(int a, int b) // sort의 내림차순을 위함.
{
return a > b;
}
int main(void)
{
list<int> my_list;
list<int> new_list;
cout<<"push_front, push_back 함수 호출 --- --- ---"<<endl;
my_list.push_back(100);
my_list.push_back(200);
my_list.push_front(900);
print_list(my_list); // 900 100 200
cout<<"insert 함수 호출 --- --- ---"<<endl;
my_list.insert(--(my_list.end()), 999);
print_list(my_list); // 900 100 999 200
cout<<"remove & remove_if 함수 호출 --- --- ---"<<endl;
my_list.remove_if(cond); // 901 제거
my_list.remove(100); // 100 제거
print_list(my_list); // 900 200
cout<<"reverse 함수 호출 --- --- ---"<<endl; // 원소들을 뒤집어서 나열
my_list.reverse();
print_list(my_list); // 200 900
cout<<"sort 함수 호출 오름차순 --- --- ---"<<endl;
my_list.sort();
print_list(my_list); // 200 900
cout<<"sort 함수 호출 내림차순 --- --- ---"<<endl; // 식을 함수 형태로 주어 내림차순 구현
my_list.sort(desc);
print_list(my_list); // 200 900
cout<<"unique 함수 호출 --- --- --- "<<endl; // 인접한 데이터 중에 중복되는 요소들을 제거한다.(연속적으로 나오는 중복을 허용 X)
new_list.insert(new_list.begin(), 55);
new_list.insert(new_list.begin(), 33);
new_list.insert(new_list.begin(), 55);
new_list.insert(new_list.begin(), 55);
new_list.unique();
print_list(new_list); // 실행결과 : 55 33 55
cout<<"merge 함수 호출 --- --- --- "<<endl;
new_list.sort();
my_list.sort(); // 각각의 리스트들은 꼭 정렬되어 있어야 한다.
new_list.merge(my_list); // 복사(copy)하는 것이 아니라 요소의 이동(move)이다.
print_list(new_list); // 실행결과 : 33 55 55 200 900
print_list(my_list); // 실행결과 : 비어 있음 -> 이동했기 때문에
cout<<"splice 함수 호출 --- --- --- "<<endl;
my_list.push_front(300);
my_list.push_front(100);
my_list.splice(my_list.begin(), new_list); // 복사(copy)하는 것이 아니라 요소의 이동(move)이다.
34번 라인처럼 insert시, 임의 접근이 불가능하므로 포인터 연산(오버로딩된)을 통해 위치를 명시한다. 그리고 remove_if 함수를 통해 조건부 삭제가 가능한데, 이 때 조건은 13번 라인의 bool 반환 타입의 함수 형태로 기입한다. 함수의 이름을 적으면 된다.
50번 라인에서 sort 함수를 통해 기본적인 오름차순 정렬이 가능한데, 내림차순이나 다른 형태의 정렬을 위해선 remove_if 처럼 조건을 전달해야한다. 17번 라인의 함수 이름을 전달하면 된다.
59번 라인의 unique 함수는 인접한 데이터 중에 중복 요소가 있으면 중복을 제거한다. 내가 가만히 보니, 11/11/22/22 는 11/22 로 중복을 제거하지만 11/22/11/22인 경우는 중복이 제거가 되지 않는다... 참으로 이상하다
62번 라인과 70번 라인의 merge와 splice는 병합의 기능을 하는데, 참으로 불편한게 이 두 함수를 사용하기 위해서는 병합할 두 요소들이 모두 일정한 방법으로 정렬이 되어 있어야 한다는 점이다. 참으로 딱하구나... 또한 병합할 때에는 요소들 간의 복사가 이루어지는게 아니라 잘라내기&붙혀넣기 즉, 요소의 이동이 이루어지기 때문에 병합하는 쪽은 merge() 및 splice() 함수 호출 후에는 텅 비어있다.. 그런데 이것은 뭐 당연하다고 생각된다. 링크를 바꾸는 것이기 때문에!
벡터가 무엇인지 한번 찾아보았다. 간단하게 정의하자면 순차 컨테이너에 속하는 동적 배열이다. C의 배열과 똑같이 행동한다.
그렇다면 C의 배열과 벡터의 차이점은 무엇일까?
1. 타입에 상관없이 모든 타입에 대해서 일반적인 배열을 만들 수 있다. => int, double, char, int *, 객체 가릴 것 없이 모든 타입에 대해서 배열을 만들 수 있다는 이야기이다. 2. 배열의 크기 조절이 자동으로 이루어지며, 추가 및 삭제에 대한 인터페이스를 제공한다 => 배열에 값을 추가하기 위해 새롭게 더 큰 메모리를 할당하고, 값을 복사하고 기존 메모리를 해체하고... 이러한 과정들을 알아서 해준다는 것이다! 개꿀!!!!ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
그러나 2번과 같은 장점에 따른 단점 또한 존재한다.
C++의 벡터는 무조건 데이터를 선형적으로 만들려고 한다.( 그렇기에 이름도 순차 컨테이너. ) 중간에 끊긴다거나 하면 안된다는 소리이다.
왼쪽과 같은 형태는 가능하지만, 오른쪽과 같은 형태는 안된다는 소리이다. 이러한 선형을 유지해야하는 특징 때문에 값을 추가할 때 단점이 발생한다.
메모리 공간이 충분하여 기존에 이어서 확장한 후 값을 그냥 더 추가할 경우에는 문제가 안된다. 아래의 그림처럼 말이야.
그런데 다음 그림과 같이 기존의 6개 메모리 뒤에 다른 관련없는 값이 이미 할당되어 기존의 6개 메모리 뒤에 연이어 추가 확장이 불가능한 경우는 문제가 발생한다.
이러한 경우에는
이렇게 복사, 확장, 추가, 소멸 등의 여러 작업들이 필요하니 속도가 느려지는 단점이 있다.
설명은 이 정도로 정리하도록 하고, 매우 간단한 코드를 기록해보자.
7번 라인에서 볼 수 있듯이 템플릿 문법을 활용하여 사용한다. 반복자를 활용하지 않은 가장 기본 기본 기본적인 벡터 예제이다. 실행 결과는 매우 뻔하기 때문에 생략~
9번 라인에서 처럼 .size() 함수를 통해 벡터가 정의된 길이를 확인할 수 있다.
다음 vector 에서 제공하는 push_back 함수를 사용한 예이다. push_back 함수를 사용하면 벡터 열에 손쉽게 데이터를 추가할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<vector>
usingnamespacestd;
int main(void)
{
int max_number =0;
int val =0;
vector<int> num_vector;
while (true)
{
cout<<"벡터에 추가할 숫자를 입력하세요 (-123123 입력 시 종료) : ";
cin>> val;
if (val ==-123123)
break;
else
num_vector.push_back(val);
}
max_number = num_vector[0];
for (int i =0; i < num_vector.size(); i++)
{
if (num_vector[i] > max_number)
max_number = num_vector[i];
}
cout<<" 입력한 값 중에서 최대 값은 "<< max_number <<" 입니다."<<endl;
오늘은 컨테이너, 이터레이터, 알고리즘이란 무엇이며, 무엇이 있는지 학습한 결과를 기록한다.
Container
컨테이너는 뜻 그대로 그릇, 무언가 담을 수 있는 역할을 한다. 즉, 자료 및 값을 저장하는 역할을 한다. 이 그릇의 모양이나 크기에 따라 담기를 권장되는 내용물이 다르고 취급 방법이 다르다.(컵이라는 그릇에 라면을 담을 수는 있지만 효율적이지 못한 것처럼.)
먼저, 컨테이너에는 순차 컨테이너, 연관 컨테이너, 컨테이너 어댑터 등이 있다.
이게 무슨 소리인가?
순차 컨테이너 : 뭔가 자료들이 순차적으로 들어가는거..? 연관 컨테이너 : 연관되어서 들어가는거..? 쌍으로 연관되어서 들어가는 것인가? 컨테이너 어댑터 : 어댑터란 다른 전기나 기계 장치를 서로 연결해서 작동할 수 있도록 만들어 주는 결합 도구 라는 정의가 있는 것으로 보아, 컨테이너와 컨테이너를 변환할 수 있는 그런게 아닐까?
나는 리얼로 위와 같이 생각했다. 내가 조사해 본 컨테이너들은 다음과 같다.
순차 컨테이너
말 그대로 순차적으로 자료를 저장한다. 내 예측이 맞았다! 순차 컨테이너에서는 자료의 추가가 빠르지만 탐색할 때에는 시간이 많이 걸린다. 왜냐하면 순차적으로 접근하기 때문에!
이러한 순차 컨테이너에는 vector, deque, list 가 있다. 그렇게 벡터, 벡터했던게 바로 여기서 나오는 개념이었구나~
1. Vector : 동적 배열 처럼 동작하며, 자료는 뒤 쪽에서 추가된다. 2. Deque : 벡터와 유사하지만 앞에서도 자료들이 추가될 수 있다. 3. List : 벡터와 유사하지만 중간에서 자료를 추가하는 연산이 효율적이다.
연관 컨테이너
다음은 연관 컨테이너이다. 연관 컨테이너는 조사해 본 결과 사전과 같은 구조로 자료를 저장한다고 한다. 즉, 키와 값의 형태로 데이터가 저장되고, 자료들은 정렬되어 있으며 이러한 정렬 때문에 자료 추가에는 시간이 걸리지만 탐색은 키를 통하여 한 번에 뽑아내니 빠르다.
이러한 연관 컨테이너에는 Set, Map, MultiSet, MultiMap 등이 있다
1. set : 집합이라고 하며, 중복이 없는 자료들이 정렬되어 저장된다. 2. map : 맵이라고 하며, key - value 형태로 저장된다. 3. multiset : 다중 집합이라고 하며, 집합과 유사하지만 자료의 중복을 허용한다. 4. multimap : 다중 맵이라고 하며, 맵과 유사하지만 키가 중복될 수 있다.
컨테이너 어댑터
드디어 컨테이너 어댑터이다!
컨테이너 어댑터는 기존 컨테이너의 인터페이시를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다고 한다. 이게 무슨 말일까 싶어서 좀 더 확인해보았는데
컨테이너 어댑터에는 Stack이 있다. 이를 예로 들자면, 기본 컨테이너인 벡터는 vector 클래스를 사용하는데 이 클래스의 인터페이스를 제한하고(벡터의 여러 기능들을 제한하고) 특정 형태(스택에 관련된 연산)의 동작 만을 수행하도록 한다.
그러니까 한 마디로 내가 어떤 자료구조를 구현할 것 인데 그냥 밑 바닥부터 구현하기 힘들고 귀찮은데 마침 기가 막히고 검증된 기존의 컨테이너가 있으니 이를 활용하여 확장 및 축소 등의 적용(Adapt)을 하는 것이라고 보면 될 것 같다. 그런데 뭔가 계속 제한한다고 하는데 이는 기존의 컨테이너에서 필요없는 부분은 사용하지 못하도록 하는 의미의 제한인 것 같다.
아무튼, 이러한 컨테이너 어댑터에는 Stack, Queue, Priority queue이 제공된다.
Iterator
이제는 반복자(Iterator)의 개념이다.
이 반복자는 각 컨테이너의 자료구조에 맞는 액세스를 할 수 있도록 도와준다. 예를 들어 순회를 한다거나, 원하는 값이 있는 메모리에 접근 가능하도록. 검증되었기 때문에 안심하고 사용해도 된다.
일종의 포인터와 비슷한 객체이다. 기존의 자료구조에서 보면 링크드 리스트에서만 보더라도 노드를 순회하기 위해서는 포인터의 값을 증가 혹은 감소시키고 여러 검사를 하는 등 작업을 했는데 반복자가 이를 대신해준다고 보면 된다.
알고리즘마다 각기 다른 방식으로 컨테이너 요소들에 접근하기 때문에 반복자에도 여러 종류들이 존재한다. 그렇기 때문에 컨테이너를 사용한다면 꼭 반복자를 사용해야 한다.
반복자에는 몇 가지 예를 들자면 input iterator, output iterator, forward iterator, bidirectional iterator, random access iterator 등이 있다.
Algorithm
알고리즘은 문제 해결하기 위해서 그 절차나 방법의 공식화를 의미한다.
탐색, 정렬, 반전, 삭제, 변환 등이 있다.
위와 같이 3가지 요소로 구성된 것이 C++ STL이라는 것을 학습했고, 대충 개념을 잡게 되었다.
