範囲のソート (C++03 – C++20)

C++
2022.08.09

概要

範囲のソートやソートされているかの判定を行います。
範囲の指定方法は、
・std::xxx(C++03): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲を直接指定します。
条件判定や、値生成に関数を指定するものがあります。※
std::ranges::xxx(C++20): 射影(projection)関数を指定できるものがあります。※
出力先は、既存の範囲に上書きするものと、別途出力先のイテレーターを指定するものがあります。※
※詳細についてはこちらを参照してください。
https://mappuri.com/program/cpp20-algorithm/

ソート

sort

範囲をソートします。
範囲はランダムに読み書き可能である必要があります。

stable_sort

範囲を安定ソートします。
範囲はランダムアクセスが必要です。
安定ソートでは、同じ値の要素の順序が維持されます。

この例では数値のメンバー変数で比較するので、{3, “a”} と {3, “c”} は同じ値と判断されます。stable_sort ではソート前の順序 {3, “a”}, {3, “c”} がソート後も維持されますが、sort では維持されるとは限りません。

sort, stable_sort のサンプル(C++03)

#include <iostream>

/** r 内の [first, last) の範囲と値を出力 範囲:[0, 9) 値:1 2 3 4 5 4 5 6 6 */
template<class T, class U, class V>
static void output(T&& r, U&& first, V&& last) {
	std::cout << "範囲:[" << std::distance(std::begin(r), first) << ", " << std::distance(std::begin(r), last) << ")";
	std::cout << " 値:";
	std::string delim = "";
	for (auto i = first; i != last; ++i, delim = ", ") {
		std::cout << delim << *i;
	}
	std::cout << std::endl;
}

/** r 内の it の位置と値を出力 位置:2 値:3 */
template<class T, class U>
static void output(T&& r, U&& it) {
	std::cout << "位置:" << std::distance(std::begin(r), it);
	std::cout << " 値:";
	if (it == std::end(r) || &*it == nullptr) {
		std::cout << "end";
	} else {
		std::cout << *it;
	}
	std::cout << std::endl;
}

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
	{
		// 範囲をソートします。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::sort(r.begin(), r.end());
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
	}
	{
		// 範囲をソートします。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::sort(r.begin(), r.end(),
			[](int a, int b) { return a > b; }); // 逆順で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 2, 1
	}
	{
		// 範囲を安定ソートします。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::stable_sort(r.begin(), r.end());
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
	}
	{
		// 範囲を安定ソートします。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::stable_sort(r.begin(), r.end(),
			[](int a, int b) { return a > b; }); // 逆順で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 2, 1
	}
	return 0;
}

sort, stable_sort のサンプル(C++20 range)

#include <algorithm>
#include <iostream>
#include <vector>

struct S1 {
	int intval;
	std::string strval;
	friend std::ostream& operator<<(std::ostream& os, const S1& s1) {
		return os << s1.intval << "," << s1.strval;
	}
};

int main(int argc, char* argv[]) {
	{
		// 範囲をソートします。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::sort(r);
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
	}
	{
		// 範囲をソートします。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::sort(r,
			[](int a, int b) { return a > b; }); // 逆順で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 2, 1
	}
	{
		// 範囲をソートします。(C++20)
		std::vector<S1> r = { {3, "a"}, {2, "b"}, {3, "c"}, {1, "d"}, {4, "e"} };
		std::ranges::sort(r, {}, &S1::intval); // 特定メンバー変数で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1,d, 2,b, 3,a, 3,c, 4,e
	}
	{
		// 範囲を安定ソートします。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::stable_sort(r);
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 4, 5
	}
	{
		// 範囲を安定ソートします。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::stable_sort(r,
			[](int a, int b) { return a > b; }); // 逆順で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:5, 4, 3, 2, 1
	}
	{
		// 範囲を安定ソートします。(C++20)
		std::vector<S1> r = { {3, "a"}, {2, "b"}, {3, "c"}, {1, "d"}, {4, "e"} };
		std::ranges::stable_sort(r, {}, &S1::intval); // 特定メンバー変数で比較
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1,d, 2,b, 3,a, 3,c, 4,e
	}
	return 0;
}

