C++ STL

// 표준 템플릿 라이브러리(STL, Standard Template Library)

- 일반화 프로그래밍(Generic Programming)을 기반으로 하는 한다.

- 자료구조와 알고리즘을 중시

​

※ 일반화 프로그래밍 : 데이터를 중시하는 객체 지향 프로그래밍과 다르게,

프로그램의 알고리즘에 중점을 두는 방식

​

※ 템플릿 : 매개변수의 타입에 따라 함수나 클래스를 생성하는 매커니즘

타입이 전달받는 매개변수의 형태에 따라 자동 변형되어 처리된다.

​

​

<STL의 3요소>

1. 반복자 (iterator) : 컨테이너에 저장된 요소를 반복적으로 순회하여

각 요소에 대한 접근을 도와준다.

2. 컨테이너 (container) : 같은 타입의 여러 객체를 저장하는 집합.

3. 알고리즘 (algorithm)

​

​

==============================================

//==============================================

​

// 동적 배열 클래스 std::vector

/*

1. 개요

- 일반 배열과 동일하게 []연산자로 값을 참조 & 대입 가능

- 배열의 크기(사이즈)와 데이터의 삽입(push back / insert) & 삭제(erase / pop back)도 비교적 쉽게 실행할 수 있다.

- C++에서는 vector 이외에도 복수의 데이터를 취급하는 클래스(std::list)가 몇개 존재하나, vector가 가장 빠르고 메모리 효율도 좋다.

​

2. 동적 배열 (dynamic array)

- 기존의 배열은 일반 변수보다 사용빈도도 높고 편리한 데이터 타입이지만, 배열의 크기를 미리 지정해야만 한다. 또한, 프로그램 실행 중에

변경 할 수도 없음.

- 반면 동적 배열은 그러한 상황에서 비교적 자유자재로 변화시킬 수 있어 기존의 배열보다 효율이 뛰어나다.

*/

​

// std::vector의 선언

/*

- vector의 선언은 여러 가지가 있다.

(빈 벡터 선언, 사이즈 지정 선언, 사이즈/데이터 지정 선언, 특정 데이터 기반 선언 등등)

​

- 특정 위치에서 선언하고 다른 곳으로 이동했을 때, 만약 그곳이 스코프

(scope, 유효범위)를 벗어난 곳이라면 해당 vector는 자동 소멸.

​

1) 초간단 선언하기

- vector 객체를 만들기 위해서는 다음과 같은 문법을 쓴다.

​

[예시]

std::vector<타입> 객체명;

- 데이터 타입은 일반적인 타입부터 구조체, 클래스도 가능하다.

- 이렇게 선언한 vector의 요소 수는 0;

​

​

2) 요소 수를 지정하여 선언하기

- 동적 배열은 프로그램 실행 중에 사이즈를 변화시킬 수 있다.

- 하지만 데이터 영역의 확보와 파기, 그리고 복사 처리를 해야하므로

약간의 처리 시간을 필요로 한다.

- 때문에 요소 수를 알고 있으면 되도록 그 수를 지정하여 객체로 만드는 것이 유리하다.

​

[예시]

std::vector<int> data(123);

-> int형 벡터 data의 요소 수는 123이다.

​

- 배열에서는 요소 개수를 표현할 때 [숫자]로 표현하지만,

벡터에서는 (숫자)로 표현한다.

*/

​

// std::vector의 초기화

/*

- 요소 수를 지정하는 것 뿐만 아니라 요소 전체의 값을 지정해 초기화하는 것도 가능.

​

=================================================

​

[예시]

std::vector<int> data(10, 5);

->요소 개소가 10개이고 그 요소의 값이 모두 5로 초기화된다.

​

- 지정한 숫자만큼 사이즈를 확보하고, 지정된 값으로 전부 초기화를 실행한다.

- 하지만 이 방법으로 값이 완전히 동일한 경우가 아니면 초기화가 불가능,

​

=================================================

​

[예시]

std::vector<type> name(itr* first, itr* last);

-> 일반 배열 데이터 가져가 쓸때 사용

​

- 위 예시는 first와 last가 가리키는 데이터를 기반으로 초기화한다.

- 이 형태를 이용하여 일반 배열 데이터를 기반으로 동적 배열 구축이 가능하다.

​

=================================================

​

[예시]

int _data[]{4,5,6};

vector<int> data(_data, _data + 3);

​

- 만약 기반 데이터 배열 사이즈가 변경 되면 필히 바꿔야하므로 위험하다.

- 이것을 사전 차단하기 위해 C++11부터 std::begin(배열명), std::end(배열명) 함수를 이용하여 배열을 포인터로 반환한다.

​

=================================================

​

[예시]

int _data[]{4,5,6};

vector<int> data(std::begin(_data), std::end(_data));

​

- 이외에도 C++11부터 vector를 초기화 할 때, 초기값을 직접 지정할 수 있다.

​

[예시]

std::vector<int> data{4, 5, 6};

​

=================================================

​

*/

