deque, map

🎈deque

deque - (double ended queue) 컨테이너의 맨 앞과 맨 뒤에서 삽입/제거를 빠르게 할 수 있다는 것이 대표적 특징이다. 스택(LIFO)과 큐(FIFO)를 합쳐놓은 것이라고 생각하면 될 것 같다.

---

🎇deque 의 헤더파일

#include <deque>

---

🎇deque 의 특징 (다른 자료구조들과의 비교)

• vector 처럼 원소들을 [] 인덱스를 사용하여 Random Access 가 가능하다.
  • stack 과 queue 와 차별화된 강점
• vector 처럼 원소들을 어떤 순서로든 앞로든 뒤 원소들을 순회할 수 있다.
• vector 가 capacity 가 고갈되면 전체 메모리 크기의 이상을 재할당 받는 것과 달리 deque 는 일정 크기를 가지는 chunk 단위로 메모리가 확장된다.
  • vector 보다 확장 비용이 절감된다.
• vector 와 달리 연속 메모리 공간이 아니다.
  • 따라서 vector와 달리 포인터 연산이 불가능하다.
• list 처럼 연속 메모리 공간이 아니다.
• stack, vector, list 처럼 맨 뒤에서 삽입/제거 하는 것이 빠르다.
  • queue 은 오직 맨 앞에서만 제거가 가능하지만 deque 는 맨 뒤에서도 제거가 가능
  • stack 과 queue 가 deque 로 구현 가능한 이유.
• queue, list 처럼 맨 앞에서 삽입/제거 하는 것이 빠르다.
  • vector 와 차별화된 강점
  • stack 은 오직 맨 뒤에서만 제거가 가능하지만 deque 는 맨 앞에서도 제거가 가능
  • stack 과 queue 가 deque 로 구현 가능한 이유.
• list 와 달리 맨 뒤, 맨 앞이 아닌 중간 원소를 삽입/제거 하는 것은 느리다.

---

🎇 deque의 push_front( ) 와 pop_front( )를 지원

: vector의 경우 push_back( ) , pop_back( ) 뒤에서 삽입, 삭제만을 제공한다. 하지만, deque는 'double-ended queue'에서 붙여진 이름답게 컨테이너 양쪽 끝에서 요소를 모두 삽입, 삭제가 가능하다.

  

🎇. vector의 capacity( ) 와 reserve( ) : deque 같은 경우에는 이런 함수가 필요없기 때문에 지원하지 않고 있는 것인데 이유를 알려면 각 형식이 메모리를 어떻게 관리 하고 있는지 알 필요가 있다.

 

  🎆 vector의 경우에는 연속된 메모리 구조를 사용한다.

  ex) 예를 들어 10MB의 vector는 연속된 10MB의 메모리를 사용하게 된다.

   ->하지만 경우에 따라서 연속된것이 아니라 10MB를 작은 블록으로 여러개 나누어서 사용하는 것이 성능이 더 좋을 수도 있다.

 

   🎆 deque의 경우 작은 메모리 블럭을 연결하여 데이터를 구성한다.

---

🎈 Map

MAP은 노드가 KEY: VALUE 쌍으로 이루어진 트리형식의 구조이며 중복을 허용하지 않는다. 

MPA은 First, Second가 있는 Pair객체로 저장되며 First-key , Second-value로 저장되는 형식을 가지고있다.

C++의 STL MAP의 기능은 시간복잡도 O(log N)인 레드블랙트리로 구성되어 있다.

---

🎇map의 기본함수 

🎇Map의 헤더파일 

#include<map>;

 

🎇Map의 기본 형

map<key, value> m;

map은 자료를 저장할때 내부에서 자동으로 정렬하게 된다. 여기서 map은 key를 기준으로 정렬하게 되며 오름차순으로 정렬하게 된다.

만약 내림차순으로 정렬하고자 한다면

map<int, int,greater> m;  선언 이후  데이터에 마이너스를 붙여 삽입하면 내림차순 정렬이 된다.

 

🎇map 선언하기 

map<key type, value type>이 기본 구조이며  선언시

map<string, int> m;

 

🎇map search 하기 ( 데이터 확인 ) 

iterator를 사용하여 map의 데이터를 확인하게 된다.

데이터를 끝까지 찾지 못했을 경우, iterator는 map.end()를 반환한다.

#include <iostream>
#include <map>
#include <string>

map<string, int> m;

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

---

🎇map에 데이터 삽입

-위에서도 말했지만 map은 데이터의 중복을 허용하지 않는다. 그렇기 떄문에 insert를 진행할때 key가 중복이 된다면 insert가 수행되지 않는다.

m.insert({"cam", 300});

---

🎇반복문 데이터 접근 ( first, second) 

인덱스 기반 반복문 

( 인덱스 기반은 iterator를 활용하여 begin() 부터 end()까지 조회하는것 )

for( auto iter = m.begin(); iter!= m.end(); iter++)
{
	cout<< iter->first <<" "<< iter->second <<endl;
}
cout<< endl;

범위 기반 반복문 활용 

for(auto iter:m)
{
	cout<<iter.first<<""<iter.second<<endl;
}

---

🎇map에서 데이터 삭제 

map에서 데이터 삭제하기 위해 활용하는 함수는 erase와 clear이다 

 

특정위치의 요소 삭제

m.erase(m.begin()+2);

 

key값을 기준으로 요소 삭제

m.erase("alice");

map의 모든 데이터 삭제

erase 함수로 모든 요소 삭제 (map의 begin()부터 end()까지 )

m.erase(m.begin(), m.end());

clear 함수로 모든 요소 삭제

m.clear();

---