部分ソート

partial_sort

範囲全体をソートした上位が指定位置までの範囲に入るようにソートします。
範囲はランダムアクセスが必要です。

partial_sort_copy

範囲全体をソートした上位が指定位置までの範囲に入るようにソートして出力します。
範囲はランダムアクセスが必要です。

nth_element

範囲の指定位置をソート後の要素にし、それより小さい要素を前に集めます。
範囲はランダムアクセスが必要です。
指定位置以外の要素の順序は不定になります。

partial_sort, partial_sort_copy, nth_element のサンプル(C++03)

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
	{
		// 範囲全体をソートした上位が指定位置までの範囲に入るようにソートします。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::partial_sort(r.begin(), r.begin() + 3, r.end());
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 5, 4
	}
	{
		// 範囲全体をソートした上位が指定位置までの範囲に入るようにソートして出力します。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::vector<int> o(3);
		std::partial_sort_copy(r.begin(), r.end(), o.begin(), o.end());
		output(o, o.begin(), o.end()); // 範囲:[0, 3) 値:1, 2, 3
	}
	{
		// 範囲の指定位置をソート後の要素にし、それより小さい要素を前に集めます。(C++03)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::nth_element(r.begin(), r.begin() + 3, r.end());
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:2, 1, 3, 4, 5
	}
	return 0;
}

partial_sort, partial_sort_copy, nth_element のサンプル(C++20 range)

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
	{
		// 範囲全体をソートした上位が指定位置までの範囲に入るようにソートします。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::partial_sort(r, r.begin() + 3);
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:1, 2, 3, 5, 4
	}
	{
		// 範囲全体をソートした上位が指定位置までの範囲に入るようにソートして出力します。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::vector<int> o(3);
		std::ranges::partial_sort_copy(r, o);
		output(o, o.begin(), o.end()); // 範囲:[0, 3) 値:1, 2, 3
	}
	{
		// 範囲の指定位置をソート後の要素にし、それより小さい要素を前に集めます。(C++20)
		std::vector<int> r = { 3, 2, 5, 1, 4 };
		std::ranges::nth_element(r, r.begin() + 3);
		output(r, r.begin(), r.end()); // 範囲:[0, 5) 値:2, 1, 3, 4, 5
	}
	return 0;
}

ソート判定

is_sorted

範囲がソート済みか判定します。

is_sorted_until

範囲のソートされていない位置を取得します。

is_sorted, is_sorted_until のサンプル(C++11)

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
	{
		// 範囲がソート済みか判定します。(C++11)
		std::vector<int> r = { 2, 3, 5, 1, 4 };
		bool is_sorted = std::is_sorted(r.begin(), r.end());
		std::cout << "is_sorted = " << std::boolalpha << is_sorted << std::endl; // is_sorted = false
	}
	{
		// 範囲のソートされていない位置を取得します。(C++11)
		std::vector<int> r = { 2, 3, 5, 1, 4 };
		auto is_sorted_until = std::is_sorted_until(r.begin(), r.end());
		output(r, is_sorted_until); // 位置:3 値:1
	}
	return 0;
}

is_sorted, is_sorted_until のサンプル(C++20 range)

#include <algorithm>
#include <iostream>
#include <vector>

int main(int argc, char* argv[]) {
	{
		// 範囲がソート済みか判定します。(C++11)
		std::vector<int> r = { 2, 3, 5, 1, 4 };
		bool is_sorted = std::ranges::is_sorted(r);
		std::cout << "is_sorted = " << std::boolalpha << is_sorted << std::endl; // is_sorted = false
	}
	{
		// 範囲のソートされていない位置を取得します。(C++11)
		std::vector<int> r = { 2, 3, 5, 1, 4 };
		auto is_sorted_until = std::ranges::is_sorted_until(r);
		output(r, is_sorted_until); // 位置:3 値:1
	}
	return 0;
}

コメント

タイトルとURLをコピーしました