​

// iterator

/*

​

- vector, list, map 등의 컨테이너 클래스에는 iterator 라는 것이 들어 있다.

- iterator는 추상화된 포인터를 가리킨다. (추상화 : 어떤 대상의 특징을 요점만 추려내는 것)

- * 연산자로 iterator가 가리키는 특정 요소를 참조, 변경 할 수 있다.

​

- std::vector<T>의 iterator는 vector<T>::iterator 이다.

​

[예시]

std::vector<int>::iterator itr;

-> vector<int>의 요소에 접근하기 위한 iterator

​

- begin() 멤버 함수는 첫 번째 요소를 반환한다.

- end() 멤버 함수는 마지막 요소를 하나 더 지나친 위치의 iterator를 반환한다.

유효한 객체를 가리키지 않으므로 역참조나 증감이 불가능하다.

- 이를 사용하여 iterator를 초기화하고 매개체로써 활용가능.

​

=================================================

​

[예시]

vector<int> v{ 1,2,3,4 };

vector<int>::iterator itr = v.begin(); // 첫번째 요소를 반환하는 begin

cout << *itr << endl; // 첫번째 요소를 참조하여 출력

++itr; // 다음 요소로 이동

*itr = 9; // 두 번째 요소의 값을 2에서 9로 변경

​

​

- iterator는 auto 키워드도 인식한다.

- 일일이 타이핑하는 건 어려우니 auto 활용

​

[예시]

vector<int> v{ 1,2,3,4 };

auto itr = v.begin(); // 첫번째 요소를 반환하는 begin

cout << *itr << endl; // 첫번째 요소를 참조하여 출력

​

​

=================================================

​

- iterator를 사용하여 vector v의 요소를 모두 검사할 때는 아래와 같은 방법을 사용한다.

​

[예시]

for(auto itr = v.begin(); itr !=v.end(); ++itr)

{

cout << *iter << endl;

}

=================================================

*/

​

// std::vector의 데이터 삽입

/*

1. push_back()

- 데이터를 vector의 요소 맨 끝에 배치하는 멤버 함수.

- 보통 데이터의 추가는 이 멤버 함수만을 사용한다.

​

[예시]

std::vector<int> v;

v.push_back(123);

​

- 처리 시간이 O(1) ( = 데이터 수에 관계없이 항상 일정속도로 처리)

​

O(1)

O(log N)

O(N)

​

2. insert(iterator, value)

- 임의의 위치에 데이터를 삽입하고 싶은 경우 사용하는 멤버 함수.

- 제 1인수에는 삽입하고 싶은 vector의 위치를, 제 2인수에는 삽입할 데이터를 지정

- n번째에 삽입하고 싶을 경우엔 객체명.begin() + n 라고 기억하면 됨

- push_back()에 비해 처리시간(O(N))이 상당량 소모되므로 권장하진 않음.

​

[예시]

​

std::vector<int> v(10, 3); // 값이 3이고, 개수는 10개

v.insert(v.begin() + 4, 7); // [4] 위치에 7을 대입

​

- 배열 중간에 빈번한 값의 삽입/삭제를 실행할 경우에는 std::list나 std::gap_vector의 사용을 검토하는 편이 좋다.

- 데이터의 가장 앞부분에 빈번한 삽입/삭제를 하는 경우 std::deque가 좋다

- 하지만 데이터 수가 10개 내외일 정도로 작을 경우엔 vector가 좋다

*/

​

// std::vector의 데이터 삭제

