Data Structure

[Data Stucture] map(๋งต) ์‚ฌ์šฉ๋ฒ•

An effort will never betray ๐Ÿ˜Ž 2020. 2. 22. 18:58
๋ฐ˜์‘ํ˜•
  • C++ STL ์ค‘ ํ•˜๋‚˜์ธ map์— ๋Œ€ํ•œ ์„ค๋ช…์ž…๋‹ˆ๋‹ค.

map ์ด๋ž€?

  • map์€ key์™€ value์˜ ์กฐํ•ฉ์œผ๋กœ ๊ตฌ์„ฑ๋œ container ์ž…๋‹ˆ๋‹ค.

  • map์€ key์˜ compare ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ •๋ ฌ๋ฉ๋‹ˆ๋‹ค. (๊ธฐ๋ณธ์ ์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ)

  • ์ œ๋„ˆ๋ฆญ์œผ๋กœ ๊ตฌํ˜„๋˜์–ด key์™€ value๋Š” ์–ด๋– ํ•œ type์ด ์˜ฌ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

  • map์€ binary search tree๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ์–ด์„œ unordered_map์— ๋น„ํ•ด ํƒ์ƒ‰์ด ๋Š๋ฆฝ๋‹ˆ๋‹ค. (์‹œ๊ฐ„ ๋ณต์žก๋„ O(log n))

  • map์€ ์ค‘๋ณต์„ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ณ  ์ค‘๋ณต key๋ฅผ ๊ฐ€์ง€๊ธฐ ์œ„ํ•ด์„œ๋Š” multimap์„ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

  • #include < map > ์„ ์„ ์–ธํ•ด์•ผ map ์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


๊ธฐ๋ณธ ํ•จ์ˆ˜

empty ( )

  • ๋งต์ด ๋น„์–ด์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋Š” ํ•จ์ˆ˜
  • if map is empty, then return 1 else 0

size ( )

  • ๋งต์˜ ํฌ๊ธฐ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
  • return size_type (unsigned int)

operator [ ]

  • ๋งต์—์„œ key๋ฅผ ํ†ตํ•ด value๋ฅผ ์ง€์ •ํ•˜๋Š” operator

insert ( {key, value} )

  • ๋งต์— pair<key, value>๋ฅผ ์ถ”๊ฐ€ํ•˜๋Š” ํ•จ์ˆ˜
  • if key is contained, then not insert
  • insert ํ•˜๋Š” ๋ฐฉ๋ฒ• : pair ์ถ”๊ฐ€, ํŠน์ • position์— pair ์ถ”๊ฐ€, ๋ฒ”์œ„ ์ถ”๊ฐ€

erase ( key )

  • ๋งต์—์„œ key์— ํ•ด๋‹นํ•˜๋Š” ์›์†Œ๋ฅผ ์‚ญ์ œํ•˜๋Š” ํ•จ์ˆ˜
  • erase ํ•˜๋Š” ๋ฐฉ๋ฒ• : ํŠน์ • position์˜ pair ์‚ญ์ œ, key๋กœ ๊ฒ€์ƒ‰ํ•˜์—ฌ ์‚ญ์ œ, ๋ฒ”์œ„ ์‚ญ์ œ

swap ( )

  • ๋‘ ๊ฐœ์˜ ๋งต์„ ๋ฐ”๊พธ๋Š” ํ•จ์ˆ˜

clear ( )

  • ๋งต์„ ์ดˆ๊ธฐํ™” ํ•˜๋Š” ํ•จ์ˆ˜

find ( key )

  • ๋งต์—์„œ key์— ํ•ด๋‹นํ•˜๋Š” ์›์†Œ๊ฐ€ ์žˆ๋Š”์ง€ ์ฐพ๋Š” ํ•จ์ˆ˜
  • if key is contained, then iterator else map.end()

count ( key )

  • ๋งต์—์„œ key์— ํ•ด๋‹นํ•˜๋Š” ์›์†Œ์˜ ๊ฐฏ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜
  • if key is contained, then 1 else 0

operator=

  • ๋Œ€์ž… ์—ฐ์‚ฐ์ž ๊ฐ€๋Šฅ

ํƒ์ƒ‰ ๋ฐฉ๋ฒ•

  • index๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์—†๊ณ  iterator๋ฅผ ์‚ฌ์šฉํ•ด์„œ ์ˆœ์ฐจ์  ์ ‘๊ทผ์ด ๊ฐ€๋Šฅํ•˜๋‹ค
  • ์‹œ์ž‘ : begin(), ๋ : end()
  • key : iter->first, value : iter->second
  • ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ํƒ์ƒ‰ํ•  ๊ฒฝ์šฐ auto ํ™œ์šฉ

์‹ค์Šต

๊ฒฐ๊ณผ

  • ์ถ”๊ฐ€๋กœ ๊ถ๊ธˆํ•œ ์ ์ด๋‚˜ ์ˆ˜์ •ํ•  ์‚ฌํ•ญ ์žˆ์œผ๋ฉด ๋Œ“๊ธ€๋กœ ๋‚จ๊ฒจ์ฃผ์„ธ์š”.
๋ฐ˜์‘ํ˜•