fork(4) download 
  1. #include <set>
  2. #include <utility>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using std::make_pair;
  7.  
  8. template<typename X, typename Y, typename Xless = std::less<X>, typename Yless = std::less<Y>>
  9. class bimap
  10. {
  11.     typedef std::pair<X, Y>                             key_type;
  12.     typedef std::pair<X, Y>                             value_type;
  13.     typedef typename std::set<key_type>::iterator       iterator;
  14.     typedef typename std::set<key_type>::const_iterator const_iterator;
  15.  
  16.     struct Xcomp
  17.     {
  18.         bool operator()(X const &x1, X const &x2)
  19.         {
  20.             return !Xless()(x1, x2) && !Xless()(x2, x1);
  21.         }
  22.     };
  23.     struct Ycomp
  24.     {
  25.         bool operator()(Y const &y1, Y const &y2)
  26.         {
  27.             return !Yless()(y1, y2) && !Yless()(y2, y1);
  28.         }
  29.     };
  30.     struct Fless 
  31.     { // prevents lexicographical comparison for std::pair, so that 
  32.         // every .first value is unique as if it was in its own map
  33.         bool operator()(key_type const &lhs, key_type const &rhs)
  34.         {
  35.             return Xless()(lhs.first, rhs.first);
  36.         }
  37.     };
  38.     /// key and value type are interchangeable
  39.     std::set<std::pair<X, Y>, Fless> _data;
  40.  
  41. public:
  42.     std::pair<iterator, bool> insert(X const &x, Y const &y)
  43.     {
  44.         auto it = find_right(y);
  45.         if (it == end()) { // every .second value is unique
  46.             return _data.insert(make_pair(x, y));
  47.         }
  48.         return make_pair(it, false);
  49.     }
  50.     iterator find_left(X const &val)
  51.     {
  52.         return _data.find(make_pair(val,Y()));
  53.     }
  54.     iterator find_right(Y const &val)
  55.     {
  56.         return std::find_if(_data.begin(), _data.end(), 
  57.             [&val](key_type const &kt)
  58.         {
  59.             return Ycomp()(kt.second, val);
  60.         });
  61.     }
  62.     iterator end()   { return _data.end();   }
  63.     iterator begin() { return _data.begin(); }
  64. };
  65.  
  66. template<typename X, typename Y, typename In>
  67. void PrintBimapInsertion(X const &x, Y const &y, In const &in)
  68. {
  69.     if (in.second) {
  70.         std::cout << "Inserted element (" 
  71.             << in.first->first << ", " << in.first->second << ")\n";
  72.     }
  73.     else {
  74.         std::cout << "Could not insert (" << x << ", " << y << ") because (" << 
  75.             in.first->first << ", " << in.first->second << ") already exists\n";
  76.     }
  77. }
  78.  
  79.  
  80. int main()
  81. {
  82.     bimap<std::string, int> mb;
  83.     PrintBimapInsertion("A", 1, mb.insert("A", 1) );
  84.     PrintBimapInsertion("A", 2, mb.insert("A", 2) );
  85.     PrintBimapInsertion("b", 2, mb.insert("b", 2));
  86.     PrintBimapInsertion("z", 2, mb.insert("z", 2));
  87.  
  88.     auto it1 = mb.find_left("A");
  89.     if (it1 != mb.end()) {
  90.         std::cout << std::endl << it1->first << ", " << it1->second << std::endl;
  91.     }
  92.  
  93.     auto it2 = mb.find_right(2);
  94.     if (it2 != mb.end()) {
  95.         std::cout << std::endl << it2->first << ", " << it2->second << std::endl;
  96.     }
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin 
Standard input is empty
stdout 
Inserted element (A, 1)
Could not insert (A, 2) because (A, 1) already exists
Inserted element (b, 2)
Could not insert (z, 2) because (b, 2) already exists

A, 1

b, 2
https://ideone.com/ygBbYn
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!