emplace()

  • 원소를 삽입할 때 중복된 key 값의 원소가 있더라도 새로운 원소를 추가한다. 
  • 이미 있는 key 값의 원소를 갱신하고 싶지 않고 새로 추가하고 싶을 때 유용하다.
  • 원소를 생성자에 매개변수로 전달하는 방식으로 추가한다. 따라서 std::map 내부에서 직접 생성하게 된다. 
  • 임시 객체 생성과 복사를 최소화하여 효율적인 원소 추가를 지원한다.

 

insert()

  • 원소를 삽입할 때 이미 중복된 key를 가진 원소가 있다면 삽입되지 않는다.
  • 이미 있는 key 값을 사용하고는 싶지만 갱신하고 싶지 않을 때 유용하다.
  • std::make_pair이나 value_type으로 값을 생성하여 insert를 해야 한다.

 

'개인 공부 > 자료구조' 카테고리의 다른 글

map, unordered_map  (0) 2022.07.19
std::map  (0) 2022.05.26
std::priority_queue  (0) 2022.05.19
std::queue  (0) 2022.05.19
STL iterator  (0) 2021.06.10

map

중복되지 않는 key를 가진 pair<const key, T>을 담는 연관 컨테이너이다.

key 값을 기준으로 sorting 되어 있고, the comparison function Compare를 사용하여 정렬된다.

대개 red-black trees를 수행한다.

 

이진 탐색 트리로 구현되면서 sorting 하므로, unordered_map보다 value를 탐색하는 데 오래 걸릴 수 있다.

 

unordered_map

map과는 달리 key나 value 기준으로 sorting 되어 있지 않다.

key 값으로 hash value를 찾는 데 시간이 적게 걸린다. (평균: O(1))

우리가 흔히 사용하는 hash 자료구조에 해당된다.

 

알고리즘 자료구조에서는 unordered_map을 일반적인 hash table 자료구조로 사용한다. (*알고리즘 문제에서는 괜찮지만 실무에서 hash table을 활용할 때 "Hash Bucket Collision" 이슈가 발생하지 않도록 주의하자.

 

 

도움 된 글

https://m.cplusplus.com/reference/map/map/?kw=map 

 

map - C++ Reference

difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t

m.cplusplus.com

https://m.cplusplus.com/reference/unordered_map/unordered_map/?kw=unordered_map 

 

unordered_map - C++ Reference

1234 unordered_map ::iterator it; (*it).first; // the key value (of type Key) (*it).second; // the mapped value (of type T) (*it); // the "element value" (of type pair )

m.cplusplus.com

https://velog.io/@pranne1224/C-unorderedmap-VS-map-%EC%BB%A8%ED%85%8C%EC%9D%B4%EB%84%88-%EC%B0%A8%EC%9D%B4%EB%8A%94

 

C++ unordered_map VS map 컨테이너 차이는...?

알고리즘 문제를 풀다 C++에서 hash table 용도로 활용하는 map 컨테이너에 대한 궁금증이 생겨 찾아보았다.일반적으로, 나의 경우 map 컨테이너를 주로 사용하는데 어떤 코드에서는 unordered_map 컨테

velog.io

 

 

'개인 공부 > 자료구조' 카테고리의 다른 글

std::map의 emplace()와 insert()  (0) 2023.08.07
std::map  (0) 2022.05.26
std::priority_queue  (0) 2022.05.19
std::queue  (0) 2022.05.19
STL iterator  (0) 2021.06.10

개요

중복되지 않는 key를 가진 key-value 쌍을 담는 컨테이너이다.

key는 the comparison function Compare를 사용하여 정렬된다.

대개 red-black trees를 수행한다.

 

 

 

 

ref

https://en.cppreference.com/w/cpp/container/map

 

std::map - cppreference.com

(1) (2) (since C++17) std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usual

en.cppreference.com

 

'개인 공부 > 자료구조' 카테고리의 다른 글

std::map의 emplace()와 insert()  (0) 2023.08.07
map, unordered_map  (0) 2022.07.19
std::priority_queue  (0) 2022.05.19
std::queue  (0) 2022.05.19
STL iterator  (0) 2021.06.10

 

개요

heap이라 불리는 유용한 구조 제공.

heap은 컨테이너에서 가장 작거나 큰 원소에 빠르게 접근할 수 있는 자료구조.

 

시간 복잡도

최소/최대 원소에 접근하는 동작은 O(1), 원소 삽입은 O(logn)로 동작.

 

특징

최소/최대 원소에 대해서만 원소 제거가 가능.

stack이나 queue와 달리 vector를 기본 컨테이너로 사용.

비교자는 std::less가 기본.

 

언제든 특정 위치에 있는 원소 하나만을 참조하면 되기 때문에, 반복자를 지원하지 않는다.

 

더 자세한 내용은

https://en.cppreference.com/w/cpp/container/priority_queue

 

std::priority_queue - cppreference.com

template<     class T,     class Container = std::vector ,     class Compare = std::less > class priority_queue; A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarit

en.cppreference.com

 

 

 

'개인 공부 > 자료구조' 카테고리의 다른 글

std::map의 emplace()와 insert()  (0) 2023.08.07
map, unordered_map  (0) 2022.07.19
std::map  (0) 2022.05.26
std::queue  (0) 2022.05.19
STL iterator  (0) 2021.06.10

FIFO

이터레이터를 지원하지 않는다.

 

 

 

도움 된 글

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=cksdn788&logNo=220485144752 

 

[Grind Away] c++ STL Queue에서는 탐색(검색)이 불가능합니다.

큐(queue)는 선입선출(FIFO)을 특징으로 하는 자료구조입니다. 먼저 들어온 데이터를 먼저 나가게끔 하...

blog.naver.com

https://min-310.tistory.com/64

 

[C & C++] STL 반복자 iterator

안녕하세요. 허언증입니다. 포인터와 상당히 비슷하며, vector, deque, set, map, list등과 같은 컨테이너에 저장되어 있는 원소를 참조(접근)할 때 사용됨 (stack, queue에는 iterator가 없음) 반복자는 컨테

min-310.tistory.com

http://www.cplusplus.com/reference/queue/queue/?kw=queue 

 

queue - C++ Reference

container_typeThe second template parameter (Container)Type of the underlying container

www.cplusplus.com

 

'개인 공부 > 자료구조' 카테고리의 다른 글

std::map의 emplace()와 insert()  (0) 2023.08.07
map, unordered_map  (0) 2022.07.19
std::map  (0) 2022.05.26
std::priority_queue  (0) 2022.05.19
STL iterator  (0) 2021.06.10

두고두고 보려고 적음.

https://enghqii.tistory.com/22

 

stl에는 iterator가 없는 컨테이너도 있다.

>>2013-10-09에 구글 드라이브에 작성. >>2015-01-13에 에버노트로 이동. 1.이야기 회사에서 타일맵 위에서의 A-star 길찾기 알고리즘을 구현할 일이 생겼었다. astar는 고3 때 수능 끝나고 만들던 게임에서

enghqii.tistory.com

 

'개인 공부 > 자료구조' 카테고리의 다른 글

std::map의 emplace()와 insert()  (0) 2023.08.07
map, unordered_map  (0) 2022.07.19
std::map  (0) 2022.05.26
std::priority_queue  (0) 2022.05.19
std::queue  (0) 2022.05.19

+ Recent posts