fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6.     template <class V0, class V1>
  7.     class CRefPair { // overrides copy semantics of std::pair
  8.     protected:
  9.         V0 &m_v0;
  10.         V1 &m_v1;
  11.  
  12.     public:
  13.         CRefPair(V0 &v0, V1 &v1)
  14.             :m_v0(v0), m_v1(v1)
  15.         {}
  16.  
  17.         void swap(CRefPair &other)
  18.         {
  19.             std::swap(m_v0, other.m_v0);
  20.             std::swap(m_v1, other.m_v1);
  21.         }
  22.  
  23.         operator std::pair<V0, V1>() const // both g++ and msvc sort requires this (to get a pivot)
  24.         {
  25.             return std::pair<V0, V1>(m_v0, m_v1);
  26.         }
  27.  
  28.         CRefPair &operator =(std::pair<V0, V1> v) // both g++ and msvc sort requires this (for insertion sort)
  29.         {
  30.             m_v0 = v.first;
  31.             m_v1 = v.second;
  32.             return *this;
  33.         }
  34.  
  35.         CRefPair &operator =(const CRefPair &other) // required by g++ (for _GLIBCXX_MOVE)
  36.         {
  37.             m_v0 = other.m_v0;
  38.             m_v1 = other.m_v1;
  39.             return *this;
  40.         }
  41.     };
  42.  
  43.     template <class V0, class V1>
  44.     inline bool operator <(std::pair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
  45.     {
  46.         return a < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
  47.     }
  48.  
  49.     template <class V0, class V1>
  50.     inline bool operator <(CRefPair<V0, V1> a, std::pair<V0, V1> b) // required by both g++ and msvc
  51.     {
  52.         return std::pair<V0, V1>(a) < b; // default pairwise lexicographical comparison
  53.     }
  54.  
  55.     template <class V0, class V1>
  56.     inline bool operator <(CRefPair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
  57.     {
  58.         return std::pair<V0, V1>(a) < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
  59.     }
  60.  
  61.     namespace std {
  62.  
  63.     template <class V0, class V1>
  64.     inline void swap(CRefPair<V0, V1> &a, CRefPair<V0, V1> &b)
  65.     {
  66.         a.swap(b);
  67.     }
  68.  
  69.     } // ~std
  70.  
  71.     template <class It0, class It1>
  72.     class CPairIterator : public std::random_access_iterator_tag {
  73.     public:
  74.         typedef typename std::iterator_traits<It0>::value_type value_type0;
  75.         typedef typename std::iterator_traits<It1>::value_type value_type1;
  76.         typedef std::pair<value_type0, value_type1> value_type;
  77.         typedef typename std::iterator_traits<It0>::difference_type difference_type;
  78.         typedef /*typename std::iterator_traits<It0>::distance_type*/difference_type distance_type; // no distance_type in g++, only in msvc
  79.         typedef typename std::iterator_traits<It0>::iterator_category iterator_category;
  80.         typedef CRefPair<value_type0, value_type1> reference;
  81.         typedef reference *pointer; // not so sure about this, probably can't be implemented in a meaningful way, won't be able to overload ->
  82.         // keep the iterator traits happy
  83.  
  84.     protected:
  85.         It0 m_it0;
  86.         It1 m_it1;
  87.  
  88.     public:
  89.         CPairIterator(const CPairIterator &r_other)
  90.             :m_it0(r_other.m_it0), m_it1(r_other.m_it1)
  91.         {}
  92.  
  93.         CPairIterator(It0 it0 = It0(), It1 it1 = It1())
  94.             :m_it0(it0), m_it1(it1)
  95.         {}
  96.  
  97.         reference operator *()
  98.         {
  99.             return reference(*m_it0, *m_it1);
  100.         }
  101.  
  102.         value_type operator *() const
  103.         {
  104.             return value_type(*m_it0, *m_it1);
  105.         }
  106.  
  107.         difference_type operator -(const CPairIterator &other) const
  108.         {
  109.             assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
  110.             // the iterators always need to have the same position
  111.             // (incomplete check but the best we can do without having also begin / end in either vector)
  112.  
  113.             return m_it0 - other.m_it0;
  114.         }
  115.  
  116.         bool operator ==(const CPairIterator &other) const
  117.         {
  118.             assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
  119.             return m_it0 == other.m_it0;
  120.         }
  121.  
  122.         bool operator !=(const CPairIterator &other) const
  123.         {
  124.             return !(*this == other);
  125.         }
  126.  
  127.         bool operator <(const CPairIterator &other) const
  128.         {
  129.             assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
  130.             return m_it0 < other.m_it0;
  131.         }
  132.  
  133.         bool operator >=(const CPairIterator &other) const
  134.         {
  135.             return !(*this < other);
  136.         }
  137.  
  138.         bool operator <=(const CPairIterator &other) const
  139.         {
  140.             return !(other < *this);
  141.         }
  142.  
  143.         bool operator >(const CPairIterator &other) const
  144.         {
  145.             return other < *this;
  146.         }
  147.  
  148.         CPairIterator operator +(distance_type d) const
  149.         {
  150.             return CPairIterator(m_it0 + d, m_it1 + d);
  151.         }
  152.  
  153.         CPairIterator operator -(distance_type d) const
  154.         {
  155.             return *this + -d;
  156.         }
  157.  
  158.         CPairIterator &operator +=(distance_type d)
  159.         {
  160.             return *this = *this + d;
  161.         }
  162.  
  163.         CPairIterator &operator -=(distance_type d)
  164.         {
  165.             return *this = *this + -d;
  166.         }
  167.  
  168.         CPairIterator &operator ++()
  169.         {
  170.             return *this += 1;
  171.         }
  172.  
  173.         CPairIterator &operator --()
  174.         {
  175.             return *this += -1;
  176.         }
  177.  
  178.         CPairIterator operator ++(int) // msvc sort actually needs this, g++ does not
  179.         {
  180.             CPairIterator old = *this;
  181.             ++ (*this);
  182.             return old;
  183.         }
  184.  
  185.         CPairIterator operator --(int)
  186.         {
  187.             CPairIterator old = *this;
  188.             -- (*this);
  189.             return old;
  190.         }
  191.     };
  192.  
  193.     template <class It0, class It1>
  194.     inline CPairIterator<It0, It1> make_pair_iterator(It0 it0, It1 it1)
  195.     {
  196.         return CPairIterator<It0, It1>(it0, it1);
  197.     }
  198.  
  199.     struct CompareByFirst {
  200.     	bool operator ()(std::pair<size_t, char> a, std::pair<size_t, char> b) const
  201.     	{
  202.             return a.first < b.first;
  203.     	}
  204.     };
  205.  
  206. int main()
  207. {
  208.     size_t keys[] = {5, 2, 3, 1, 4};
  209.     char values[] = {'e', 'b', 'd', 'c', 'a'};
  210.  
  211.     std::vector<char> vv(values, values + 5); // fill by values
  212.     std::vector<size_t> kv(keys, keys + 5); // fill by keys
  213.  
  214.     std::sort(make_pair_iterator(kv.begin(), vv.begin()),
  215.         make_pair_iterator(kv.end(), vv.end()), CompareByFirst());
  216.     // nice
  217.  
  218.     for(int i = 0; i < 5; ++ i)
  219.         std::cout << kv[i] << " ";
  220.     std::cout << std::endl;
  221.     for(int i = 0; i < 5; ++ i)
  222.         std::cout << vv[i] << " ";
  223.     std::cout << std::endl;
  224.     // could have used for_each and lambdas
  225.  
  226. 	return 0;
  227. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 3 4 5 
c b d a e
https://ideone.com/PVrHtI
language:
C++ (gcc 8.3)
created:
9 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!