vectorによるx-y座標のソート

Question

前提・実現したいこと

メンバ変数cx,cy,px,pyをもつ構造体C2Pをvectorコンテナc2pListに格納しています。構造体C2Pをメンバ変数pxとpyの大きさに応じてソートしたいと考えています。
表１のようにランダムに並んだC2Pを、表２のようにpyが昇順になるようにC2Pをソートしてからpyが同じ場合はpxが昇順になるようにC2Pをソートするといったイメージです。
下記のソースコードではC2Pの数が増えると動作が重くなってしまいます。for文を使わない単純な方法でソートしたいと考えています。アドバイスをお願いいたします。

<表１>
|cx|cy|px|py|
|:--|:--:|--:|
111|169|6|2
34|90|7|2
61|122|0|0
139|40|3|1
257|169|3|2
|8|113|0|0
252|47|2|2
55|8|5|2
148|190|1|0
113|194|0|1
190|60|7|2
1|97|1|1

<表２>
|cx|cy|px|py|
|:--|:--:|--:|
|8|113|0|0
61|122|0|0
148|190|1|0
113|194|0|1
1|97|1|1
139|40|3|1
252|47|2|2
257|169|3|2
55|8|5|2
111|169|6|2
34|90|7|2
190|60|7|2

発生している問題・エラーメッセージ

下記のソースコードでは無駄が多いのか座標数が多くなるとプログラムがうまく動作しません。そのため、もう少し単純な方法で実現したいと考えております。for文を使わずに実現することは可能でしょうか。

該当のソースコード

#include <vector>
#include <algorithm>
#include <random>
using namespace std;

struct C2P
{
	int cx;
	int cy;
	int px;
	int py;

	C2P(int camera_x, int camera_y, int proj_x, int proj_y)
	{
		cx = camera_x;
		cy = camera_y;
		px = proj_x;
		py = proj_y;
	}
};
//---最後尾から探索するfind_if-------
template<class Iterator,class Predicate>
Iterator find_last_if(Iterator begin, Iterator end, Predicate pred)
{
	const auto rbegin = make_reverse_iterator(end);
	const auto rend = make_reverse_iterator(begin);
	auto found = find_if(rbegin, rend, pred);

	return (found != rend) ? (++found).base() : end;
}

int main()
{
	//データの用意
	vector<C2P> c2pList;
        

	for (int i = 0;i < 2000;i++)
	{
		for (int j = 0;j < 1000;j++)
		{
			c2pList.push_back(C2P(j, i, rand() % 100, rand() % 100)
		}
	}

	//C2Pの最大値と最小値を調べる
	auto max_px = max_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.px < b.px;});
	auto min_px = min_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.px < b.px;});
	auto max_py = max_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.py < b.py;});
	auto min_py = min_element(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) {return a.py < b.py;});

	int max_px_num = max_px->px;
	int min_px_num = min_px->px;
	int max_py_num = max_py->py;
	int min_py_num = min_py->py;

	//今回の質問の本題(ソートを行う)
	sort(c2pList.begin(), c2pList.end(), [](C2P& a, C2P& b) { return a.py < b.py; });//pyを使いC2Pをソート
	for (int i = min_py_num;i <= max_py_num;i++)//pxをソート
	{
		auto first_itr = find_if(c2pList.begin(), c2pList.end(), [&i](C2P& a) {return a.py == i;});//先頭のイテレータを取得
		auto last_itr = find_last_if(c2pList.begin(), c2pList.end(), [&i](C2P& a) { return a.py == i; });//最後尾のイテレーターを取得

		if (first_itr != c2pList.end() && last_itr != c2pList.end()&&first_itr!=last_itr)
		{
			sort(first_itr, last_itr + 1, [](C2P& a, C2P& b) { return a.px < b.px; });
		}

     }

       return 0;		
		
	
		
}

試したこと

補足情報（FW/ツールのバージョンなど）

Answer 1

#include <vector>
#include <algorithm>
#include <random>
#include <utility>
#include <iostream>
#include <iomanip>

struct C2P {
    int cx;
    int cy;
    int px;
    int py;

    C2P(int camera_x, int camera_y, int proj_x, int proj_y) {
        cx = camera_x;
        cy = camera_y;
        px = proj_x;
        py = proj_y;
    }
};

int main() {
    //データの用意
    std::vector<C2P> c2pList;

    std::mt19937 gen{std::random_device{}()};
    std::uniform_int_distribution<int> dist(0,99);
    
    for ( int i = 0;i < 2000; i++) {
        for ( int j = 0;j < 1000; j++) {
            c2pList.push_back(C2P(j, i, dist(gen), dist(gen)));
        }
    }

    //今回の質問の本題(ソートを行う)
    std::sort(c2pList.begin(), c2pList.end(), 
              [](C2P& a, C2P& b) { 
                  return std::make_pair(a.py, a.px) < std::make_pair(b.py, b.px);
              });

    for ( const auto& item : c2pList ) {
        std::cout << std::setw(5) << item.cx 
                  << std::setw(5) << item.cy 
                  << std::setw(5) << item.px 
                  << std::setw(5) << item.py 
                  << std::endl;
    }

}

