データ構造で悩んでます

質問

以下の構造体があります。
struct Test {
　　string name;
　　int no;// 1～100
　　int age;// 1～100
};
stlのvectorに頻繁に動的に追加、削除されるとします。これをnoやageをキーに効率よく検索する方法を教えてください。

私が思いついたのは、
・multisetを別に用意する。問題点は追加、削除毎にソートされてしまう。
・no,age分vectorを用意する。速いけど汎用性が無い。

boostや他のライブラリは無しでお願いします。

回答No.4

qwertfk

struct Test
{
　string name;
　int no;
　int age;
};
typedef list<Test> TestList;
typedef vector<Test*> TestPtrAry;

struct TestContainer
{
public:
　TestList Buf;

private:
　map< int , TestPtrAry > No_Test;
　map< int , TestPtrAry > Age_Test;

public:
　void Add( const Test& t )
　{
　　Buf.push_back(t);
　　No_Test[ t.no ].push_back( &Buf.back() );
　　Age_Test[ t.age ].push_back( &Buf.back() );
　}

　const TestPtrAry* GetItemsByAge( int age )
　{
　　if( Age_Test.find(age) == Age_Test.end() ) return NULL;
　　return &Age_Test[age];
　}
};

という感じでどうでしょうか。

お礼

回答ありがとうございます。
検索用にマップを用意するやり方ですね。。。
検証してみます。

回答No.3

hitomura

要件を見る限り、検索キーがnoまたはageのようなので、setやmapは使いづらいのではないでしょうか。
とりあえずこんな感じで検索ができました。

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Test {
　string name;
　int no;
　int age;
};

// no によるデータ収集
struct SearcherByNo {
　int no_;
　vector<Test>* result_;

　SearcherByNo(int no, vector<Test>* result)
　{
　　no_ = no;
　　result_ = result;
　}
　void operator()(Test& tester)
　{
　　if (tester.no == no_){
　　　result_->push_back(tester);
　　}
　}
};

// age によるデータ収集
struct SearcherByAge {
　int age_;
　vector<Test>* result_;

　SearcherByAge(int age, vector<Test>* result)
　{
　　age_ = age;
　　result_ = result;
　}
　void operator()(Test& tester)
　{
　　if (tester.age == age_){
　　　result_->push_back(tester);
　　}
　}
};

int main(int argc, char** argv)
{
　vector<Test> test_data;

　// テスト用データ追加
　Test alpha = {"alpha", 20, 10};
　Test beta = {"beta", 20, 50};
　Test gamma = {"gamma", 80, 50};
　test_data.push_back(alpha);
　test_data.push_back(beta);
　test_data.push_back(gamma);

　cout << "*** no によるデータ検索 ***" << endl;
　vector<Test> result_sbn;
　for_each(test_data.begin(), test_data.end(), SearcherByNo(20, &result_sbn));
　for (vector<Test>::iterator i = result_sbn.begin(); i != result_sbn.end(); i++){
　　cout << i->name << endl;
　}

　cout << "*** age によるデータ検索 ***" << endl;
　vector<Test> result_sba;
　for_each(test_data.begin(), test_data.end(), SearcherByAge(10, &result_sba));
　for (vector<Test>::iterator i = result_sba.begin(); i != result_sba.end(); i++){
　　cout << i->name << endl;
　}

　return 0;
}

なお、データのコピーを行っているので、検索後にデータの追加・修正があったときに実際のデータとズレが出てくる恐れがあります。

お礼

回答ありがとうございます。
このやり方ですとスッキリしてて良いですね。
ただ、検索は先頭から検索して行ってるので時間がかかっちゃいますね、、、
色々考えて見たいと思います。

回答No.2

tsuduki123

vectorなのは配列っぽいアクセスが多いということなんですかね?
参照方式がわかんないから何ともいえないけれど
個人的には、std::vectorやめてstd::list にしてfind_ifを使うに一票
vectorのままでもfind_ifは使えますけどvectorは要素数の編集が苦手ですよ。(記憶)

まぁ、レンジスキャン、ユニークスキャンの方が
追加削除よりもおおいならmultisetだけでよいとおもわれ
要素指定のアクセスが多いのならvectorのまま find_ifでしょうか。。

お礼

回答ありがとうございます。
アクセスに関しては先頭から末尾を順にアクセスします。
追加は末尾。削除は任意の場所です。
find_ifというものがあるんですか。知りませんでした。

ただ、検索も頻繁に行われるのでsetやmapで要素の追加時にソートしたほうがいいのかなと思って質問しました。でもソートも時間かかるんですよね。。。

回答No.1

hitomura

確認したいのですが、この構造体の列に対する検索とは具体的に何をするのでしょうか。自分が思いついたのは、
(1)とにかく一致するものが1つでも見つかればいい
(2)一致するデータが全てほしい
(3)ある一定範囲内に値が入るデータが全てほしい
の3パターンですが、上記の何番なのか、ぜんぜん違うならばどのような検索をやりたいのか具体的な例を挙げて説明願います。

お礼

回答ありがとうございます。
検索は(2)一致するデータが全てほしいです。