/*

1. pop_back()

- vector의 맨 끝에 위치한 데이터를 삭제하는 멤버 함수

- 처리속도가 push_back()과 동일한 O(1) 이다.

​

예시) std::vector<int> v{3, 1, 4, 1, 5};

v.pop_back(); // 맨 마지막의 데이터를 삭제한다.

​

- 빈 vector에서 pop_back()을 실행하면 디버그에서 예외가 발생한다.

이를 방지하기 위해 empty() 혹은 size()로 vector의 내부 크기를 확인해야 한다.

​

2. erase(iterator)

- 임의의 위치에 있는 데이터를 삭제하고 싶은 경우 사용하는 멤버 함수.

- 중간의 요소를 삭제하면 사이즈가 1 감소하여 삭제된 요소 다음에 위치해있던 요소들이 자리 이동을 실시한다.

- 그러나 요소 수가 많을 경우 데이터 이동에 시간을 필요로 하니 주의

​

예시) std::vector<int> v{3, 1, 9, 4};

v.erase(v.begin() + 2); // 3번째의 요소 (9)를 삭제

3. erase(first, last)

- vector의 일부를 삭제하고 싶은 경우 하나하나 지우지 않아도 범위 삭제가 가능

​

예시) std::vector<int> v{3, 1, 4, 1, 5};

v.erase(v.begin() + 1, v.begin() + 3); // 1, 4를 삭제

*/

​

// std::vector의 대입

/*

1. 대입 연산자

- 동일 타입의 vector라면 = 연산자를 사용하여 일반 변수와 동일하게 값을 대입할 수 있다.

​

예시) vector<int> a{1, 2, 3, 4};

vector<int> b{9, 8};

b= a; // a의 요소를 b에 대입

-> 둘이 합쳐지는게 아닌 완전히 값이 바뀐다.

​

2. assign 함수

- assign(first, last)는 특정 범위의 데이터를 vector에 대입한다.

​

예시) int ar[] {1, 2, 3, 4, 5, 6, 7};

vector<int> v{9, 8};

v.assign(&ar[0], &ar[3]); // v의 내부 값은 {1, 2, 3}으로 변화

​

- assign(size, 값)을 하면 요소를 범위 지정하여 대입할 수 있다.

- resize(size, 값)도 의미상 비슷하긴 하나 resize()는 처음부터 존재하던 요소를 삭제하는 것이 아니기 때문에

특정 값으로 완전 초기화를 하고 싶으면 이걸 써야한다.

vector<int> v{9, 8}

v.assign(3, 1); // 사이즈가 3이고 그 값이 전부 1임 / v의 내부 값은 {1, 1, 1}로 변화

​

*/

​

// std::vector의 참조

/*

1. [] 연산자

- 일반적인 배열과 동일하게 인덱스를 사용하여 배열 요소 값을 참조, 대입할 수 있다.

- [] 연산자를 사용한 랜덤 엑세스 소요시간은 O(1)이다.

이는 일반 배열과 마찬가지일 정도로 매우 빠른속도를 의미

​

[예시1]

std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

for(int i = 0; i<10; i++)

std::cout << data[i]; // data의 i번쨰 요소를 표시

​

[예시2]

const int SZ= 10; // 요소개수

std::vector<int>v(SZ); // 지정된 요소 수를 가지는 vector 생성

for(int i=0; i< SZ; ++i)

v[i] = i; // 요소를 0, 1, 2, 3,....9의 값으로 설정

​

2. at함수

- i번째 데이터에 엑세스하게 만들어주는 멤버 함수

- at() 함수는 값이 아닌 참조를 반환하므로 [] 연산자처럼 값을 참조하는 것과 대입하는 것이 모두 가능하다.

​

[예시1]

std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};

for(int i = 0; i<10; i++)

std::cout << data.at(i); // data의 i번쨰 요소를 표시

​

[예시2]

const int SZ= 10; // 요소개수

std::vector<int>v(SZ); // 지정된 요소 수를 가지는 vector 생성

for(int i=0; i< SZ; ++i)

v.at(i) = i; // 요소를 0, 1, 2, 3,....9의 값으로 설정

*/

​

// 기타 멤버 함수

