fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cassert>
  5.  
  6.     template <class KeyType, class ValueVectorType>
  7.     struct MyKeyWrapper { // all is public to save getters
  8.         KeyType k;
  9.         bool operator <(const MyKeyWrapper &other) const { return k < other.k; }
  10.     };
  11.  
  12.     template <class KeyType, class ValueVectorType>
  13.     struct ValueVectorSingleton { // all is public to save getters, but kv and vv should be only accessible by getters
  14.         static std::vector<MyKeyWrapper<KeyType, ValueVectorType> > *kv;
  15.         static ValueVectorType *vv;
  16.  
  17.         static void StartSort(std::vector<MyKeyWrapper<KeyType, ValueVectorType> > &_kv, ValueVectorType &_vv)
  18.         {
  19.             assert(!kv && !vv); // can't sort two at once (if multithreading)
  20.             assert(_kv.size() == _vv.size());
  21.             kv = &_kv, vv = &_vv; // not an attempt for atomic operation
  22.         }
  23.  
  24.         static void EndSort()
  25.         {
  26.             kv = 0, vv = 0;
  27.         }
  28.     };
  29.  
  30.     template <class KeyType, class ValueVectorType>
  31.     std::vector<MyKeyWrapper<KeyType, ValueVectorType> >
  32.         *ValueVectorSingleton<KeyType, ValueVectorType>::kv = 0;
  33.     template <class KeyType, class ValueVectorType>
  34.     ValueVectorType *ValueVectorSingleton<KeyType, ValueVectorType>::vv = 0;
  35.  
  36.     namespace std {
  37.  
  38.     template <class KeyType, class ValueVectorType>
  39.     void swap(MyKeyWrapper<KeyType, ValueVectorType> &a, MyKeyWrapper<KeyType, ValueVectorType> &b)
  40.     {
  41.         assert((ValueVectorSingleton<KeyType, ValueVectorType>::vv &&
  42.             ValueVectorSingleton<KeyType, ValueVectorType>::kv)); // if this triggers, someone forgot to call StartSort()
  43.         ValueVectorType &vv = *ValueVectorSingleton<KeyType, ValueVectorType>::vv;
  44.         std::vector<MyKeyWrapper<KeyType, ValueVectorType> > &kv =
  45.             *ValueVectorSingleton<KeyType, ValueVectorType>::kv;
  46.         size_t ai = &kv.front() - &a, bi = &kv.front() - &b; // get indices in key vector
  47.         std::swap(a, b); // swap keys
  48.         std::swap(vv[ai], vv[bi]); // and any associated values
  49.     }
  50.  
  51.     } // ~std
  52.  
  53. int main()
  54. {
  55.     size_t keys[] = {5, 2, 3, 1, 4};
  56.     char values[] = {'e', 'b', 'd', 'c', 'a'};
  57.  
  58.     std::vector<char> vv(values, values + 5); // fill by values
  59.     typedef MyKeyWrapper<size_t, std::vector<char> > KV;
  60.     assert(sizeof(KV) == sizeof(size_t)); // otherwise this will crash
  61.     std::vector<KV> kv((KV*)keys, (KV*)keys + 5); // fill by keys, casted to MyKeyWrapper
  62.  
  63.     ValueVectorSingleton<size_t, std::vector<char> >::StartSort(kv, vv);
  64.     std::sort(kv.begin(), kv.end());
  65.     ValueVectorSingleton<size_t, std::vector<char> >::EndSort();
  66.     // trick std::sort into using the custom std::swap which also swaps the other vectors
  67.  
  68.     for(int i = 0; i < 5; ++ i)
  69.         std::cout << kv[i].k << " ";
  70.     std::cout << std::endl;
  71.     for(int i = 0; i < 5; ++ i)
  72.         std::cout << vv[i] << " ";
  73.     std::cout << std::endl;
  74.     // could have used for_each and lambdas
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 
e b d c a
https://ideone.com/HriZ62
language:
C++ (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!