Comments

[k.s.t]

回答いただきありがとうございました。
無事解決しました。

[episteme]

僕のがbest-answer? なんで?

[k.s.t]

初心者なものでつける回答を間違てしまいました。
申し訳ありません。
epistemeさんの回答も大変参考になりました。
回答いただきありがとうございました。

Answer 2

for文を使わない単純な方法でソートしたいと考えています。アドバイスをお願いいたします。

下記ソースコードのmain関数内で使用しているstd::sortの
第三引数のラムダ式内のようにpyの比較なのかpxの比較なのか
if文や三項演算子で分岐してやればコードを簡略化できます。

C2Pの数が増えると動作が重くなってしまいます

vectorのreserveメソッドを使わずpush_backで
何度もメモリの確保を行うと遅くなってしまうので
サイズがあらかじめ決まっているのなら
最初にreserveでメモリを全て確保してから
push_backで要素を追加していく方が好ましいかと思われます。

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

//
//    C2P構造体
//
struct C2P
{
    int cx;
    int cy;
    int px;
    int py;
    
    C2P(int camera_x, int camera_y, int proj_x, int proj_y)
    {
        cx = camera_x;
        cy = camera_y;
        px = proj_x;
        py = proj_y;
    }

};

//
//    C2Pオブジェクトの標準出力用演算子のオーバーライド
//
std::ostream& operator<<(std::ostream& os, const C2P& c2p)
{
    os << "---------------------------------" << std::endl;
    os << "cy:" << c2p.cy << std::endl;
    os << "cx:" << c2p.cx << std::endl;
    os << "py:" << c2p.py << std::endl;
    os << "px:" << c2p.px;
    return os;
}

//
//    C2Pの初期値生成関数
//
std::vector<C2P> c2pList_factry(const std::size_t size_x, const std::size_t size_y)
{
    auto result = std::vector<C2P>();
    result.reserve(size_x * size_y);

    for(std::size_t x = 0; x < size_x; x++) for(std::size_t y = 0; y < size_y; y++)
        result.push_back(C2P(x, y, rand() % 100, rand() % 100));

    return result;
}

//
//    main関数
//
int main()
{
    auto c2p_list = c2pList_factry(100, 200);

    std::sort(c2p_list.begin(), c2p_list.end(), [](const C2P& c2p_1, const C2P& c2p_2)
    {
       return c2p_1.py != c2p_2.py ? c2p_1.py < c2p_2.py : c2p_1.px < c2p_2.px;
    });

    for(auto&& i:c2p_list) std::cout << i << std::endl;

    return 0;        
}

wandboxで実行

Comments

[actorbug]

元のソースからC2Pの定義を変えてしまっているのは良いのでしょうか。
定義を変えなくても、reserveでメモリを事前確保するだけで十分だと思いますが。

[退会済みユーザー]

> 元のソースからC2Pの定義を変えてしまっているのは良いのでしょうか。
私の記載したサンプルコードに必要ない引数付きコンストラクタだったので省略しましたが
C2Pの定義を変えたくないのなら下記のように記載すれば良いかと思われます。

struct C2P
{
int cx;
int cy;
int px;
int py;

C2P() = default;

C2P(int camera_x, int camera_y, int proj_x, int proj_y)
{
cx = camera_x;
cy = camera_y;
px = proj_x;
py = proj_y;
}

};

> reserveでメモリを事前確保するだけで十分だと思いますが。
std::vectorのreserveを使うのも引数付きコンストラクタで事前にメモリを確保
することもやっている事は同じかと。

[actorbug]

> 私の記載したサンプルコードに必要ない引数付きコンストラクタだったので省略しましたが
> C2Pの定義を変えたくないのなら下記のように記載すれば良いかと思われます。
それって結局C2Pを改変しているのは変わらないのではないでしょうか。
元のソースだと引数ありのコンストラクタのみ定義しているので、
デフォルトコンストラクタが存在しません。
回答のソースだと、コンストラクタ定義がないのでデフォルトコンストラクタが存在します。
コメントのソースだと、C2P() = default;としているのでデフォルトコンストラクタが存在します。
デフォルトコンストラクタが存在するかどうかが、元ソースとの差になります。

> std::vectorのreserveを使うのも引数付きコンストラクタで事前にメモリを確保
> することもやっている事は同じかと。
元のソースだとC2Pのデフォルトコンストラクタがないので、
vectorの初期サイズを指定するとエラーになるはずです。
その場合でもreserveなら使用可能なので、C2Pを改変しないのなら、こちらしか選択肢はありません。
reserveとresizeを勘違いしてはいませんか。

[actorbug]

デフォルトコンストラクタが定義されるかどうかについては、以下のページなどを参照してください。

コンストラクタが暗黙に宣言されるとき、されないとき
https://qiita.com/rinse_/items/1ac008fe3aea7c0887fc

[退会済みユーザー]

確かにreserve+push_backを使えばデフォルトコンストラクタを呼ばなくて良いので消せますね。
回答があまり適切ではなかったので修正しておきました。
教えてくださりありがとうございます。

[k.s.t]

回答いただきありがとうございました。
無事に解決することができました。