/*

1. vector의 상태를 받아오는 멤버 함수

1) empty()

- vector가 비어있는 상태인지 아닌지 검사하는 함수

- 비어있으면 true, 아니면 false를 반환

if(v.empty())

{

v가 비어있을 경우 처리를 실행하도록

}

​

2) size()

- vector의 요소 개수를 반환하는 함수

for(int i= 0; i != v.size(); i++)

{

벡터 전체를 순회하라

}

​

2. vector의 요소를 받아오는 멤버 함수

1) front() : 맨 앞의 요소를 참조반환. 객체명[0]와 동일.

2) back() : 맨 뒤의 요소를 참조반환. 객체명[객체명.size() -1]과 동일

​

// 아래와 같이 대입도 가능

std::vector<int> a{1, 2, 3, 4};

v.front() = 10;

-> 나중에 확인해보자

​

3. vector의 메모리 멤버 함수

1) clear()

- vector를 텅 비게 만들어 버리는 함수.

- size가 0으로 바뀔 뿐, 할당된 메모리가 해제 되지는 않는다.

- 메모리를 해제하고 싶은 경우 shrink_to_fit(), swap()을 실행

​

2) resize(리사이즈)

- 요소 수를 지정한 값만큼으로 설정하는 함수

- 만약 사이즈가 capacity를 초과하는 경우 메모리가 새로 할당되어 데이터를 복사한다.

- 사이즈가 늘어난 부분의 값을 별도로 지정하고 싶다면 resize(사이즈, 값)처럼 두번째

인수를 지정해줘야한다.

- clear()와 마찬가지로 사이즈를 바꿀 수 있을 뿐, 메모리를 해제할 수는 없다.

- 메모리를 해제하고 싶은 경우 shrink_to_fit(), swap()을 실행

​

3) swap(객체)

- 인수로 삽입한 객체와 내부 요소를 서로 바꾸는 함수.

std::vector<int> x, y;

x.swap(y);

-> x와 y의 값이 뒤바뀐다. 말그대로 스왑해버림

​

4) shrink_to_fit()

- C++11 이전에 clear()를 사용하여 해제가 되지 않는 메모리를 해제할 때?

std::vector<int> v;

std::vector<int>().swap(v); // 텅빈 임시 객체 생성 후 swap 사용

​

- 하지만 C++11부터 shrink_to_fit() 함수가 추가되었다.

- capacity를 현재 vector의 사이즈로 변경하고, 남은 잉여 메모리를 해제.

*/

​

// 알고리즘 함수

/*

1. count()

- count(객체명.begin(), 객체명.end(), value)

- 컨테이너의 처음부터 끝까지 검사한 후, value의 개수를 정수 형으로 반환한다.

​

[예시]

vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

cout << "요소 7의 개수 : " << count(v.begin(), v.end(), 7) << endl;

​

// 객체도 셀수있다. ex) 클래스

​

2. find()

- find(객체명.begin(), 객체명.end(), value)

- 컨테이너의 처음부터 끝까지 검사한 후, value가 중복이 될 때

가장 처음에 위치한 값을 반환한다.

- 지정 valuㄷ를 찾지 못할 경우에는 객체.end()를 반환한다. // 사실상 null

​

[예시1]

vector<int> v{ 1,2,3,1,2,3,1,2,3 };

auto itr = std::find(v.begin(), v.end(), 2);

cout << *itr << endl;

​

[예시2]

vector<int> y{ 1,2,3,4,5,6,7,8,9,10 };

auto itr = std::find(y.begin(), y.end(), 15);

​

if (itr == y.end())

{

cout << "초과 범위 입력" << endl;

}

else

{

cout << *itr << endl;

}

​

3. accumulate()

- accumulate(객체명.begin(), 객체명.end(), init)

- 컨테이너의 처음부터 끝까지 검사한 후, 내부에 존재하는 요소를 전부 합산하다.

- 합산된 값은 세번째 인수인 initial value를 따라간다 (보통 0을 기입)

- 사용하기 위해서 #include <numeric> 선언이 필요하다

​

[예시]

#include <numeric>

...

vector<int> v {1,2,3,4,5,6,7,8,9,10}

cout << accumulate(v.begin(), v.end(), 0) << endl;

​

4. sort()

- sort(객체명.begin(), 객체명.end())

- 컨테이너의 내부 요소를 오름차순으로 정렬한다.

- 단, 사용하려면 #include <algorithm> 선언을 해야한다

​

[예시]

vector<int> v{ 4,5,1,9,8,2,3,6,7 };

​

sort(v.begin(), v.end()); // 전체 데이터 정렬

sort(v.begin() + 1, v.end() - 1); // 일부 데이터 정렬

sort(&v[1], &v[5]); // 포인터(주소)로 정렬 위치 지정

​

5. reverse()

- reverse(객체명.begin(), 객체명.end())

- 데이터 정렬 순서를 역순으로 만들어 주는 함수

​

[예시]

vector<int> v{ 4,5,1,9,8,2,3,6,7 };

reverse(v.begin(), v.end());

​

for(auto a:v)

cout << a << endl;

*/

