ソートと重複要素削除

ソートと重複要素削除について単純な例からまとめていきます。

目次

  1. 1次元ソート
  2. 1次元重複要素の削除
  3. 多次元ソート
  4. 3次元重複要素の削除
  5. タプルを用いたソートと重複要素の削除
  6. 多次元の重み付きソート

ソート(1次元)

1次元vectorをソートします。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
 vector<int> v = {3,3,1,1,5,5,2};
 sort(v.begin(), v.end());
 for (auto e : v) {
  cout << e << endl;
 }
}

実行結果.

1
1
2
3
3
5
5

重複要素の除去(1次元)

重複要素を削除したい場合、面倒ですが、
(1) sort (2) unique (3) eraseでごみデータを削除する
という3段回の操作をします。uniqueでは、後ろの方にごみデータが引っ付いてくるので、eraseする必要が生じてきます。 どこからがごみデータかという情報はuniqueの戻り値から判断します。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
 vector<int> v = {3,3,1,1,5,5,2};
 sort(v.begin(), v.end());
 auto it = unique(v.begin(),v.end());
 v.erase(it, v.end());
 for (auto e : v) {
  cout << e << endl;
 }
}

実行結果.

1
2
3
5

多次元ソート

最初に2次元ソートについて考えます。例として(2,1),(1,1),(3,2),(2,3) のソートについて考えます。 2次元なので、どのような順序でソートすべきかを指定する必要がありますが、次の例では第1成分の昇順にソートしています。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point {
public:
 int X;
 int Y;
 Point(int x,int y):X(x),Y(y){}
};
std::ostream& operator<<(std::ostream& ost, const Point& p)
{
 ost << "(" << p.X << "," << p.Y << ")";
 return ost;
}
int main() {
 vector<Point> v = {Point(2,1),Point(1,1),Point(3,2),Point(2,3)};
 sort(v.begin(), v.end(), [](Point p1,Point p2)-> bool {return p1.X < p2.X; });
 for (auto e : v) {
  cout << e << endl;
 }
}

実行結果.

(1,1)
(2,1)
(2,3)
(3,2)

シフト演算子「<<」をオーバーロードすることで、cout に自作クラスPoint変数を渡せるようにしています。 これについて解説しませんが、とにかく、このようにすると、Point型変数を(1,2)のように表示することができるようになると思ってください。

本題は、sort関数ですが、今回は順序づけの方法を指定するので、第3引数を利用し、ここでどちらが大きいかを指定する関数をいれます。 今回は第1成分の昇順になるようソートするので、上のようにX成分の大小関係だけを指定しています。

次は、3次元のPoint3dクラスを考えます。 単純にX成分についてソートして、それからY成分についてソートすると次のようになってしまいます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point3d {
public:
 int X;
 int Y;
 int Z;
 Point3d(int x, int y, int z) :X(x), Y(y), Z(z) {}
};
std::ostream& operator<<(std::ostream& ost, const Point3d& p)
{
 ost << "(" << p.X << "," << p.Y << "," << p.Z << ")";
 return ost;
}
int main() {
 vector<Point3d> v;
 for (int i = 0; i < 30; i++)
 {
  v.push_back(Point3d(i % 2, i % 3, i % 4));
 }
 sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {return p1.X < p2.X; });
 sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {return p1.Y < p2.Y; });
 for (auto e : v) {
  cout << e << endl;
 }
}

実行結果.

(0,0,0)
(0,0,2)
(0,0,0)
(0,0,2)
(0,0,0)
(1,0,3)
(1,0,1)
(1,0,3)
(1,0,1)
(1,0,3)
(0,1,0)
(0,1,2)
(0,1,0)
(0,1,2)
(0,1,0)
(1,1,1)
(1,1,3)
(1,1,1)
(1,1,3)
(1,1,1)
(0,2,2)
(0,2,0)
(0,2,2)
(0,2,0)
(0,2,2)
(1,2,1)
(1,2,3)
(1,2,1)
(1,2,3)
(1,2,1)

最初X成分の昇順でソートしたにもかかわらず、X成分の昇順になっていません。それは、Y成分をソートしたときに最初の順序が 崩れてしまうからです。X成分の順序は保ちつつ、X成分が一致するときのみ、Y成分を昇順にするには、次のようにします。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point3d {
public:
    int X;
    int Y;
    int Z;
    Point3d(int x, int y, int z) :X(x), Y(y), Z(z) {}
};
std::ostream& operator<<(std::ostream& ost, const Point3d& p)
{
    ost << "(" << p.X << "," << p.Y << "," << p.Z << ")";
    return ost;
}
int main() {
    vector<Point3d> v;
    for (int i = 0; i < 30; i++)
    {
        v.push_back(Point3d(i % 2, i % 3, i % 4));
    }
    sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {return p1.X < p2.X; });
    sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {
        if (p1.X == p2.X) {
            return p1.Y < p2.Y;
        }
        else {
            return false;
        }
        });
    for (auto e : v) {
        cout << e << endl;
    }
}

