Svotin

Untitled

Feb 12th, 2023
185
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1.     template <typename K, typename V, int N>
  2.     class Map {
  3.     private:
  4.         std::array<std::pair<K, V>, N> data;
  5.         int count = 0;
  6.  
  7.         int binary_search( K key ) const {
  8.             int left = 0, right = count - 1;
  9.             while ( left <= right ) {
  10.                 int mid = left + ( right - left ) / 2;
  11.                 if ( data[ mid ].first == key ) {
  12.                     return mid;
  13.                 }
  14.                 else if ( data[ mid ].first < key ) {
  15.                     left = mid + 1;
  16.                 }
  17.                 else {
  18.                     right = mid - 1;
  19.                 }
  20.             }
  21.             return -1;
  22.         }
  23.  
  24.     public:
  25.         Map() {}
  26.  
  27.         constexpr Map( std::initializer_list<std::pair<K, V>> list ) {
  28.             count = 0;
  29.             for ( const auto& item : list ) {
  30.                 if ( count < N ) {
  31.                     data[ count++ ] = item;
  32.                 }
  33.                 else {
  34.                     break;
  35.                 }
  36.             }
  37.             std::sort( data.begin(), data.begin() + count,
  38.                 []( const auto& a, const auto& b ) { return a.first < b.first; } );
  39.         }
  40.  
  41.         V find( K key ) const {
  42.             int index = binary_search( key );
  43.             if ( index != -1 ) {
  44.                 return data[ index ].second;
  45.             }
  46.             return V();
  47.         }
  48.     };
Add Comment
Please, Sign In to add comment