​

//==============================================

//==============================================

​

// 양방향 연결 리스트 클래스 std::list

/*

1. 양방향 연결 리스트 (doubly linked list)

- 요소를 보관하는 각각의 노드에 앞뒤로 위치한 노드의 포인터가 존재

- 이 때문에 어느 위치에 삽입/삭제를 실행해도 O(1)의 속도로 처리할 수 있음

​

2. vector와의 차이점

1) std::vector

- 맨 마지막 위치에서 실시하는 데이터 삽입/삭제 속도는 O(1)

- 그 외의 위치에서 실시하는 데이터 삽입/삭제 속도는 O(N) -> 배열형식이기 때문

- 어떤 위치에서든 O(1)의 속도로 랜덤(고속) 액세스(참조와 대입)가 가능하다.

- 배열과 비슷하게 연속된 메모리 할당 구조

​

2) std::list

- 데이터 위치에 상관없이 모든 삽입/삭제가 O(1)로 동작

- n번째에 위치한 데이터로 이동할 때, 선두와 후미 또는 현재 위치에서 포인터를 받아야

하므로 랜덤 액세스 속도가 O(N)이다.

- 각각의 노드가 독립적인 메모리를 갖고 있고, 이것이 포인터로 상호 링크 되어 있음

​

*/

​

// std::list의 선언

/*

1) 초간단 선언하기

- #include <list> 선언이 선행 조건

- list 객체를 만들기 위해서는 아래와 같은 문법 사용

​

[문법]

std::list<타입> 객체명;

​

2) 요소 수를 지정하여 선언하기

- vector는 데이터 영역이 연속되어 있어, 공간이 부족한 경우 메모리의

추가 할당과 데이터 복사가 필연적이다

- 반면 list는 데이터 영역이 모두 독립적이기 때문에 굳이 사이즈를 지정하여

객체를 만들어도 vector에 비해 이렇다할 메리트가 없다.

​

[예시]

std::list<int> data(123);

-> int형에 초기 요소 수가 123인 리스트 data를 선언

​

​

*/

​

// std::list의 초기화는 vector의 초기화와 같다

​

// std::list의 iterator

/*

1. 개요

- list에는 [] 연산자가 없다. 따라서 n번째 요소 참조하는 것이 불가능

- 때문에 임의의 위치에 저장된 데이터를 탐색하기 위해 iterator를 사용한다.

2. 상세

- begin() : 제일 처음에 위치한 데이터의 iterator를 반환한다.

- end() : 제일 마지막에 위치한 데이터의 다음 위치에 해당하는 iterator를 반환한다.

유효 객체를 가리키지 않아 역참조같은 것이 불가능하다.

- 증감 연산자(++/--)로 iterator를 다음으로 넘기거나 되돌아갈 수 있다.

- * 연산자로 iterator가 가리키는 요소를 참조 할 수 있다.

​

*/

​

// std::list의 데이터 삽입

/*

1. front_back()

- 데이터를 list 내부의 맨 앞에 배치하는 멤버 함수

- 처리 시간이 O(1)으로 요소 수에 관계없이 항상 일정시간으로 처리

​

[예시]

std::list<int> v;

v.push_front(456);

​

2. push_back()

- 데이터를 list의 요소 맨 끝에 배치하는 멤버 함수.

- 처리 시간이 O(1)으로 요소 수에 관계없이 항상 일정시간으로 처리

​

[예시]

std::list<int> v;

v.push_back(123);

​

3. insert(iterator, value)

- 임의의 위치에 데이터를 삽입하고 싶은 경우 사용하는 멤버 함수.

- 제1인수에는 삽입하고 싶은 list의 위치를, 제2인수에는 삽입할 데이터를 지정

​

​

[예시]

list<int> v{ 1, 2, 3, 4, 5, 6, 7 };

for (auto itr = v.begin(); itr != v.end(); itr++)

{

if (*itr == 3)

{

v.insert(itr, 10); // 3앞에 10을 삽입, itr는 10을 가리킨다.

++itr; // itr을 3의 위치로 이동

}

}

​

for (auto a : v)

{

cout << a << endl;

}

*/

​

// std::list의 데이터 삭제

/*

1. pop_front()

- list 내부의 맨 앞에 위치한 데이터를 삭제하는 멤버 함수.

- 처리시간이 O(1)으로 요소 수에 관계없이 항상 일정시간 처리

​

[예시]

std::list<int> v{ 1, 2, 3, 4, 5 };

v.pop_front();

​

2. pop_back()

- list 내부의 맨 뒤에 위치한 데이터를 삭제하는 멤버 함수.

- 처리시간이 O(1)으로 요소 수에 관계없이 항상 일정시간 처리

​

[예시]

std::list<int> v{ 1, 2, 3, 4, 5 };

v.pop_back();

​

3. erase

- 임의의 위치에 있는 데이터를 삭제하고 싶은 경우 사용하는 멤버 함수

​

[예시]

std::list<int> v{ 1, 2, 3, 4, 5 };

auto itr = lst.begin();

++itr;

++itr; // 세번째 위치로 이동

lst.erase(itr); // 세번째 위치의 데이터인 3을 삭제

​

​

- vector 처럼 삭제된 위치에서 자리이동이 일어나지 않으면, 포인터가 바뀌는 것이 전부

- itr가 가리키고있던 메모리 주소는 힙 영역으로 반환되는 동시에 itr가 가리키고 있던 곳은

무표 판정으로 변하므로 그대로 사용하면 안된다.

- 이후에도 itr를 계속 사용한다면 반드시 erase(itr)이 반환되는 값을 itr에 대입하고 itr이

노드를 올바르게 가리킬 수 있도록 해야만 한다.

​

[예시]

리스트에 포함된 데이터 중에서 1을 모두 지우고 싶은 경우

list<int> lst {1, 2, 3, 4, 5, 1, 6, 7, 8, 9, 1, 10 };

for(auto itr = lst.begin(); itr != lst.end(); itr+=)

{

if(*itr ==1) // 데이터가 1일 떄

itr = lst.erase(itr); // 무조건 삭제하고 다음으로 진행한다

else

++itr; // itr를 다음으로 넘긴다.

}

*/

​

//==============================================

//==============================================

// 연관 배열 클래스 std::map

/*

1. 연관 배열 (Associative Array) 클래스

- 검색이 가능한 키(Key)와 그 키에 대응하는 밸류(value)가 페어(pair)로

구성된 컨테이너 클래스.

- 보유한 데이터에 키를 지정하여 값을 고속으로 탐색, 출력할 수 있다.

​

2. 특징

- 단순한 배열을 사용하여 값을 취득할 경우 처리시간 O(N)인데

map은 O(log N)이다. / N보다는 한 단계 고속 / 이는 map이

이진 트리(binary tree)로써 구성되어 있기 때문이다.

​

* O(log N) : 입력 값 N이 주어지고 연산을 실행할 때 필요한 단계가 특정

요인에 의해 줄어듬

​

* O(N)이면 요소 수가 1천배일 때 처리시간도 1천배가 된다. 반면에 이

진트리의 O(log N)이면 요소 수가 1천배로 증가해도 처리시간의 증가는

약 10배에 지나지 않음.

​

- map과 비슷한 클래스가 C++11 에서 unordered_map 이라는 이름으로 존재.

이는 해쉬를 사용하기 때문에 키에서 데이터를 추출하는 속도가 O(1)이라 매우 빠름

​

- 하지만 이름에서 알 수 있듯이 요소가 순서대로 정렬되어 있지 않아 정렬하고 싶은

경우에는 map을 사용하게 된다.

​

- 또한, 하나의 키에 여러개의 값을 대응시킬 수 있는 multimap도 있다.

*/

​

// std::map의 선언

