データの整列 in C++ DouKaku?

(x, y) の座標情報を以下の2種類の方法で整列する機能を実現してください。

(x, y) の辞書順(まず x で昇順に整列して、x が同じデータに対して y で昇順に整列する)
(0, 0) からの距離の昇順

データの表現方法はタプルなり構造体/オブジェクトなり各自で適当に選んで下さい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <cmath>

struct Pos
{
    double x;
    double y;
    Pos() : x(0), y(0) {}
    Pos(double x, double y) : x(x), y(y) {}
    double length() const { return std::sqrt(x*x + y*y); }
};

bool lexicalOrder(const Pos& lhs, const Pos& rhs)
{
    return (lhs.x  < rhs.x) ||((lhs.x == rhs.x) && (lhs.y < rhs.y));
}

bool lengthOrder(const Pos& lhs, const Pos& rhs)
{
    return lhs.length() < rhs.length();
}

std::ostream& operator << (std::ostream& out, const Pos& pos)
{
    return out << '(' << pos.x <<',' << pos.y << ')';
}

int main(int, char* [])
{
    std::vector<Pos> a;
    a.push_back(Pos(1, 1));
    a.push_back(Pos(3, 3));
    a.push_back(Pos(0, 0));
    a.push_back(Pos(0, 3));
    a.push_back(Pos(4, 0));

    std::sort(a.begin(), a.end(), lexicalOrder);
    std::copy(a.begin(), a.end(), std::ostream_iterator<Pos>(std::cout, " "));
    std::cout << "\n";
    // (0,0) (0,3) (1,1) (3,3) (4,0)

    std::sort(a.begin(), a.end(), lengthOrder);
    std::copy(a.begin(), a.end(), std::ostream_iterator<Pos>(std::cout, " "));
    std::cout << "\n";
    // (0,0) (1,1) (0,3) (4,0) (3,3)

    return 0;
}

座標の値が不変なら、長さをキャッシュして毎回計算しないようにしますよね。(蛇足か...)

% diff -u 5866.cpp.orig 5866.cpp
--- 5866.cpp.orig    2008-02-27 19:06:45.000000000 +0900
+++ 5866.cpp    2008-02-27 19:10:30.000000000 +0900
@@ -8,9 +8,8 @@
 {
     double x;
     double y;
-    Pos() : x(0), y(0) {}
-    Pos(double x, double y) : x(x), y(y) {}
-    double length() const { return std::sqrt(x*x + y*y); }
+    double length;
+    Pos(double x, double y) : x(x), y(y), length(std::sqrt(x*x + y*y)) {}
 };
 
 bool lexicalOrder(const Pos& lhs, const Pos& rhs)
@@ -20,7 +19,7 @@
 
 bool lengthOrder(const Pos& lhs, const Pos& rhs)
 {
-    return lhs.length() < rhs.length();
+    return lhs.length < rhs.length;
 }

DouKaku?

データの整列

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq