C++で3次元ベクトルをstd::setにinsertする

こんにちは。ヤマヤタケシです。
くっそー。意外にハマった!ハマったから、ここにメモる!

やりたいこと。double x,y,zの3次元ベクトルを重複なしにしたい!
で、std::vectorだと線形に探してしまうので、クソ遅い。
なので、std::setを使ってやろう!

それがなかなか難しかった。
std::setは、要素を内部で序列付きで追加してくれる。
序列があるから、対数時間で重複なしで挿入できる。

自分が作ったクラスなので、”序列”を自分で定義しなくちゃいけない。

具体的には、operator < をオーバーライドする必要がある。 operator< の条件がなかなかうまく行かなかったのだ! うまくいったあとコードを眺めれば、「そうだよね。」くらいなのだけども。 考えの浅い間違った条件のコード。

bool operator<(const Vertex3& left, const Vertex3& right)
{
	return 
        left.x < right.x &&
        left.y < right.y &&	
        left.z < right.z;
}

正しいコード。テスト付き。

//
//
// 3次元ベクトルのstd::set のためのoperator < のテスト
//
/*
#テスト用makefile
all:
	g++ -std=c++11 aaaaaa.cpp
	./a.exe
*/

#include 
#include 
using namespace std;
class Vertex3
{
public:
    double x, y , z;
    Vertex3() : x( 0 ), y( 0 ), z( 0 ){}
    Vertex3( double tx, double ty , double tz )
        : x( tx ), y( ty ), z( tz )
    {
    }

};

bool operator<(const Vertex3& left, const Vertex3& right)
{
    if( left.x < right.x ){
        return true;
    }

    if( left.x == right.x ){
        if( left.y < right.y ){
            return true;
        }

        if( left.y == right.y ){
            if( left.z < right.z ){
                return true;
            }
        }
    }

    return false;
}

void test()
{
    std::set vertexSet;
    auto result = vertexSet.insert( Vertex3( 1,0,0 ) );
    cout << result.second << endl;
    result = vertexSet.insert( Vertex3( 1,0,0 ) );
    cout << result.second << endl;
    result = vertexSet.insert( Vertex3( 2,0,0 ) );
    cout << result.second << endl;
    result = vertexSet.insert( Vertex3( 1,1,0 ) );
    result = vertexSet.insert( Vertex3( 1,1,0 ) );
    cout << result.second << endl;
}

int main()
{
    test();
    return 0;
}

そんじゃまた。

軽い気持ちで有名になりたいのでクリックをお願いします!

コメントを残す

メールアドレスが公開されることはありません。