ソートせずにコンテナを unique にする

ソートしてもいいなら

std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

でいいんだけど、ソートしたくない場合はどうするんだろうとか思ったわけです。

でまあ、自前でアルゴリズム書くとか無理ゲーなので、こんな風にしました。

// イテレータ経由で比較する
struct direct_less
{
    template<class Iterator>
    bool operator()(const Iterator& a, const Iterator& b) const
    {
        return *a < *b;
    }
};

template<class Iterator, class OutputIterator>
OutputIterator unique_no_sort(Iterator first, Iterator last, OutputIterator out)
{
    // 要素を格納するのは無駄なのでイテレータを格納する
    std::set<Iterator, direct_less> set;
    for (; first != last; ++first)
    {
        if (set.insert(first).second)
            *out++ = *first;
    }
    return out;
}

// イテレータ経由で Compare する
template<class Compare>
struct direct_less_comp
{
    template<class Iterator>
    bool operator()(const Iterator& a, const Iterator& b) const
    {
        return Compare()(*a, *b);
    }
};

template<class Iterator, class OutputIterator, class Compare>
OutputIterator unique_no_sort(Iterator first, Iterator last, OutputIterator out, Compare)
{
    std::set<Iterator, direct_less_comp<Compare> > set;
    for (; first != last; ++first)
    {
        if (set.insert(first).second)
            *out++ = *first;
    }
    return out;
}

int main()
{
    int values[] = { 3, 1, 3, 2, 5, 4, 2, 3, 3, 1, 0, 4, 5 };
    
    std::vector<int> v(values, values + sizeof(values) / sizeof(values[0]));
    std::vector<int> result;
    unique_no_sort(v.begin(), v.end(), std::back_inserter(result));
    for (std::vector<int>::iterator it = result.begin(); it != result.end(); ++it)
    {
        std::cout << *it << " ";
    }
}

3 1 2 5 4 0 

set 使って重複を検出するだけ。
Boost.MultiIndex とか使って sequential で ordered_unique なコンテナにぶち込めばそれでいけそうな気がする。