ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Data Structure] unordered_map ์‚ฌ์šฉ๋ฒ•
    Data Structure 2020. 3. 16. 22:04
    ๋ฐ˜์‘ํ˜•
    • C++ STL์ค‘ ํ•˜๋‚˜์ธ unordered_map์— ๋Œ€ํ•œ ์„ค๋ช…์ž…๋‹ˆ๋‹ค.

    unorderd_map

    • map๋ณด๋‹ค ๋” ๋น ๋ฅธ ํƒ์ƒ‰์„ ํ•˜๊ธฐ ์œ„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.

    • unordered_map์€ ํ•ด์‰ฌํ…Œ์ด๋ธ”๋กœ ๊ตฌํ˜„ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ๋กœ ํƒ์ƒ‰ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(1)์ž…๋‹ˆ๋‹ค.

    • map์€ Binary Search Tree๋กœ ํƒ์ƒ‰ ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(log n)์ž…๋‹ˆ๋‹ค.

    • unordered_map์„ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” #include< unordered_map > ์„ ์„ ์–ธํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

    • unordered_map์€ ์ค‘๋ณต๋œ ๋ฐ์ดํ„ฐ๋ฅผ ํ—ˆ์šฉํ•˜์ง€ ์•Š๊ณ  map์— ๋น„ํ•ด ๋ฐ์ดํ„ฐ๊ฐ€ ๋งŽ์„ ์‹œ ์›”๋“ฑํžˆ ์ข‹์€ ์„ฑ๋Šฅ์„ ๋ณด์ž…๋‹ˆ๋‹ค.

    • ํ•˜์ง€๋งŒ, key๊ฐ€ ์œ ์‚ฌํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ๋งŽ์„ ์‹œ ํ•ด์‹œ ์ถฉ๋Œ๋กœ ์ธํ•ด ์„ฑ๋Šฅ์ด ๋–จ์–ด์งˆ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค.


    ํ•จ์ˆ˜

    empty( )

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

    size( )

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

    operator [ ]

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

    find( key )

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

    count( key )

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

    insert( {key, value} )

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

    erase( key )

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

    clear( )

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

    operator =

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

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

    • index๋กœ ์ ‘๊ทผํ•  ์ˆ˜ ์—†๊ณ  iterator๋กœ ์ ‘๊ทผํ•˜์—ฌ์•ผ ํ•œ๋‹ค.
    • ์‹œ์ž‘ : begin( ), ๋ : end( )
    • key : iter->first, value : iter->second
    • ๋ฐ˜๋ณต๋ฌธ ์‚ฌ์šฉ ์‹œ auto ํ™œ์šฉ or pair< key_type, value_type > ์‚ฌ์šฉ

    ์‹ค์Šต

    ๊ฒฐ๊ณผ

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