fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3. #include <memory>
  4. #include <utility>
  5.  
  6. template<typename firstKeyT,
  7.          typename secondKeyT,
  8.          typename mappedT,
  9.          typename CompareT = std::less<std::pair<firstKeyT, secondKeyT> >,
  10.          typename AllocT = std::allocator<std::pair<firstKeyT, secondKeyT> > >
  11. class trimap : public std::map<std::pair<firstKeyT, secondKeyT>,
  12.                                mappedT,
  13.                                CompareT,
  14.                                AllocT>
  15. {
  16.         typedef std::map<std::pair<firstKeyT, secondKeyT>,
  17.                          mappedT,
  18.                          CompareT,
  19.                          AllocT> map_type;
  20.  
  21.         map_type::insert;
  22.  
  23.         typedef typename map_type::value_type value_type;
  24.         typedef typename map_type::mapped_type mapped_type;
  25.         typedef typename map_type::iterator iterator;
  26.         typedef typename map_type::const_iterator const_iterator;
  27.         typedef typename map_type::size_type size_type;
  28.         typedef typename map_type::key_compare key_compare;
  29.         typedef typename map_type::value_compare value_compare;
  30.         typedef typename map_type::allocator_type allocator_type;
  31.         typedef typename map_type::reference reference;
  32.         typedef typename map_type::const_reference const_reference;
  33.         typedef typename map_type::difference_type difference_type;
  34.         typedef typename map_type::pointer pointer;
  35.         typedef typename map_type::const_pointer const_pointer;
  36.         typedef typename map_type::reverse_iterator reverse_iterator;
  37.         typedef typename map_type::const_reverse_iterator const_reverse_iterator;
  38.  
  39.         struct index_proxy1
  40.         {
  41.                 trimap& mMap;
  42.                 firstKeyT const& mgivenKey;
  43.  
  44.                 index_proxy1(trimap& m,
  45.                             firstKeyT const& k):
  46.                         mMap(m),
  47.                         mgivenKey(k){}
  48.  
  49.                 mapped_type& operator[](secondKeyT const& k)
  50.                 {
  51.                         return mMap.map_type::operator[](std::make_pair(mgivenKey, k));
  52.                 }
  53.         };
  54.  
  55.         struct index_proxy2
  56.         {
  57.                 trimap& mMap;
  58.                 secondKeyT const& mgivenKey;
  59.  
  60.                 index_proxy2(trimap& m,
  61.                             secondKeyT const& k):
  62.                         mMap(m),
  63.                         mgivenKey(k){}
  64.  
  65.                 mapped_type& operator[](firstKeyT const& k)
  66.                 {
  67.                         return mMap.map_type::operator[](std::make_pair(k, mgivenKey));
  68.                 }
  69.         };
  70.  
  71. public:
  72.  
  73.         map_type::end;
  74.         map_type::begin;
  75.         map_type::clear;
  76.         map_type::find;
  77.         map_type::empty;
  78.         map_type::get_allocator;
  79.         map_type::key_comp;
  80.         map_type::max_size;
  81.         map_type::operator=;
  82.         map_type::rbegin;
  83.         map_type::rend;
  84.         map_type::size;
  85.         map_type::swap;
  86.         map_type::value_comp;
  87.  
  88.         trimap(trimap const& m):
  89.                 map_type(m){}
  90.  
  91.         explicit trimap ( CompareT const& comp = CompareT(),
  92.                           AllocT const& alloc = AllocT() ):
  93.                 map_type(comp, alloc) {}
  94.  
  95.         template <class InputIterator>
  96.                 trimap ( InputIterator first,
  97.                       InputIterator last,
  98.                       CompareT& comp = CompareT(),
  99.                       AllocT const& alloc = AllocT() ):
  100.                         map_type(comp, alloc)
  101.                 {
  102.                         insert(first, last);
  103.                 }
  104.  
  105.  
  106.         std::pair<iterator,bool> insert ( const value_type& x )
  107.         {
  108.                 typename map_type::iterator t1 = find(x.first),
  109.                                             t2 = find(std::make_pair(x.first.second, x.first.first));
  110.                 if(t1 == end()
  111.                 && t2 == end())
  112.                         return map_type::insert(x);
  113.  
  114.                 return std::make_pair((t1 == end() ? t2 : t1), false);
  115.         }
  116.  
  117.         template <class InputIterator>
  118.                void insert ( InputIterator first, InputIterator last )
  119.                {
  120.                        while(first != last)
  121.                         insert(*first++);
  122.                }
  123.  
  124.  
  125.         index_proxy1 operator[](firstKeyT const& k)
  126.         {
  127.                 return index_proxy1(*this, k);
  128.         }
  129.         index_proxy2 operator[](secondKeyT const& k)
  130.         {
  131.                 return index_proxy2(*this, k);
  132.         }
  133.  
  134.         size_type count(firstKeyT const& k) const
  135.         {
  136.                 size_type rval = 0;
  137.                 iterator it = begin();
  138.                 for(;it != end();++it)
  139.                         if(it->first->first == k)
  140.                                 ++rval;
  141.  
  142.                 return rval;
  143.         }
  144.         size_type count(secondKeyT const& k) const
  145.         {
  146.                 size_type rval = 0;
  147.                 iterator it = begin();
  148.                 for(;it != end();++it)
  149.                         if(it->first->second == k)
  150.                                 ++rval;
  151.  
  152.                 return rval;
  153.         }
  154.  
  155.         size_type count(firstKeyT const& k1, secondKeyT const& k2) const
  156.         {
  157.                 return map_type::count(std::make_pair(k1, k2));
  158.         }
  159.  
  160.         std::pair<iterator, iterator> equal_range(firstKeyT const& k)
  161.         {
  162.                 return std::make_pair(lower_bound(k), upper_bound(k));
  163.         }
  164.  
  165.         std::pair<iterator, iterator> equal_range(secondKeyT const& k)
  166.         {
  167.                 return std::make_pair(lower_bound(k), upper_bound(k));
  168.         }
  169.  
  170.         std::pair<const_iterator, const_iterator> equal_range(firstKeyT const& k) const
  171.         {
  172.                 return std::make_pair(lower_bound(k), upper_bound(k));
  173.         }
  174.  
  175.         std::pair<const_iterator, const_iterator> equal_range(secondKeyT const& k) const
  176.         {
  177.                 return std::make_pair(lower_bound(k), upper_bound(k));
  178.         }
  179.  
  180.         iterator lower_bound(firstKeyT const& k)
  181.         {
  182.                 iterator rval = begin();
  183.                 for(;rval != end();++rval)
  184.                         if(k <= rval->first->first)
  185.                                 break;
  186.  
  187.                 return rval;
  188.         }
  189.  
  190.         const_iterator lower_bound(firstKeyT const& k) const
  191.         {
  192.                 const_iterator rval = begin();
  193.                 for(;rval != end();++rval)
  194.                         if(k <= rval->first->first)
  195.                                 break;
  196.  
  197.                 return rval;
  198.         }
  199.  
  200.         iterator lower_bound(secondKeyT const& k)
  201.         {
  202.                 iterator rval = begin();
  203.                 for(;rval != end();++rval)
  204.                         if(k <= rval->first->second)
  205.                                 break;
  206.  
  207.                 return rval;
  208.         }
  209.  
  210.         const_iterator lower_bound(secondKeyT const& k) const
  211.         {
  212.                 const_iterator rval = begin();
  213.                 for(;rval != end();++rval)
  214.                         if(k <= rval->first->second)
  215.                                 break;
  216.  
  217.                 return rval;
  218.         }
  219.  
  220.         iterator upper_bound(firstKeyT const& k)
  221.         {
  222.                 iterator rval = begin();
  223.                 for(;rval != end();++rval)
  224.                         if(k < rval->first->first)
  225.                                 break;
  226.  
  227.                 return rval;
  228.         }
  229.  
  230.         const_iterator upper_bound(firstKeyT const& k) const
  231.         {
  232.                 const_iterator rval = begin();
  233.                 for(;rval != end();++rval)
  234.                         if(k < rval->first->first)
  235.                                 break;
  236.  
  237.                 return rval;
  238.         }
  239.  
  240.         iterator upper_bound(secondKeyT const& k)
  241.         {
  242.                 iterator rval = begin();
  243.                 for(;rval != end();++rval)
  244.                         if(k < rval->first->second)
  245.                                 break;
  246.  
  247.                 return rval;
  248.         }
  249.  
  250.         const_iterator upper_bound(secondKeyT const& k) const
  251.         {
  252.                 const_iterator rval = begin();
  253.                 for(;rval != end();++rval)
  254.                         if(k < rval->first->second)
  255.                                 break;
  256.  
  257.                 return rval;
  258.         }
  259.  
  260.         void erase ( iterator position ){map_type::erase(position);}
  261.         void erase ( iterator first, iterator last ){map_type::erase(first, last);}
  262.  
  263.         size_type erase ( const firstKeyT& x )
  264.         {
  265.                 size_type rval = 0;
  266.                 for(iterator it = begin();it != end();++it)
  267.                         if(it->first->first == x)
  268.                         {
  269.                                 iterator toerase = it++;
  270.                                 erase(toerase);
  271.                                 ++rval;
  272.                         }
  273.                 return rval;
  274.         }
  275.         size_type erase ( const secondKeyT& x )
  276.         {
  277.                 size_type rval = 0;
  278.                 for(iterator it = begin();it != end();++it)
  279.                         if(it->first->second == x)
  280.                         {
  281.                                 iterator toerase = it++;
  282.                                 erase(toerase);
  283.                                 ++rval;
  284.                         }
  285.                 return rval;
  286.         }
  287.  
  288.         iterator find(firstKeyT const& k)
  289.         {
  290.                 iterator rval = begin();
  291.                 for(;rval != end();++rval)
  292.                         if(rval->first->first == k)
  293.                                 break;
  294.  
  295.                 return rval;
  296.         }
  297.  
  298.         const_iterator find(firstKeyT const& k) const
  299.         {
  300.                 const_iterator rval = begin();
  301.                 for(;rval != end();++rval)
  302.                         if(rval->first->first == k)
  303.                                 break;
  304.  
  305.                 return rval;
  306.         }
  307.  
  308.         iterator find(secondKeyT const& k)
  309.         {
  310.                 iterator rval = begin();
  311.                 for(;rval != end();++rval)
  312.                         if(rval->first->first == k)
  313.                                 break;
  314.  
  315.                 return rval;
  316.         }
  317.  
  318.         const_iterator find(secondKeyT const& k) const
  319.         {
  320.                 const_iterator rval = begin();
  321.                 for(;rval != end();++rval)
  322.                         if(rval->first->second == k)
  323.                                 break;
  324.  
  325.                 return rval;
  326.         }
  327. };
  328.  
  329. template<typename KeyTs,
  330.          typename mappedT,
  331.          typename CompareT,
  332.          typename AllocT>
  333. class trimap<KeyTs,
  334.              KeyTs,
  335.              mappedT,
  336.              CompareT,
  337.              AllocT> : public std::map<std::pair<KeyTs, KeyTs>,
  338.                                        mappedT,
  339.                                        CompareT,
  340.                                        AllocT>
  341. {
  342.         typedef std::map<std::pair<KeyTs, KeyTs>,
  343.                          mappedT,
  344.                          CompareT,
  345.                          AllocT> map_type;
  346.  
  347.         map_type::insert;
  348.  
  349.         typedef typename map_type::value_type value_type;
  350.         typedef typename map_type::mapped_type mapped_type;
  351.         typedef typename map_type::iterator iterator;
  352.         typedef typename map_type::const_iterator const_iterator;
  353.         typedef typename map_type::size_type size_type;
  354.         typedef typename map_type::key_compare key_compare;
  355.         typedef typename map_type::value_compare value_compare;
  356.         typedef typename map_type::allocator_type allocator_type;
  357.         typedef typename map_type::reference reference;
  358.         typedef typename map_type::const_reference const_reference;
  359.         typedef typename map_type::difference_type difference_type;
  360.         typedef typename map_type::pointer pointer;
  361.         typedef typename map_type::const_pointer const_pointer;
  362.         typedef typename map_type::reverse_iterator reverse_iterator;
  363.         typedef typename map_type::const_reverse_iterator const_reverse_iterator;
  364.  
  365.         struct index_proxy
  366.         {
  367.                 trimap& mMap;
  368.                 KeyTs const& mgivenKey;
  369.  
  370.                 index_proxy(trimap& m,
  371.                             KeyTs const& k):
  372.                         mMap(m),
  373.                         mgivenKey(k){}
  374.  
  375.                 mapped_type& operator[](KeyTs const& k)
  376.                 {
  377.                         const_iterator end_i = mMap.end();
  378.                         iterator iter  = mMap.find(std::make_pair(mgivenKey, k)),
  379.                                  iter2 = mMap.find(std::make_pair(k, mgivenKey));
  380.  
  381.                         if(iter != end_i)
  382.                                 return iter->second;
  383.                         else if(iter2 != end_i)
  384.                                 return iter2->second;
  385.                         else
  386.                                 return mMap.map_type::operator[](std::make_pair(mgivenKey, k));
  387.                 }
  388.         };
  389.  
  390. public:
  391.  
  392.         map_type::end;
  393.         map_type::begin;
  394.         map_type::clear;
  395.         map_type::find;
  396.         map_type::empty;
  397.         map_type::get_allocator;
  398.         map_type::key_comp;
  399.         map_type::max_size;
  400.         map_type::operator=;
  401.         map_type::rbegin;
  402.         map_type::rend;
  403.         map_type::size;
  404.         map_type::swap;
  405.         map_type::value_comp;
  406.  
  407.         trimap(trimap const& m):
  408.                 map_type(m){}
  409.  
  410.         explicit trimap ( CompareT const& comp = CompareT(),
  411.                           AllocT const& alloc = AllocT() ):
  412.                 map_type(comp, alloc) {}
  413.  
  414.         template <class InputIterator>
  415.                 trimap ( InputIterator first,
  416.                       InputIterator last,
  417.                       CompareT& comp = CompareT(),
  418.                       AllocT const& alloc = AllocT() ):
  419.                         map_type(comp, alloc)
  420.                 {
  421.                         insert(first, last);
  422.                 }
  423.  
  424.         std::pair<iterator,bool> insert ( const value_type& x )
  425.         {
  426.                 typename map_type::iterator t1 = find(x),
  427.                                             t2 = find(std::make_pair(x.second, x.first));
  428.                 if(t1 == end()
  429.                 && t2 == end())
  430.                         return map_type::insert(x);
  431.  
  432.                 return std::make_pair((t1 == end() ? t2 : t1), false);
  433.         }
  434.  
  435.         template <class InputIterator>
  436.                void insert ( InputIterator first, InputIterator last )
  437.                {
  438.                        while(first != last)
  439.                         insert(*first++);
  440.                }
  441.  
  442.         index_proxy operator[](KeyTs const& k)
  443.         {
  444.                 return index_proxy(*this, k);
  445.         }
  446.  
  447.         size_type count(KeyTs const& k) const
  448.         {
  449.                 size_type rval = 0;
  450.                 iterator it = begin();
  451.                 for(;it != end();++it)
  452.                 {
  453.                         bool const second_eq = it->first->second == k,
  454.                                    first_eq = it->first->first == k;
  455.  
  456.                         if(first_eq and second_eq)
  457.                                 rval += 2;
  458.  
  459.                         else if(first_eq or second_eq)
  460.                                 ++rval;
  461.                 }
  462.  
  463.                 return rval;
  464.         }
  465.  
  466.         size_type count(KeyTs const& k1, KeyTs const& k2) const
  467.         {
  468.                 return map_type::count(std::make_pair(k1, k2)) + map_type::count(std::make_pair(k2, k1));
  469.         }
  470.  
  471.         void erase ( iterator first, iterator last ){map_type::erase(first, last);}
  472.         void erase ( iterator position ){map_type::erase(position);}
  473.  
  474.         size_type erase ( const KeyTs& x )
  475.         {
  476.                 size_type rval = 0;
  477.                 for(iterator it = begin();it != end();++it)
  478.                         if(it->first->first == x
  479.                         or it->first->second == x)
  480.                         {
  481.                                 iterator toerase = it++;
  482.                                 erase(toerase);
  483.                                 ++rval;
  484.                         }
  485.                 return rval;
  486.         }
  487.  
  488.         iterator find(KeyTs const& k)
  489.         {
  490.                 iterator rval = begin();
  491.                 for(;rval != end();++rval)
  492.                         if(rval->first->first == k
  493.                         or rval->first->second == k)
  494.                                 break;
  495.  
  496.                 return rval;
  497.         }
  498.  
  499.         const_iterator find(KeyTs const& k) const
  500.         {
  501.                 const_iterator rval = begin();
  502.                 for(;rval != end();++rval)
  503.                         if(rval->first->first == k
  504.                         or rval->first->second == k)
  505.                                 break;
  506.  
  507.                 return rval;
  508.         }
  509. };
  510.  
  511.  
  512. int main()
  513. {
  514.  
  515. }
Success #stdin #stdout 0.01s 2676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N58aM
language:
C++ (gcc 8.3)
created:
12 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!