반응형
728x90
반응형
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
#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    // vector 값 10개를 추가한다.
    vector<int> vec;
    for (int i = 0; i < 10; i++)
        vec.push_back(i);
 
    // iterator를 이용한 순회
    vector<int>::iterator it;
    for (it = vec.begin(); it != vec.end(); it++)
        cout << *it << endl;
    cout << endl;
 
    // iterator를 포인터처럼 사용할 수 있다.
    it = vec.begin();
    cout << it[3] << endl; // 3
    cout << *(it+3) << endl; // 3
    cout << *(++it) << endl; // 1
    cout << *it++ << endl; // 1
    cout << *it << endl; // 2
 
    it[0] = 100;
    cout << it[0] << endl; // 100
    
    *(it+1) = 200;
    cout << *(it + 1) << endl; // 200
    cout << it[1] << endl; // 200
 
    cout << "--------------------------------------------------" << endl;
    vector<int>::const_iterator cit = vec.begin();
    for (cit = vec.begin(); cit != vec.end(); cit++)
        cout << *cit << endl;
    cout << "--------------------------------------------------" << endl;
    cout << cit[-1] << endl;
    cout << cit[-2] << endl;
    cout << cit[-3] << endl;
    cout << cit[-4] << endl;
    cout << cit[-5] << endl;
    cout << cit[-6] << endl;
    cout << cit[-7] << endl;
    cout << cit[-8] << endl;
    cout << cit[-9] << endl;
    cout << cit[-10] << endl;
    // cout << cit[-11] << endl; // 에러 ㅋ
    cout << "--------------------------------------------------" << endl;
    // vec.begin() 실제 요소, vec.end() 요소가 아님 -> 가리킬 수 없음
 
    // 값이 반전되어 출력함
    vector<int>::reverse_iterator rit;
    for (rit = vec.rbegin(); rit != vec.rend(); rit++)
        cout << *rit << endl;
 
    cout << "--------------------------------------------------" << endl;
    vector<int>::const_reverse_iterator crit;
    for (crit = vec.crbegin(); crit != vec.crend(); crit++)
        cout << *crit << endl;
 
    return 0;
}
cs
728x90
반응형
저작자표시

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

R-Value, Copy Elision, 이동 생성자, RVO, NRVO  (0) 2021.01.26
자료형 추론 auto / 범위 기반 for  (0) 2021.01.21
Priority Queue  (0) 2021.01.04
Queue  (0) 2021.01.04
Stack  (0) 2021.01.03
728x90
반응형

오늘은 지난 번 Deque 정리에 이어서 List 정리를 해본다.

LIST 란?

리스트는 벡터와 디큐와 마찬가지로 순차 선형 콘테이너이다. 그래서 외부에서 볼 때에는 벡터와 완전히 동일한 듯 보이지만, 구조 자체부터 크게 다르다.

벡터는 순차 배열 형태였다면, 리스트는 이중 연결 리스트로 구현된다. 다음 그림과 같이 말이다.

위와 같은 이중 연결 리스트로 구현되어 있기 때문에 벡터에서의 순회 방법에서 아주 조금의 차이가 있다. 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>
 
using namespace std;
 
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)이다.
    print_list(new_list); // 실행결과 : 비어 있음 -> 이동했기 때문에
    print_list(my_list); // 실행결과 :  33 55 55 200 900 100 300
 
    return 0;
}
 cs

s간단한 설명을 붙이자면,

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() 함수 호출 후에는 텅 비어있다.. 그런데 이것은 뭐 당연하다고 생각된다. 링크를 바꾸는 것이기 때문에!

이상 list^^

 

728x90
반응형
저작자표시

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

Map  (0) 2020.09.15
Set  (0) 2020.09.15
Deque  (0) 2020.09.13
모든 컨테이너 공통 멤버  (0) 2020.09.13
Iterator( With vector )  (0) 2020.09.13
728x90
반응형

반복자(iterator) 에 대한 정리이다. 

반복자는 컨테이너의 요소를 가리키는 객체이다. 포인터와 비슷한 개념이지만 일반화된 포인터라고 보면 될 것 같다. 이 반복자를 통해 컨테이너의 요소에 쉽게 접근할 수 있다.

그러니까 쉽게 말하자면 컨테이너는 여러 종류이지만 각 컨테이너들의 자료 구조나 코드적인 구조를 생각하지 않더라도 컨테이너의 요소들에 쉽게 접근할 수 있도록 만들어진 인터페이스와 같다.

나는 이 반복자가 따로 클래스 정의되어 있는 것인줄 알았다. 그런 것이 아니고 보니까 각각 컨테이너마다 반복자가 들어있던 것이다.

사용법은 정말 간단한 코드로 정리를 해놓는다.

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
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
    int max_number = 0;
    int val = 0;
    vector<int> num_vector;
    vector<int>::iterator it; // 반복자를 선언한다.
 
    while (true)
    {
        cout << "벡터에 추가할 숫자를 입력하세요 (-123123 입력 시 종료) : ";
        cin >> val;
        if (val == -123123)
            break;
        else
            num_vector.push_back(val);
    }
    max_number = num_vector[0];
    for (it=num_vector.begin() ; it<num_vector.end(); it++) 
    {
        if (*it > max_number)
            max_number = *it;
    }
 
    cout << " 입력한 값 중에서 최대 값은 " << max_number << " 입니다." << endl;
    return 0;
}
 cs

이전 코드와 다른 점은 컨테이너의 요소 순회를 정수 인덱스(i)가 아닌 반복자를 통해서 순회한다는 점인데, 9번 라인에서 벡터 콘테이너 클래스 템플릿 내에 존재하는 iterator를 선언하고, 21번 라인에서 선언한 반복자를 이용해서 시작과 끝을 설정하는 부분이다. 

위의 21번 라인에 있는 begin과 end 멤버는 어떤 반환을 하길래 저렇게 사용할까? 라는 생각에 벡터 컨테이너 클래스 내에서 begin과 end 멤버 함수의 정의를 확인해 보았는데, 친절하게도 아래와 같이 주석이 달려있다. 

반환형이 시퀀스의 시작을 위한 iterator 형태와 끝 iterator 형태를 반환하기 때문에 코드에서 선언한 반복자로 이를 반환 받은 후 범위에 대한 접근 처리를 진행할 수 있었던 것이다.

23, 24 라인과 같이 접근할 때에는 포인터를 사용하는 듯이 오버로딩된 연산자 * 을 통해서 진행된다.

728x90
반응형
저작자표시

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

Deque  (0) 2020.09.13
모든 컨테이너 공통 멤버  (0) 2020.09.13
Vector  (0) 2020.09.12
STL:Container, Iterator, Algorithm 개념  (0) 2020.09.10
C++ STL(Standard Template Library이란?  (0) 2020.09.07
728x90
반응형

오늘은 컨테이너, 이터레이터, 알고리즘이란 무엇이며, 무엇이 있는지 학습한 결과를 기록한다.

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이라는 것을 학습했고, 대충 개념을 잡게 되었다.

728x90
반응형
저작자표시

'프로그래밍응용 > Modern & STL' 카테고리의 다른 글

Deque  (0) 2020.09.13
모든 컨테이너 공통 멤버  (0) 2020.09.13
Iterator( With vector )  (0) 2020.09.13
Vector  (0) 2020.09.12
C++ STL(Standard Template Library이란?  (0) 2020.09.07

+ Recent posts

티스토리툴바