実行結果.

(0,0,0)
(0,0,2)
(0,0,0)
(0,0,2)
(0,0,0)
(0,1,0)
(0,1,2)
(0,1,0)
(0,1,2)
(0,1,0)
(0,2,2)
(0,2,0)
(0,2,2)
(0,2,0)
(0,2,2)
(1,0,3)
(1,0,1)
(1,0,3)
(1,0,1)
(1,0,3)
(1,1,1)
(1,1,3)
(1,1,1)
(1,1,3)
(1,1,1)
(1,2,1)
(1,2,3)
(1,2,1)
(1,2,3)
(1,2,1)

sort関数の第3引数で指定するbool型の比較関数は、falseのとき何もしないということなので、 2回目のsort関数使用時に、X成分が等しいとき以外をfalseにして、X成分に関する順序を保つようにします。 Z成分について、最後にソートするには次のようにします。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point3d {
public:
 int X;
 int Y;
 int Z;
 Point3d(int x, int y, int z) :X(x), Y(y), Z(z) {}
};
std::ostream& operator<<(std::ostream& ost, const Point3d& p)
{
 ost << "(" << p.X << "," << p.Y << "," << p.Z << ")";
 return ost;
}
int main() {
 vector<Point3d> v;
 for (int i = 0; i < 30; i++)
 {
  v.push_back(Point3d(i % 2, i % 3, i % 4));
 }
 sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {return p1.X < p2.X; });
 sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {
  if (p1.X == p2.X) {
   return p1.Y < p2.Y;
  }
  else {
   return false;
  }
  });
 sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {
  if (p1.X == p2.X && p1.Y == p2.Y) {
   return p1.Z < p2.Z;
  }
  else {
   return false;
  }
  });
 for (auto e : v) {
  cout << e << endl;
 }
}

実行結果.

(0,0,0)
(0,0,0)
(0,0,0)
(0,0,2)
(0,0,2)
(0,1,0)
(0,1,0)
(0,1,0)
(0,1,2)
(0,1,2)
(0,2,0)
(0,2,0)
(0,2,2)
(0,2,2)
(0,2,2)
(1,0,1)
(1,0,1)
(1,0,3)
(1,0,3)
(1,0,3)
(1,1,1)
(1,1,1)
(1,1,1)
(1,1,3)
(1,1,3)
(1,2,1)
(1,2,1)
(1,2,1)
(1,2,3)
(1,2,3)

x成分,y成分,z成分という優先度で昇順に並べ替えると上の結果になります。

重複要素の削除(3次元)

上の例で、重複要素の削除を行います。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point3d {
public:
    int X;
    int Y;
    int Z;
    Point3d(int x, int y, int z) :X(x), Y(y), Z(z) {}
};
std::ostream& operator<<(std::ostream& ost, const Point3d& p)
{
    ost << "(" << p.X << "," << p.Y << "," << p.Z << ")";
    return ost;
}
int main() {
    vector<Point3d> v;
    for (int i = 0; i < 30; i++)
    {
        v.push_back(Point3d(i % 2, i % 3, i % 4));
    }
    sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {return p1.X < p2.X; });
    sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {
        if (p1.X == p2.X) {
            return p1.Y < p2.Y;
        }
        else {
            return false;
        }
        });
    sort(v.begin(), v.end(), [](Point3d p1, Point3d p2)-> bool {
        if (p1.X == p2.X && p1.Y == p2.Y) {
            return p1.Z < p2.Z;
        }
        else {
            return false;
        }
        });
    auto it = unique(v.begin(), v.end(), [](Point3d p1, Point3d p2)->bool {return p1.X == p2.X && p1.Y==p2.Y && p1.Z==p2.Z; });
    v.erase(it, v.end());
    for (auto e : v) {
        cout << e << endl;
    }
}

実行結果.

(0,0,0)
(0,0,2)
(0,1,0)
(0,1,2)
(0,2,0)
(0,2,2)
(1,0,1)
(1,0,3)
(1,1,1)
(1,1,3)
(1,2,1)
(1,2,3)

