STL deque / map

C++ STL Deque Container

Deque 컨테이너는 시퀀스 컨테이너이자, 배열 기반 컨테이너이다. 따라서 Vector 컨테이너와 특징이 매우 유사하다.

하나의 메모리 블록에 저장되는 Vector와 달리 Deque는 여러 개의 메모리 블록에 나눠서 저장된다는 특징이 있다.

 

Deque는 위와같은 메모리 구조를 가지고 있어서, Vector와는 달리 push_front(), pop_front()를 이용하여 제일 앞의 원소도

추가 / 제거할 수 있다. 또한 중간 원소를 추가 / 제거하는 경우(insert, erase), Vector에 비해 약간 더 효율적이다.

이는 Vector에서는 앞 원소를 추가 / 제거하는 것이 불가능한 스택구조이기 때문에, 모든 원소를 뒤에서 밀어야만 하는데,

Deque는 앞, 뒤 어디든 원소의 추가 / 제거가 가능하다.

---

Deque 사용법

기본적으로 Vector와 사용법이 비슷하기에 쉽게 사용할 수 있다.

먼저 deque를 사용하기 위해서는, deque 헤더파일부터 include 해줘야 한다.

#include<deque>

 

이어서 Deque의 선언 및 초기화 방식이다. 이 또한 Vector와 사용법이 비슷하다.

"deque<자료형> 변수이름;" 의 형태로 선언할 수 있다.

deque<int> dq1; //int 자료형의 deque 생성
dq1.push_back(10); //10 추가
dq1.pop_back(); //맨 뒤의 원소 10 삭제

 

push_front / pop_front

원소의 제일 앞으로 접근하여 추가 / 삭제를 할 수 있다.

---

C++ STL Map

Map은 각 노드가 key와 value 한 쌍으로 이루어진 트리이다. 중복을 허용하지 않는다는 특징을 가지고 있다.

따라서 Map에는 first, second가 있는 pair 객체로 저장되는데, first-key로 second-value로 저장된다.

C++ Map의 내부 구현은 검색, 삽입, 삭제가 O(logn)인 레드블랙트리로 구성된다.

 

Map의 기본 형태는 다음과 같다. 먼저 Map 또한 마찬가지로 사용하기 위해서는 Map헤더파일을 include해주어야 한다.

#include<map>

map<key_type, value_type>map1;

Map은 자료를 저장할 때 내부에서 자동으로 정렬해준다. Key를 기준으로 정렬하며 오름차순으로 정렬해준다.

만약 내림차순으로 정렬이 필요한 경우에는 "map<int, int, greater>map1;" 과 같이 사용할 수 있다.

 

만약 map에서 데이터를 찾을 때는 iterator를 사용하면 된다. 데이터를 끝까지 찾지 못했다면, iterator는 map.end() 를

반환해준다.

if(m.find("Alice") != m.end()
{
	cout<<"find"<<endl;
}
else
{
	cout<<"not find"<<endl;
}

 

map은 중복을 허용하지 않는다. insert로 key값을 넣을 때, 만약 중복된 값이라면 insert가 수행되지 않는다.

key의 역할을 제대로 수행하지 못하게 되는 것이다.

m.insert({"Cam",300});
//중복된 값이라면 실행되지 않는다.

---

map에서 데이터를 삭제할 때는 erase / clear 함수를 활용하면 된다.

//특정 위치의 요소 삭제
m.erase(m.begin() + 2);

//key값을 기준으로 요소 삭제
m.erase("Alice");

//모든 요소 삭제하기
m.erase(m.begin(), m.end());

//clear 함수로 모든 요소 삭제
m.clear();