blc/bimap/blc_bidirectional_map.h - C++ 양방향 맵 라이브러리

bidirectional map(양방향 맵)은 first와 second가 모두 키 역할을 할 수 있는 컨테이너 입니다. 이런 컨테이너는 first와 second가 1:1 대응 또는 1:n 또는 n:1 대응관계를 가질 때 사용할 수 있습니다. 예를 들어 CP949 코드 페이지와 유니코드를 맵핑시킨 테이블 등을 만들때 사용될 수 있습니다.

이 문서에서는 blc_bidirectional_map.h의 구성요소에 대해서 설명합니다. 아래에 설명된 요소들은 모두 namespace blc::bimap 내부에 선언되어 있습니다.

• class BidirectionalMap final

  ---

  BidirectionalMap의 선언문은 다음과 같이 생겼습니다.
  
  

  1. template <
  2. typename FirstType_,
  3. typename SecondType_,
  4. template <typename, typename, template <typename> class> class ContainerType_ = ContainerMap,
  5. bool kUseReadLock = true,
  6. template <typename, bool> class ThreadingModel_ = Loki::SingleThreaded,
  7. template <typename> class Allocator_ = std::allocator,
  8. typename = std::enable_if_t<
  9. IsBimapContainerTPL<ContainerType_>::value &&
  10. Loki::IsThreadingModelTPL<ThreadingModel_>::value
  11. >
  12. >
  13. class BidirectionalMap;

  
  각 템플릿 인수의 의미는 다음과 같습니다.

  1. FirstType_
     첫 번째 키 역할을 할 타입입니다. 첫 번째 키 값을 통해, 두 번째 키 값을 검색할 수 있습니다.
  2. SecondType_
     두 번째 키 역할을 할 타입입니다. 두 번째 키 값을 통해, 첫 번째 키 값을 검색할 수 있습니다.
  3. ContainerType_
     컨테이너 단위전략입니다. 단위전략에 따라 중복된 키 허용 여부와 내부적으로 사용되는 컨테이너를 변경할 수 있습니다. 제공되는 컨테이너 단위전략은 다음과 같습니다.
     
     
     • ContainerMultiMap: 내부적으로 std::multimap과 std::multiset이 사용됩니다(키 중복 허용).
     • ContainerMap: 내부적으로 std::map과 std::set이 사용됩니다(키 중복 비허용). 컨테이너 단위전략을 지정하지 않으면 기본으로 적용되는 단위전략입니다.
     • ContainerMultiVec: 내부적으로 std::vector가 사용됩니다(키 중복 허용).
     • ContainerVec: 내부적으로 std::vector가 사용됩니다(키 중복 비허용).
     • ContainerUnorderedMultiMap: 내부적으로 std::unordered_multimap과 std::unordered_multiset이 사용됩니다(키 중복 허용).
     • ContainerUnorderedMap: 내부적으로 std::unordered_map과 std::unordered_set이 사용됩니다(키 중복 비허용).
     
     중복을 허용하는 단위전략의 경우, 원소를 삽입할 때 중복 검사를 하지 않으므로, 중복을 허용하지 않는 단위전략에 비해 삽입 속도가 빠릅니다.
     
     탐색 결과값이 단 하나인 멤버 함수(FirstToSecond, SecondToFirst)의 경우, 중복 허용 여부에 상관없이 비슷한 성능을 냅니다. 단, 중복 허용 컨테이너에서 결과 값이 여러개가 될 수 있는 경우에 FirstToSecond또는 SecondToFirst 멤버 함수를 사용하여 탐색하면, 여러 개의 결과 후보 중 항상 같은 결과 값이 반환된다는 보장을 해 주지는 않습니다.
     
     결과값이 여러개인 멤버 함수(FirstToSecondRange, SecondToFirstRange)의 경우 중복을 허용하지 않는 단위전략의 탐색속도가 더 빠릅니다. 이 경우, 중복을 허용하는 단위전략은 여러개의 결과값을 벡터에 담아, 오름차순으로 정렬하여 반환합니다.
     
     양방향 맵의 내부에는 std::pair<FirstType_, SecondType_>를 FirstType_ 기준으로 정렬하여 담는 주 컨테이너와, 주 컨테이너의 반복자를 SecondType_ 기준으로 정렬하여 담는 보조 컨테이너가 포함됩니다. 벡터는 삽입 혹은 삭제가 일어날 때마다 반복자가 무효화 되므로, 삽입 삭제가 일어날 때마다 보조 컨테이너를 새로 채워야 합니다. 따라서 내부적으로 벡터를 사용하는 단위전략은 내부적으로 std::map 계열의 컨테이너를 사용하는 단위전략에 비해, 원소의 삽입 삭제 속도가 매우 느립니다. 대신 메모리의 지역성이 증가하기 때문에, 내부적으로 std::map 계열의 컨테이너를 사용하는 단위전략보다 탐색 속도가 약간 빠릅니다.
     
     내부적으로 std::unordered_map 계열의 컨테이너를 사용하는 단위전략이 모든 면에서 가장 빠른 성능을 냅니다. 단, std::unordered_map 계열의 단위전략을 사용하기 위해서 FirstType_과 SecondType_ 모두에 std::hash를 적용할 수 있어야 합니다.
     
     FirstToSecond(Range) 멤버 함수가 SecondToFirst(Range) 멤버 함수보다 속도가 빠릅니다. SecondToFirst(Range) 멤버 함수는, 보조 컨테이너에 담긴 주 컨테이너의 반복자를 간접참조하며 탐색하기 때문입니다.
  4. kUseReadLock
     이 비타입 인수가 true값을 갖는 경우, 가능한 경우 멀티스레드 동기화에 std::shared_mutex::lock_shared를 사용할 수 있도록 합니다. 반대로 이 비타입 인수가 false값을 갖는 경우, 모든 스레드 동기화에 std::shared_mutex::lock을 사용하게 됩니다. 기본값은 true 입니다.
     참고자료
  5. ThreadingModel_
     멀티스레드 동기화 관련된 단위전략입니다. 기본값은 Loki::SingleThreaded(동기화 하지 않음) 입니다.
     참고자료1, 참고자료2
  6. Allocator_
     할당자 입니다. 여기서 지정한 할당자는 std::(multi)map, std::(multi)set, std::vector, std::unordered_(multi)map, std::unordered_(multi)set에 그대로 사용됩니다.

  ---

  
  
  • using 선언된 타입
    • Base

      ---

      컨테이너 단위전략의 별칭입니다(BidirectionalMap은 컨테이너 단위전략을 상속받습니다).

      ---

      
      
    • ThreadingModel

      ---

      적용중인 스레딩 단위전략의 별칭입니다.
      참고자료1, 참고자료2

      ---

      
      
    • IterType

      ---

      주 컨테이너(ContainerType)의 상수 반복자 타입 별칭입니다.

      ---

      
      
    • DataType

      ---

      std::pair<FirstType_, SecondType_>의 별칭입니다. 컨테이너 단위전략에 따라 FirstType_앞에 const가 붙을 수 있습니다.

      ---

      
      
    • IdxContainerType

      ---

      보조 컨테이너(IterType을 담는 컨테이너) 타입의 별칭입니다.

      ---

      
      
    • IndirectIterType

      ---

      보조 컨테이너(IdxContainerType)의 상수 반복자 타입 별칭입니다.

      ---

      
      
    • FirstType

      ---

      첫 번째 키 타입(FirstType_)의 별칭입니다.

      ---

      
      
    • SecondType

      ---

      두 번째 키 타입(SecondType_)의 별칭입니다.

      ---

      
      
    • DirectFirstComp

      ---

      주 컨테이너(ContainerType)에 사용되는 비교 함수자 타입의 별칭입니다. DataType(std::pair<FirstType_, SecondType_>)에서, std::less를 FirstType_에만 적용시킨 타입과 동일합니다. 예외로, 컨테이너 단위전략이 ContainerUnordered(Multi)Map인 경우에는 DataType에서, std::equal_to를 FirstType_에만 적용시킨 타입과 동일합니다.

      ---

      
      
    • IndirectSecondComp

      ---

      보조 컨테이너(IdxContainerType)에 사용되는 비교 함수자 타입의 별칭입니다. IterType(주 컨테이너(ContainerType)의 상수 반복자 타입) 객체가 가리키는 DataType에서, std::less를 SecondType_에만 적용시킨 타입과 동일합니다. 예외로, 컨테이너 단위전략이 ContainerUnordered(Multi)Map인 경우에는 IterType 객체가 가리키는 DataType에서, std::equal_to를 SecondType_에만 적용시킨 타입과 동일합니다.

      ---

      
      
    • ContainerType

      ---

      주 컨테이너(DataType을 담는 컨테이너) 타입의 별칭입니다.

      ---

      
      
    • key_type

      ---

      첫 번째 키 타입(FirstType_)의 별칭입니다.

      ---

      
      
    • mapped_type

      ---

      두 번째 키 타입(SecondType_)의 별칭입니다.

      ---

      
      
    • value_type

      ---

      주 컨테이너의 value_type 별칭입니다(const ContainerType::value_type의 별칭).

      ---

      
      
    • key_compare

      ---

      DirectFirstComp의 별칭입니다.

      ---

      
      
    • allocator_type

      ---

      할당자(Allocator_<DataType>)의 별칭입니다.

      ---

      
      
    • reference

      ---

      주 컨테이너의 reference 별칭입니다(ContainerType::reference의 별칭).

      ---

      
      
    • const_reference

      ---

      주 컨테이너의 const_reference 별칭입니다(ContainerType::const_reference의 별칭).

      ---

      
      
    • pointer

      ---

      주 컨테이너의 pointer 별칭입니다(ContainerType::pointer의 별칭).

      ---

      
      
    • const_pointer

      ---

      주 컨테이너의 const_pointer 별칭입니다(ContainerType::const_pointer의 별칭).

      ---

      
      
    • const_iterator

      ---

      IterType의 별칭입니다.

      ---

      
      
    • size_type

      ---

      주 컨테이너의 size_type 별칭입니다(ContainerType::size_type의 별칭).

      ---

      
      
    • difference_type

      ---

      주 컨테이너의 difference_type 별칭입니다(ContainerType::difference_type의 별칭).

      ---

      
      
    • ReadLock

      ---

      비타입 템플릿 인수 kUseReadLock가 true인 경우에는 std::shared_mutex::lock_shared를, false인 경우에는 std::shared_mutex::lock을 사용하는 스레드 동기화 객체의 별칭입니다. 상세한 사용법은 아래의 참고자료에 나와 있습니다.
      참고자료

      ---

      
      
    • WriteLock

      ---

      비타입 인수 kUseReadLock의 값과 상관없이 언제나 std::shared_mutex::lock을 사용하는 스레드 동기화 객체의 별칭입니다. 상세한 사용법은 아래의 참고자료에 나와 있습니다.
      참고자료

      ---

      
      
    • WriteReadLock

      ---

      생성자의 첫 번째 인수에 대해 WriteLock을, 두 번째 인수에 대해 ReadLock을 사용하는 스레드 동기화 객체의 별칭입니다. 자세한 사용법은 아래의 참고자료에 나와 있습니다.
      참고자료

      ---

      
      
    • WriteWriteLock

      ---

      생성자의 첫 번째 인수와 두 번재 인수 모두에 대해 WriteLock을 사용하는 스레드 동기화 객체의 별칭입니다. 자세한 사용법은 아래의 참고자료에 나와 있습니다.
      참고자료

      ---

      
      
  • 멤버 함수 (템플릿)
    • inline ~BidirectionalMap()

      ---

      class BidirectionalMap의 소멸자 입니다. BidirectionalMap 객체 소멸 시, 주 컨테이너와 보조 컨테이너의 소멸자를 호출합니다.

      ---

      
      
    • BidirectionalMap(...)

      ---

      class BidirectionalMap의 생성자 입니다. 생성자는 5 가지의 오버로드 버전이 존재합니다(그 중 하나는 템플릿 생성자).
      
      

      1. //-----------------------------------------------------------------------------
      2. // 1
      3. inline BidirectionalMap();
      4.  
      5. // 기본 생성자 입니다. 주 컨테이너와 보조 컨테이너의 기본 생성자를 호출합니다.
      6.  
      7.  
      8. //-----------------------------------------------------------------------------
      9. // 2
      10. inline BidirectionalMap(const BidirectionalMap&);
      11.  
      12. // 복사 생성자입니다. 주 컨테이너와 보조 컨테이너의 복사 생성자를 호출합니다.
      13.  
      14.  
      15. //-----------------------------------------------------------------------------
      16. // 3
      17. BidirectionalMap(const std::initializer_list<DataType>& data);
      18.  
      19. // 중괄호 초기치를 통해 BidirectionalMap 객체를 생성합니다.
      20.  
      21.  
      22. //-----------------------------------------------------------------------------
      23. // 4
      24. inline BidirectionalMap(BidirectionalMap&& rhs) noexcept;
      25.  
      26. // 이동 생성자입니다. rhs와 기본 생성자로 생성된 this를 바꿔치기(swap) 합니다.
      27.  
      28.  
      29. //-----------------------------------------------------------------------------
      30. // 5
      31. template <typename IterType_>
      32. BidirectionalMap(IterType_ begin, IterType_ end);
      33.  
      34. // 반복자를 통한 생성자 입니다. DataType을 담는
      35. // 다른 컨테이너의 반복자로부터 생성할 수 있습니다.

      
      키의 중복을 허용하지 않는 단위전략을 사용한다면, 첫 번째 키와 두 번째 키 모두 중복을 허용하지 않습니다. 키의 중복을 허용하는 단위전략을 사용한다면, 첫 번째 키와 두 번째 키 모두 중복을 허용합니다.

      ---

      
      
    • inline BidirectionalMap& operator =(...) &

      ---

      대입 연산자 입니다. 대입 연산자는 복사 대입 연산자와 이동 대입 연산자 두 가지 버전이 오버로딩 되어 있습니다. 복사 대입 연산자는 주 컨테이너와 보조 컨테이너의 복사 대입 연산자를 호출하여 BidirectionalMap 객체를 복사합니다. 이동 대입 연산자는, 이동 대입 연산자의 매개변수(BidirectionalMap의 우측값)와 this를 바꿔치기(swap) 합니다.

      ---

      
      
    • inline void swap(BidirectionalMap& rhs) noexcept

      ---

      this 내의 주 컨테이너와 rhs 내의 주 컨테이너를, this 내의 보조 컨테이너와 rhs 내의 보조 컨테이너를 서로 바꿉니다.

      ---

      
      
    • auto Insert(...) &

      ---

      BidirectionalMap 객체에 원소를 삽입하는 멤버 함수입니다. DataType 객체 하나를 받는 버전과, 반복자 범위를 받는 버전이 오버로딩 되어 있습니다.
      
      

      1. //-----------------------------------------------------------------------------
      2. // 1
      3. auto Insert(const DataType& data) &;
      4.  
      5. // 중복을 허용하는 컨테이너 단위전략을 사용할때는 항상 삽입에 성공합니다.
      6. // DataType 객체 하나를 삽입하고, 삽입된 요소를 가리키는 반복자를 반환합니다.
      7.  
      8. // 중복을 허용하지 않는 컨테이너 단위전략을 사용할때는, 반복자와 삽입 성공 여부를
      9. // 나타내는 bool 값의 쌍(std::pair)이 반환됩니다.
      10. // 삽입에 성공한 경우, 삽입된 요소를 가리키는 반복자와 true를
      11. // std::pair로 묶어 반환합니다.
      12. // 삽입에 실패한다면, 첫 번째 키 또는 두 번째 키가 중복되어 있는
      13. // 요소를 가리키는 반복자와 false를 std::pair로 묶어 반환합니다.
      14.  
      15. // 반환된 반복자는 주 컨테이너의 반복자 입니다.
      16.  
      17.  
      18. //-----------------------------------------------------------------------------
      19. // 2
      20. template <typename IterType_>
      21. size_t Insert(IterType_ begin, IterType_ end) &;
      22.  
      23. // 주어진 반복자 범위의 원소를 삽입하고, 삽입에 성공한 원소의 수를 반환합니다.

      
      키의 중복을 허용하지 않는 단위전략을 사용한다면, 첫 번째 키와 두 번째 키 모두 중복을 허용하지 않습니다. 키의 중복을 허용하는 단위전략을 사용한다면, 첫 번째 키와 두 번째 키 모두 중복을 허용합니다.

      ---

      
      
    • auto Erase(...) &

      ---

      BidirectionalMap 객체 내의 특정 원소를 삭제합니다. Erase 멤버 함수는 3가지의 오버로드 버전이 존재합니다.
      
      

      1. //-----------------------------------------------------------------------------
      2. // 1
      3. auto Erase(const DataType& data) &;
      4.  
      5. // DataType 객체 하나를 삭제하고, 삭제 성공 여부를 반환합니다.
      6. // (삭제에 성공하면 true 반환)
      7.  
      8.  
      9. //-----------------------------------------------------------------------------
      10. // 2
      11. auto Erase(IterType iter) &;
      12.  
      13. // 반복자가 가리키는 원소를 삭제하고,
      14. // 삭제된 원소의 다음 원소를 가리키는 반복자를 반환합니다.
      15.  
      16.  
      17. //-----------------------------------------------------------------------------
      18. // 3
      19. auto Erase(IterType begin, IterType end) &;
      20.  
      21. // 반복자 범위에 포함된 원소들을 삭제하고,
      22. // 삭제된 원소들의 다음 원소를 가리키는 반복자를 반환합니다.

      ---

      
      
    • inline auto FirstToSecondRange(const FirstType& first) const

      ---

      첫 번째 키(FirstType_) 값과 매칭되는 두 번째 키(SecondType_) 값들을 모두 구하는 멤버 함수 입니다. 첫 번째 키와 매칭되는 두 번째 키 값들의 포인터를 담은 벡터가 반환됩니다. 이 벡터는 두 번째 키 값의 오름차순으로 정렬되어 있으며, 첫 번째 키 값과 매칭되는 두 번째 키 값이 없는 경우 빈 벡터가 반환됩니다. FirstToSecond 멤버 함수보다 실행속도가 느리므로, 중복 비허용 컨테이너 단위전략을 사용하거나, 첫 번째 키와 매칭되는 두 번째 키 값이 하나 이하인 경우에는 FirstToSecond 멤버 함수를 호출하는 편이 낫습니다.

      ---

      
      
    • inline auto SecondToFirstRange(const SecondType& second) const

      ---

      두 번째 키(SecondType_) 값과 매칭되는 첫 번째 키(FirstType_) 값들을 모두 구하는 멤버 함수 입니다. 두 번째 키와 매칭되는 첫 번째 키 값들의 포인터를 담은 벡터가 반환됩니다. 이 벡터는 첫 번째 키 값의 오름차순으로 정렬되어 있으며, 두 번째 키 값과 매칭되는 첫 번째 키 값이 없는 경우 빈 벡터가 반환됩니다. SecondToFirst 멤버 함수보다 실행속도가 느리므로, 중복 비허용 컨테이너 단위전략을 사용하거나, 두 번째 키와 매칭되는 첫 번째 키 값이 하나 이하인 경우에는 SecondToFirst 멤버 함수를 호출하는 편이 낫습니다.

      ---

      
      
    • inline const auto* const FirstToSecond(const FirstType& first) const

      ---

      첫 번째 키(FirstType_) 값과 매칭되는 두 번째 키(SecondType_) 값 하나를 구하는 멤버 함수 입니다. 첫 번째 키와 매칭되는 두 번째 키 값의 포인터가 반환됩니다. 첫 번째 키 값과 매칭되는 두 번째 키 값이 없는 경우 nullptr이 반환됩니다. FirstToSecondRange 멤버 함수보다 실행속도가 빠르므로, 중복 비허용 컨테이너 단위전략을 사용하거나, 첫 번째 키와 매칭되는 두 번째 키 값이 하나 이하인 경우에는 FirstToSecond 멤버 함수를 호출하는 편이 낫습니다. 만일 첫번째 키와 매칭되는 두 번째 키 값이 여러개인 경우에는(중복 허용 컨테이너 단위전략 사용시), 첫 번째 키와 매칭되는 여러 개의 두 번째 키들 중, 항상 같은 결과 값이 반환된다는 보장을 해 주지는 않습니다.

      ---

      
      
    • inline const auto* const SecondToFirst(const SecondType& second) const

      ---

      두 번째 키(SecondType_) 값과 매칭되는 첫 번째 키(FirstType_) 값 하나를 구하는 멤버 함수 입니다. 두 번째 키와 매칭되는 첫 번째 키 값의 포인터가 반환됩니다. 두 번째 키 값과 매칭되는 첫 번째 키 값이 없는 경우 nullptr이 반환됩니다. SecondToFirstRange 멤버 함수보다 실행속도가 빠르므로, 중복 비허용 컨테이너 단위전략을 사용하거나, 두 번째 키와 매칭되는 첫 번째 키 값이 하나 이하인 경우에는 SecondToFirst 멤버 함수를 호출하는 편이 낫습니다. 만일 두 번째 키와 매칭되는 첫 번째 키 값이 여러개인 경우에는(중복 허용 컨테이너 단위전략 사용시), 두 번째 키와 매칭되는 여러 개의 첫 번째 키들 중, 항상 같은 결과 값이 반환된다는 보장을 해 주지는 않습니다.

      ---

      
      
    • inline auto cbegin() const noexcept

      ---

      주 컨테이너의 cbegin() 멤버 함수를 호출하여 얻은 상수 반복자를 그대로 반환합니다. 반복자를 사용하여 BidirectionalMap 의 요소들을 순회할 때 반드시 요소들이 정렬되어 있다는 보장을 해 주지 않습니다(컨테이너 단위전략에 따라 다름).

      ---

      
      
    • inline auto cend() const noexcept

      ---

      주 컨테이너의 cend() 멤버 함수를 호출하여 얻은 상수 반복자를 그대로 반환합니다. 반복자를 사용하여 BidirectionalMap 의 요소들을 순회할 때 반드시 요소들이 정렬되어 있다는 보장을 해 주지 않습니다(컨테이너 단위전략에 따라 다름).

      ---

      
      
    • inline auto size() const noexcept

      ---

      BidirectionalMap 객체 안에 담긴 요소의 개수를 반환합니다. 반환 타입은 size_type 입니다(일반적으로 size_t).

      ---

      
      
    • inline auto empty() const noexcept

      ---

      BidirectionalMap 객체 안에 담긴 요소가 하나도 없는 경우(비어 있는 경우) true를, 그렇지 않은 경우 false를 반환합니다.

      ---

      
      
    • inline void clear() noexcept

      ---

      BidirectionalMap 객체 안에 담긴 요소들을 모두 삭제합니다.

      ---

      
      
    • inline bool operator ==(const BidirectionalMap& rhs) const

      ---

      this와 rhs에 포함된 주 컨테이너끼리 비교하여 같은 경우 true를, 다른 경우 false를 반환합니다.

      ---

      
      
    • inline bool operator !=(const BidirectionalMap& rhs) const

      ---

      this와 rhs에 포함된 주 컨테이너끼리 비교하여 같은 경우 false를, 다른 경우 true를 반환합니다.

      ---