ソートしてなくても動くuniqueを書いた

std::uniqueは引数のコンテナの要素がソートされていることを前提に作られているのですが、最近C#ばかり触っているおかげですっかり忘れていました。思い出すのまで3分くらいぼーっとしてしまった。

で、ソートしたら重複した要素はなくなったのですが、ソートされると都合の悪いデータだったため、ソートしなくても良いunique関数を書きました。効率とか気にしないで書いているのであまり宜しくなさそうですがまあ気にしません。富豪的!

template<class T>
std::vector<T> unsorted_unique(T* first, T* last)
{
    std::vector<T> result;
    std::map<T, bool> cache;
    for (; first != last; ++first) {
        if (cache.find(*first) == cache.end()) {
            result.push_back(*first);
            cache[*first] = true;
        }
    }
    return result;
}

こちらは1分くらいで書けましたが一度 if 文の中を間違えて find(*fist) != end() とか書いて結果が空になったりと愉快な結果になったりしました。デバッグに1分追加。何も考えないで書いているとこうなる。で、テストする前にこれ書いてるのでバグがあるかも。

というかfindなんかしなくても一度全部の要素をmap(のkey)に入れてから取り出すだけでユニークになるのかな……とここまで書いて気付いた。

追記:↑試したら並び順が変わってしまった。そりゃそうか。