fork download 
  1. #include <array>
  2. #include <iostream>
  3. #include <queue>
  4. #include <vector>
  5.  
  6. template <std::size_t N, typename It, typename Queue>
  7. std::array<It, N> asArray(Queue& queue, It emptyValue)
  8. {
  9.     std::array<It, N> res;
  10.     for (auto& e : res) {
  11.         if (queue.empty()) {
  12.             e = emptyValue;
  13.         } else {
  14.             e = queue.top();
  15.             queue.pop();
  16.         }
  17.     }
  18.     return res;
  19. }
  20.  
  21. template <std::size_t N, typename It, typename ValueGetter>
  22. std::array<It, N>
  23. MinNElementsBy(It begin, It end, ValueGetter valueGetter)
  24. {
  25.     auto myComp = [&](const It& lhs, const It& rhs){ return valueGetter(*lhs) <  valueGetter(*rhs); };
  26.     std::priority_queue<It, std::vector<It>, decltype(myComp)> queue(myComp);
  27.  
  28.     for (auto it = begin; it != end; ++it) {
  29.         queue.push(it);
  30.         if (N < queue.size()) {
  31.             queue.pop();
  32.         }
  33.     }
  34.     return asArray<N>(queue, end);
  35. }
  36.  
  37. struct Point {
  38.     double x; double y;
  39. };
  40.  
  41. std::ostream& operator << (std::ostream& os, const Point& p)
  42. {
  43.     return os << "{" << p.x << ", " << p.y << "}";
  44. }
  45.  
  46. double square(double x) { return x * x; }
  47.  
  48. double SqrDistance(const Point& p1, const Point& p2)
  49. {
  50.     return square(p1.x - p2.x) + square(p1.y - p2.y);
  51. }
  52.  
  53. int main ()
  54. {
  55.     const std::vector<Point> points = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
  56.     const Point ref{42, 1};
  57.  
  58.     auto its = MinNElementsBy<2>(points.begin(), points.end(), [&](const Point& p) { return SqrDistance(ref, p); });
  59.  
  60.     for (auto it : its) {
  61.         std::cout << *it << " ";   
  62.     }
  63. }
  64.  
Success #stdin #stdout 0s 3464KB
comments ()
stdin 
Standard input is empty
stdout 
{0, 1} {1, 0}
https://ideone.com/CrOkgJ
language:
C++14 (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!