bigsleepの日記

 | 

2011-04-29

ソートされたインデックスを取得

20:14

なにかの値がコンテナに入っていて、コンテナの要素順は変更したくない、または変更できない

でもソートされたアクセス方法が欲しいということがある気がします。

こういうときどうするかのメモ。

比較用の関数オブジェクト書く

関数オブジェクトを書いてインデックスをソート。

これでまあいいと思うけど、なんか名前がcompareとかlessとかしか思いつかない。

あまり何度も使うわけではないのでLambda使えればLambdaで書いた方が良さそう。

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

class compare
{
private:
    std::vector<double> const& m_v;

public:
    typedef bool result_type;
    
    compare(std::vector<double> const& _v)
        : m_v(_v)
    {}
    
    bool operator()(std::size_t a, std::size_t b) const
    {
        return (m_v[a] < m_v[b]);
    }
};

int main()
{
    std::vector<double> v = {0.8, 0.7, 0.0, 0.6, 0.2, 0.9, 0.3, 0.1, 0.4, 0.5};
    std::vector<std::size_t> idx(v.size());
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(idx.begin(), idx.end(), compare(v));
    
    for(std::size_t i = 0, sz = v.size(); i < sz; ++i){
        std::cout << v[idx[i]] << std::endl;
    }
}

boost.bind使う

これでも書けたけどオーバーロードされているメンバ関数ポインタをとるところでメンバ関数ポインタの型を

書かなくちゃならないのが面倒くさい。やっぱりLambdaあればLambda使ったほうが楽そう。

#include <iostream>
#include <vector>
#include <cstddef>
#include <numeric>
#include <algorithm>
#include <functional>
#include <boost/function.hpp>
#include <boost/bind.hpp>

int main()
{
    std::vector<double> v = {0.8, 0.7, 0.0, 0.6, 0.2, 0.9, 0.3, 0.1, 0.4, 0.5};
    std::vector<std::size_t> idx(v.size());
    std::iota(idx.begin(), idx.end(), 0);
    
    typedef double const& (std::vector<double>::*at_type)(std::vector<double>::size_type) const;
    boost::function<bool(std::size_t, std::size_t)>
        compare = boost::bind(std::less<double>(),
            boost::bind(static_cast<at_type>(&std::vector<double>::at), &v, _1),
            boost::bind(static_cast<at_type>(&std::vector<double>::at), &v, _2));
    
    std::sort(idx.begin(), idx.end(), compare);
    
    for(std::size_t i = 0, sz = v.size(); i < sz; ++i){
        std::cout << v[idx[i]] << std::endl;
    }
}

Lambda使う

今手元にLambda使えるコンパイラがないのでコンパイルしてないけど下のような感じか。

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

int main()
{
    std::vector<double> v = {0.8, 0.7, 0.0, 0.6, 0.2, 0.9, 0.3, 0.1, 0.4, 0.5};
    std::vector<std::size_t> idx(v.size());
    std::iota(idx.begin(), idx.end(), 0);
    
    std::sort(idx.begin(), idx.end(),
        [&v](std::size_t a, std::size_t b) -> (bool)
        {
            return (v[a] < v[b]);
        });
    
    for(std::size_t i = 0, sz = v.size(); i < sz; ++i){
        std::cout << v[idx[i]] << std::endl;
    }
}

アルゴリズムっぽい問題

20:14

辺が交差しない平面グラフがあって、点の位置のリストと、辺が結ぶ点のペアのリストがあるときに閉空間の数を数えたり、面積を求めたりするというアルゴリズムっぽい問題をやっていた。

自分がグラフとかアルゴリズムとか全然知らないからか、かなり難しいように感じる。

プログラミングコンテストにでてるような人はぱっととけるのかも。

いまいちうまいやりかたが思いつかないけど、辺の角度でソートされた近接リストを作って図のような感じで閉空間を探して、評価し終わった点を消す。逆まわりの場合は除くような感じでやった。

f:id:bigsleep:20110429201327p:image

連結しているとは限らないので入れ子の状態になっている場合等を考えるとさらに面倒くさい...。

faith_and_bravefaith_and_brave 2011/04/30 07:36 Boost.MultiIndexを使うという手もあります。

bigsleepbigsleep 2011/04/30 11:42 コメントありがとうございます。
multi_index使ったことなかったんですが、少し調べたところご指摘の通りこの記事の目的にちょうどあうような気がします。
自分が書いたような方法だと、要素追加したときなどに再度ソートの処理をしなければならないので、あまりスマートでないですね。

 |