コレクションクラスの選択

質問

VC++6.0 + MFCを利用しています。
下のような、複数の点とその座標を記録しておいて利用するためどのような実装にすればいいのか悩んでいます。
主な利用方法は、「点番号Xから座標をgetする」で、たまに、「すべての点の中でx座標が一番小さいほうから10番目の中にあり、かつ、y座標が最も小さな点番号をgetする」というような並び替えが必要となる利用が予想されます。
最初の使い方だけだったら、CMapクラスで、点番号をキー、各座標の構造体を値にすれば、実装できますが、それだと2番目の使い方のとき、毎回全データを見ないといけなくなって非常に効率が悪い気がします。
どのようなデータ構造にすれば効率よくこのような実装ができるでしょうか。できれば既存のクラスを組み合わせて使いたいのですが、詳しい方教えていただけますか。

点番号　x座標　y座標　z座標
　　　1　　　1.0　　　1.1　　　1.2
　　　2　　　2.0　　　2.3　　　4.5
　　　　　　　　:
　　　　　　　　:

回答No.3

jacta · ベストアンサー

> 追加で質問ですが、x座標の昇順に並び替えした点番号をもつことになるコンテナはどれにすればいいのでしょうか。

実際の用途が分からないと何とも言えないのですが...

> 「すべての点の中でx座標が一番小さいほうから10番目の中にあり、かつ、y座標が最も小さな点番号をgetする」

ということであれば、x座標順でソートしたvectorに、そのx座標を持つy座標順でソートしたvectorを要素として持たせる、すなわち二次元のvectorにしてもよいと思います。
std::vector<vector<点番号> > table;
といった感じです。
これだと、x座標が一番小さい方から10番目はtable[9]で表せますし、かつy座標が最も小さな点番号ということであれば、table[9][0]とすることができます（添え字の範囲チェックが必要ならatメンバ関数を使うなどしてください）。

お礼

よくわかりました。この方法でやってみたいと思います。
どうもありがとうございました。

回答No.2

jacta

#1の回答と似ているのですが...

主な用途が連番で座標を取得するということであれば、std::vectorクラステンプレートを使うのがよいでしょう。
そして、用途に応じて他のコンテナを使うことになるわけですが、そのとき、元のコンテナの各要素の反復子を格納するようにしておくとよいでしょう。無駄なコピーが発生しないので効率がよくなります。
ただし、元のコンテナの要素を後から追加するような場合には、反復子では都合が悪いので、要素番号（0, 1, 2, ...）か点番号を使うと良いでしょう。

お礼

回答ありがとうございます。
STL使ったことがないのですが、これを機会に使ってみようと思います。
追加で質問ですが、x座標の昇順に並び替えした点番号をもつことになるコンテナはどれにすればいいのでしょうか。
multisetが近いかと思いますが、キーと値を持つことができるのでしょうか。(点番号での昇順になってしまいませんか？)

回答No.1

JJsoft

複数の配列を利用してみては？
オリジナルの座標配列はそのままキープしておいて、それをコピーしたものをいくつか用意して、事前にX,Y,Zでそれぞれソートしておき、必要に応じて参照するのはどうですか？

お礼

たしかに配列を複数利用するのは思いつきませんでした。
ただ、点の数が万のオーダーですので、コピーすると、メモリ使用量がものすごく大きくなりそうで、あまり気がすすみません。