fork download
copy 
  1. #include <algorithm>
  2.  
  3. #include <iterator>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. template <
  8.       typename MultiPassIOIterator
  9.     , typename BinaryPredicate
  10.     , typename BinaryMergeTransform
  11. >
  12. MultiPassIOIterator conditionalInPlaceMerge(
  13.       MultiPassIOIterator cur
  14.     , MultiPassIOIterator end
  15.     , BinaryPredicate predicate
  16.     , BinaryMergeTransform merge)
  17. {
  18.     MultiPassIOIterator next(cur + 1);
  19.     while ((cur != end) && (next != end))
  20.     {
  21.         if (predicate(*cur, *next))
  22.         {
  23.             *cur = merge(*cur, *next);
  24.             move(next + 1, end, next);
  25.             --end;
  26.         }
  27.         else
  28.         {
  29.             ++cur;
  30.             ++next;
  31.         }
  32.     }
  33.  
  34.     return (cur != end) ? next : end;
  35. }
  36.  
  37. // our aggregate structure
  38. struct Aggregate
  39. {
  40.     int key_;
  41.     unsigned count_;
  42. };
  43. ostream& operator<<(ostream &os, Aggregate a)
  44. {
  45.     os << "{ " << a.key_ << ", " << a.count_ << " }";
  46.     return os;
  47. }
  48. int main() {
  49.     Aggregate aggregates[] = {
  50.         { 12, 35 },
  51.         { 57, 503 },
  52.         { 83, 5675 },
  53.         { 12, 123 },
  54.         { 11, 578 }
  55.     };
  56.     Aggregate *end(aggregates + (sizeof(aggregates) / sizeof(aggregates[0])));
  57.     // first sort
  58.     sort(
  59.           aggregates, end
  60.         , [](Aggregate const &lhs, Aggregate const &rhs){ return lhs.key_ < rhs.key_; });
  61.     // now condense
  62.     end = conditionalInPlaceMerge(
  63.           aggregates
  64.         , end
  65.         , [](Aggregate const &lhs, Aggregate const &rhs){ return lhs.key_ == rhs.key_; }
  66.         , [](Aggregate lhs, Aggregate const &rhs){ lhs.count_ += rhs.count_; return lhs; }
  67.         );
  68.  
  69.     ostream_iterator< Aggregate > out_it(cout, "\n");
  70.     copy(aggregates, end, out_it);
  71.     return 0;
  72. }
Success #stdin #stdout 0s 2896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
{ 11, 578 }
{ 12, 158 }
{ 57, 503 }
{ 83, 5675 }
https://ideone.com/jsLf0h
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

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!