基本は1次元の場合と同じですが、異なるのは、何が等しいかを指定する必要が生じる点です。 ここでは、unique関数の第3引数で、Point3dのデータが等しいとは、「各成分がすべて等しい」ことだと定義しています。

tupleを用いる方法

tupleは上のような処理を自動的に行ってくれます。

#include <tuple>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Point3d {
public:
 int X;
 int Y;
 int Z;
 Point3d(int x, int y, int z) :X(x), Y(y), Z(z) {}
};
std::ostream& operator<<(std::ostream& ost, const Point3d& p)
{
 ost << "(" << p.X << "," << p.Y << "," << p.Z << ")";
 return ost;
}
int main() {
 vector<tuple<int, int, int>> tv;
 cout << "入力データ" << endl;
 for (int i = 0; i < 30; i++)
 {
  tv.push_back(make_tuple(i % 2, i % 3, i % 4));
 }
 for (auto e : tv) {
  cout << get<0>(e) << "," << get<1>(e) << "," << get<2>(e) << endl;
 }
 cout << endl;
 cout << "ソートして、重複要素を削除したデータ" << endl;
 sort(tv.begin(), tv.end(), less<tuple<int, int , int>>());
 auto it = unique(tv.begin(), tv.end());
 tv.erase(it, tv.end());
 for (auto e : tv) {
  cout << get<0>(e) << "," << get<1>(e) << "," << get<2>(e) << endl;
 }
}

実行結果.

入力データ
0,0,0
1,1,1
0,2,2
1,0,3
0,1,0
1,2,1
0,0,2
1,1,3
0,2,0
1,0,1
0,1,2
1,2,3
0,0,0
1,1,1
0,2,2
1,0,3
0,1,0
1,2,1
0,0,2
1,1,3
0,2,0
1,0,1
0,1,2
1,2,3
0,0,0
1,1,1
0,2,2
1,0,3
0,1,0
1,2,1

ソートして、重複要素を削除したデータ
0,0,0
0,0,2
0,1,0
0,1,2
0,2,0
0,2,2
1,0,1
1,0,3
1,1,1
1,1,3
1,2,1
1,2,3

tupleの昇順ソートは

sort(tv.begin(), tv.end(), less<tuple<int, int , int>>());

の部分になります。降順の場合は「less」のかわりに「greater」を指定します。

多次元の重み付きソート

各次元ごとに優先順位をつけてソートをくりかえすのは面倒です。 ここでは、優先順位ごとに重みを付けてソートする方法について考えます。

例として、X年Y月Z日という3次元のデータを日付順に昇順にソートします。 最大値について調べると、

Zの最大値 31
Yの最大値 12

となります。したがって

X*31*12+Y*31+Z

というように重みをつけた和を基準にしてソートすれば、優先順位としてX,Y,Zの順にソートできます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MyDate {
public:
 int Year;
 int Month;
 int Day;
 MyDate(int year, int month, int day) {
  Year = year;
  Month = month;
  Day = day;
 };
 int getValue() const {
  return Year * 12 * 31 + Month * 31 + Day;
 }
};


ostream& operator <<(ostream& ost, const MyDate& p) {
 ost << p.Year << "年" << p.Month << "月" << p.Day << "日";
 return ost;
}

int main() {

 vector<MyDate> dates = { MyDate(2020,1,10), MyDate(2020,3,10), MyDate(2020,2,3), 
      MyDate(2021,3,11), MyDate(2022,12,12), MyDate(2020,1,1),
      MyDate(2019,12,31), MyDate(2019,11,1), MyDate(2019,10,31),
      MyDate(2020,2,2) };
 cout << "ソート前のデータ" << endl;
 for (auto d : dates) {
  cout << d << endl;
 }
 sort(dates.begin(), dates.end(), [](const MyDate& d1, const MyDate& d2)-> bool {return d1.getValue() < d2.getValue(); });
 cout << "ソート後のデータ" << endl;

 for (auto d : dates) {
  cout << d << endl;
 }
}

実行結果.

ソート前のデータ
2020年1月10日
2020年3月10日
2020年2月3日
2021年3月11日
2022年12月12日
2020年1月1日
2019年12月31日
2019年11月1日
2019年10月31日
2020年2月2日
ソート後のデータ
2019年10月31日
2019年11月1日
2019年12月31日
2020年1月1日
2020年1月10日
2020年2月2日
2020年2月3日
2020年3月10日
2021年3月11日
2022年12月12日

getValue関数が、重みを付けた日付の和を計算している部分になります。この値を昇順に並べれば 自動的に日付が昇順に並びます。