λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
🏁 42seoul ν”„λ‘œμ νŠΈ

[42seoul] Ft_containers : C++ STL μ»¨ν…Œμ΄λ„ˆ κ΅¬ν˜„

by kukim 2021. 10. 28.

πŸ“š ft_containers

@42seoul : (2021.02.02 ~ 2020.03.09)

πŸ“– About

  • 이 ν”„λ‘œμ νŠΈλŠ” C++ STL 라이브러리의 λͺ‡ 가지 Containerλ₯Ό μ΄ν•΄ν•˜κΈ° μœ„ν•΄ 직접 κ΅¬ν˜„ν•΄λ΄…λ‹ˆλ‹€. (In this project you will implement the various container types of the C++ standard template library.)
  • κ΅¬ν˜„ 사항
    • C++ 98을 λ”°λ¦…λ‹ˆλ‹€.
    • βœ… List
    • βœ… Vector
    • βœ… Map
    • βœ… Stack
    • βœ… Queue
    • βœ… 각각의 μ»¨ν…Œμ΄λ„ˆμ— λ§žλŠ” iterator

πŸ“ Review

  • STL의 μ»¨ν…Œμ΄λ„ˆλ“€μ„ 직접 κ΅¬ν˜„ν•˜λ©΄μ„œ κ°€μž₯ 큰 이점은 λ‹¨μˆœνžˆ STL ν•¨μˆ˜ μ‚¬μš©λ²•μ„ μ•„λŠ” 것을 λ„˜μ–΄ microsoft/STL μ˜€ν”ˆμ†ŒμŠ€λ₯Ό λ”°λΌκ°ˆ 수 μžˆμ—ˆμœΌλ©° μ‹€μ œ κ΅¬ν˜„μ΄ μ–΄λ–»κ²Œ λ˜μ–΄μžˆλŠ”μ§€ 확인할 수 μžˆμ—ˆλ‹€. μ΄λŠ” μ•žμœΌλ‘œ μ–΄λ–€ ν•¨μˆ˜λ“  κ΅¬ν˜„μ‚¬ν•­μ„ λœ―μ–΄λ³Ό 수 μžˆλ‹€λŠ” 생각에 두렀움이 μ‚¬λΌμ‘Œλ‹€.
  • 각 μ»¨ν…Œμ΄λ„ˆλ₯Ό κ΅¬ν˜„ν•˜κΈ° μœ„ν•΄ 자료ꡬ쑰λ₯Ό 이둠적으둜만 μ•„λŠ” 것이 μ•„λ‹Œ μ‹€μ œλ‘œ κ΅¬ν˜„ν•˜λ‹ˆ μ’€ 더 μ™€λ‹Ώμ•˜λ‹€.
    • i.e. vectorλŠ” 동적 λ°°μ—΄λ‘œ λ°°μ—΄ 크기의 μž¬ν• λ‹Ήμ„ μ‚¬μš©μžκ°€ 신경쓰지 μ•Šκ³  μ‚¬μš©ν•˜λŠ” 맀우 μœ μš©ν•œ μ»¨ν…Œμ΄λ„ˆ, μžλ£Œκ΅¬μ‘°μ΄λ‹€. (Python의 List도 동적 배열이닀) κΈ°μ‘΄ C, CPPμ—μ„œ 동적배열 자료ꡬ쑰λ₯Ό μ‚¬μš©ν•˜μ§€ μ•Šκ³  ν• λ‹Ήν•œ λ°°μ—΄ 크기λ₯Ό λ„˜μ—ˆμ„ λ•ŒλŠ” μž¬ν• λ‹Ή ν•΄μ•Όν•˜λŠ” λ²ˆκ±°λ‘œμ›€μ„ λ²—μ–΄λ‚œλ‹€λŠ” κ΅¬ν˜„ν•˜λŠ”λ° μžˆμ–΄ 동적 ν• λ‹Ή 된 λ°°μ—΄μ˜ 크기λ₯Ό 증가할 λ•Œ λ§ˆλ‹€ μƒˆλ‘­κ²Œ 동적 ν• λ‹Ήν•˜μ—¬ μΆ”κ°€ν•˜λŠ” 문제λ₯Ό ν•΄κ²°ν–ˆλ‹€. μ΄λ•Œ μž¬ν• λ‹Ή 크기λ₯Ό μ–Όλ§ˆλ§ŒνΌ μ‚¬μ΄μ¦ˆλ₯Ό μ„€μ •ν•΄μ•Όν• κΉŒλ₯Ό 찾던 쀑 Growth Factor의 값을 μ„€μ •ν•˜μ—¬ (STL κΈ°μ€€ 2) 동적할당 ν•œλ‹€λŠ” κ΅¬ν˜„ 방식이 μƒˆλ‘œμ› λ‹€.
    • i.e. Map μ»¨ν…Œμ΄λ„ˆλ₯Ό κ΅¬ν˜„ν•  λ•Œ STL은 Red-Black tree둜 κ΅¬ν˜„λ˜μ–΄ μžˆλ‹€. μ‹€μ œλ‘œ λ‚˜λ§Œμ˜ Map을 κ΅¬ν˜„ν•  λ•Œ μ²˜μŒμ—λŠ” λ‹¨μˆœ Binary tree둜 κ΅¬ν˜„ν•˜μ˜€λŠ” 데 트리 λΆˆκ· ν˜• 문제둜 κ²€μƒ‰ν•˜λŠ” 데 O(log n)을 지킀지 λͺ»ν–ˆλ‹€. 이λ₯Ό ν•΄κ²°ν•˜κΈ° μœ„ν•΄ AVL-Tree 자료ꡬ쑰둜 κ΅¬ν˜„ν•˜μ˜€κ³  Red-Black tree와 같은 평균과 μ΅œμ•…μ˜ 경우 검색,μ‚½μž…,μ‚­μ œ λͺ¨λ‘ O(log n)으둜 κ΅¬ν˜„ν•  수 μžˆμ—ˆλ‹€.
    • μ»¨ν…Œμ΄λ„ˆλ“€μ˜ μ‹œκ°„, 곡간 λ³΅μž‘λ„ κ°œμ„ ν•΄μ•Ό ν•œλ‹€. 같은 κΈ°λŠ₯이어도 .size()λ₯Ό 찍어보면 큰 차이가 λ°œμƒν–ˆλ‹€.

πŸ”— Reference

πŸ§‘πŸ»‍πŸ’» Author

kukim

νƒœκ·Έ

,

λŒ“κΈ€0