uniqueの使い方について

質問

現在C++でSTLを用いてプログラムを書いておりますが、uniqueの使い方で質問があります。

1, 1, 1,2 , 1
という配列が合った場合、uniqueで重複を消した場合、
1, 2, 1
となります。
sortをしてからuniqueを使えば
1,2
となりますが、sortをせずに一気に重複変数を消すアルゴリズムはありますでしょうか？

このようなアルゴリズムが必要なのは以下の通りです。
要素にa,bを持つ構造体A
struct A{
int a;
int b;
};
で、まずaの値でソートし、次にbの値が重複しているものは消すプログラムを書いております。
例えば
(a,b) = (2,2), (1,1) (3,1)
の場合
(a,b)=(1,1) (2,2)
としたいのですが、単純にuniqueを使うと連続した値しか重複判定をしないので、
(a,b)=(1,1) (2,2) (3,1)
と(3,1)が残ってしまいます。

uniqueに変わる良い方法はありますでしょうか？
説明が下手で申し訳ございませんが、もしなにか良い方法がございましたらご教示お願いいたします。

回答No.3

qwertfk

uniqueを使う場合、対象の要素があらかじめソートされてあることが必須なので、
まずはbでソート→その後uniqueという手順が必要です。

Aの配列が、bがユニーク+aでソートされている、という条件さえクリアできれば良いのであれば

void ToUnique_A(std::vector<A>& v)
{
std::sort(v.begin(), v.end(),
[] (A& a, A& b){return a.b < b.b;});

std::vector<A>::iterator it;
it = std::unique(v.begin(), v.end(),
[] (A& a, A& b){return a.b == b.b;});
v.resize(std::distance(v.begin(), it));

std::sort(v.begin(), v.end(),
[] (A& a, A& b){return a.a < b.a;});
}

このようにすれば可能です。

もしくは、setを使えば下記のように実装できます。

void ToUnique_B(std::vector<A>& v)
{
std::set<int> us;
for (std::vector<A>::iterator i = v.begin(); i != v.end(); ++i)
{
std::set<int>::iterator j = us.find(i->b);
if (j == us.end())
us.insert(i->b);
else
v.erase(i--);
}
}

回答No.2

επιστημη（@episteme）

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int main() {
const int N = 10;
int data[N] = { 1, 2 ,2, 1 ,4 ,5, 2, 3, 4, 3 };
vector<int> result; // 結果はココに。

set<int> hist;
for( int item : data) {
if ( hist.insert(item).second ) {
result.push_back(item);
}
}

for ( int item : result ) {
cout << item << ' ';
}
cout << endl;
}

回答No.1

Tacosan

まあ std::set を使えばできるっちゃできるけど.... 本質的にソートするのと変わらんってのが微妙.

あれ? std::map でできそう?