[C++] vector, map / sort, find / reverse iterator and base iterator

컨테이너

= 자료 구조 Data Structures

- 템플릿 구현으로 타입 관계 없이 사용 가능

- 내부적으로 메모리 관리하므로 사용 시의 메모리 관리를 고려하지 않아도 됨

- 반복자 iterator 로 traverse 가능

 

벡터

- 삽입되는 원소 갯수에 따라 내부 배열 크기 자동 관리 / 생성자에서 초기 크기를 지정해도 원소 추가 삽입/삭제에 따라 내부적으로 메모리 관리

- 삽입/삭제 맨 뒤에 하는 경우에 주로 사용

- #include <vector>

 

+ 벡터의 복사 방식을 알아보기 위해 아래와 같이 비교해보았다.

    vector<int> vec1 = { 1,2,3,4,5 };
    vector<int> vec2(vec1);
    vector<int> vec3 = vec1;

    cout << &vec1 << endl;
    cout << &vec2 << endl;
    cout << &vec3 << endl;

    vec1 = { 1, 2, 3 };
    cout << *(--vec1.end()) << endl;
    cout << *(--vec2.end()) << endl;
    cout << *(--vec3.end()) << endl;

vec2, vec3 은 vec1과 별개의 주소에 할당되어 vec1의 값을 바꾸어도 vec2, vec3 은 바뀌지 않음을 알 수 있다.

 

- push_back(element); : 벡터 끝에 element 추가 / pop_back() : 마지막 원소 제거 / size() : 크기

-  for ([type] [var] : [vector]) 형식으로 벡터 traverse 가능

- erase([index]) : index 위치의 원소 삭제 / erase([start], [end]) : start ~ end-1 원소 삭제

 

맵

- 키 & 밸류가 하나의 타입

- 키의 값 기준으로 데이터 자동 정렬

- 중복된 키의 값을 갖는 것은 불가능

 

- 선언 : map<Type, Type> MapName;

- 초기화 : map<Type, Type> MapName = { {Key, Value}, {Key, Value}, ... }

 

- pair 를 key로, vector를 value로 사용 가능

- MapName[Key] = Value; 로 Key-Value 삽입 가능

 

- 복사 생성자: map<Type, Type> CopiedMap(OriginalMap);

- 대입 연산자로 복사: CopiedMap = OriginalMap;

- insert(범위)로 복사: CopiedMap.insert(OriginalMap.begin(), OriginalMap.end());

 

- iterator->first = 키 / iterator->second = 값

- 삽입: MapName.insert(make_pair(key, value));

  *같은 키를 가진 원소가 이미 있는 경우 값이 변경됨

- 검색: find(key) / iterator 를 반환함 / 못 찾았으면 end() 위치

- 모든 원소 삭제: clear()

 

<algorithm> sort

sort(StartIndex, EndIndex, CompareBool)\

- 범위는 [StartIndex, EndIndex)

- 정렬 기준 함수가 true 를 반환하면 순서를 유지한다.

- 정렬 기준 함수가 없으면 오름차순

- 정렬 기준 함수가 두 개의 인자를 받을 때 앞의 인자가 앞의 원소, 뒤의 인자가 뒤의 원소

e.g. bool compare(int a, int b) { return a > b }; --> 내림차순

 

<algorithm> find

- find(start, end, value)

- 발견한 위치 : findIndex - startIndex / distance(startIndex, findIndex)

 

rbegin, rend

- rbegin = end - 1

- rend = begin - 1

 

reverse iterator 의 base() 사용 시 주의!!

reverse iterator의 base iterator는 하나 뒤를 가리킨다!!!

https://cplusplus.com/reference/iterator/reverse_iterator/base/

 

c++ stl what does base() do

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

int main() {
    vector <int> v;
    for (int i = 0; i < 5; i++) v.push_back(i);

    auto rit = find(v.rbegin(), v.rend(), 2);
    if (rit != v.rend()) {
        cout << "Found " << *rit << " from rit." << endl;
        cout << "rit.base(); and dereference: " << *(rit.base()) << endl;
    }

    return 0;
}

위처럼 간단한 테스트를 해보면, rit 를 dereference 했을 때 2를, rit.base()를 dereference 했을 때 3을 리턴하는 것을 볼 수 있다.

reverse iterator의 base iterator는 베이스 기준으로 하나 뒤의 원소를 가리키고 있다.

결국 rend().base() 는 begin()을, rbegin().base() 는 end() 를 가리키고 있다는 말이 된다.

항목 28 : reverse_iterator에 대응되는 기점 반복자(base iterator)를 사용하는 방법을 정확하게 이해하자

 

 

그 외 추가 내용

- int size = sizeof(array) / sizeof(array[0])  --> 배열 전체크기를 원소 하나의 크기로 나누면 배열의 길이를 알 수 있음

* dynamic array 는 포인터이므로 sizeof(array)에서 오류

- auto type : type 를 추론해서 자동으로 결정 e.g. auto it = find(vec.begin(), vec.end(), value); --> it 자동으로 vector<type>::iterator 가 됨