/*

1. 개요

- vector와 list 둘과 map의 가장 큰 차이점은 삽입하는 요소의 형태가 2종류라는 것이다.

- 첫번째 인수는 키 (key)라고 불리며, string이나 int 같은 타입들을 지정할 수 있다.

단, 아무 타입이나 지정할 수 있는 것은 아니며, 노드를 키 순서대로 정렬하기 위해

키 객체의 순서가 계산 가능한 것이 아니면 안된다.

​

[문법]

#include <map>

...

std::map<key, value> 객체명;

std::map<string, int> map_; //string &int의 연관 배열 map_ 생성

*/

​

// std::map의 값 설정과 참조

/*

1. key에 대응하는 value를 설정

- 연관 배열에서 key에 대응하는 값을 설정하려면 객체명[key] = value로

해야한다.

​

[예시]

std::map<std::string, int> mp;

mp["abc"] = 123;

​

- key-value설정이 완료되면 map 내부의 트리에 저장된다.

- 한 번 설정한 key에는 값을 여러 번 바꿀 수 있다. 덮어쓰기가 가능함

​

[예시]

mp["abc"] = 123;

mp["abc"] = 456;

mp["abc"] = 789;

​

2. key에 대응하는 value를 취득하는 방법

- 객체명[key]를 입력하는 것만으로 map에서 value를 불러올 수 있다.

- 그러나, 만약에 value가 설정되어 있지 않은 key를 불러오면 value의 데이터

타입에 기반한 디폴트 값을 불러온다.

​

[예시]

std::map<std::string, int> mp;

mp["Lotus"] = 123;

​

cout << mp["Lotus"] << endl; // mp["Lotus"] 의 값 123을 불러옴

cout << mp["IBM"] << endl; // mp["IBM"]은 없으므로 0을 표시

​

- 사실 [] 연산자가 반환하는 타입은 (const가 아닌) 값의 참조다. 따라서 연관 배열

이 보유하고 있지 않은 키를 사용하면 그 키와 디폴트 값으로 구성된 노드가 작성되

므로 주의할 것.

​

[예시]

std::map<std::string, int> mp;

mp["Lotus"] = 123;

​

const std::map<std::string ,int> mp2(mp); // 상수 mp2 을 생성

cout << mp2["Lotus"] << "\n"; // 탐색할 수 없음

​

​

- 위 예시 뿐만 아니라 인수로써 const map이 들어가는 경우도 있다. 이때도 []연산자는 사용불가능.

- 연관 컨테이너 const일 경우에 값을 참조하고 싶으면 at() 멤버 함수를 사용한다. 이 함수는 const도

정의되어 있으므로 안전하다.

​

[예시]

std::map<std::string, int> mp;

mp["Lotus"] = 123;

const std::map<std::string, int> mp2(mp); // mp를 기반으로 mp2 생성

cout << mp2.at("Lotus") << "\n"; // 123이 표시됨

*/

​

// 모든 key, value의 데이터 취득(iterator)

/*

- map 에서는 객체명.begin()과 객체명.end()로 데이터를 취득할 수 있다.

- 이때 이 데이터는 페어(std::pair)로 구성되어 있어 키와 값을 가각 itr->first, itr->second

로 받는다.

​

[예시]

std::map<std::string, int> mp;

for(auto itr = mp.begin(); itr !=mp.end(); ++itr)

{

std::cout << "key = " << itr->first << ", val = " << itr->second << "\n";

}

*/

​

// std::map에서 key를 검색

/*

1.find() : iterator

- 객체명.find(key)를 사용하여 key에 map이 존재하는지 검사한다.

- key가 설정되어 있을 경우, key와 value pair의 iterator를 반환.

- key가 설정되어 있지 않을 경우, end()를 반환.

​

[예시]

map<string, int> mp;

auto itr = mp.find("xyz");

if(itr != mp.end())

{

// 값이 있을 때의 처리

}

else

{

// 값이 없을 때의 처리

}

​

2. lower_bound(key) & upper_bound(key)

- 이진 탐색 기반의 검색용 함수

​

1) lower_bound(key)

- 자신을 포함하여 인수로 지정된 key보다 큰 최초의 key에

대한 iterator를 반환한다.

​

2) upper_bound(key)

- 인수로 지정된 key보다 큰 최초의 key에 대한 iterator를 반환한다.

​

*/

//==============================================

//==============================================