1

次のように動作するインデックス付きの連想コンテナが必要です。

  • 最初は空、サイズ=0。

  • 新しい要素を追加すると、ベクターの push_back と非常によく似たインデックス [サイズ] に配置されます。サイズをインクリメントし、新しく追加された要素のインデックスを返します。

  • 要素が既に存在する場合は、その要素が存在するインデックスを返します。

Set はこのための理想的なデータ構造のようですが、検索操作からインデックスを取得するようなものは見当たりません。セットを検索すると、要素にイテレータが返されます。

この状況で set.begin() との差を取ることは正しいことでしょうか?

4

1 に答える 1

5

STL には、これにすぐに適したデータ構造はありませんが、これを実装する簡単でかなり効率的な方法の 1 つは、マップとポインターのベクトルを使用することです。はmapオブジェクトを配列内のインデックスにマップし (オブジェクトが存在するかどうかのチェックが効率的であり、オブジェクトが既に存在する場合はインデックスをすぐに利用できるようにするため) vector、マップ内のオブジェクトにインデックスをマップします (そのため、インデックスによるオブジェクトの取得は効率的です)。

std::map<T,size_t> objects;
std::vector<const T *> indexed;

要素を追加するには:

size_t add_element(const T &v) {
    std::map<T,size_t>::iterator it=objects.find(v);
    if(it==objects.end()) {
        it=objects.insert(std::map<T,size_t>::value_type(v,objects.size())).first;
        indexed.push_back(&it->first);
    }
    return it->second;
}

(個人的なスタイルによる明らかな変更は、マップ イテレータのベクトルを格納し、毎回 map::insert を使用し、結果の bool 部分をチェックしてindexed更新が必要かどうかを確認することなどです。)

要素を取得するには:

const T &get_element(size_t index) {
    return *indexed[index];
}

そして、それはそれです。もちろん、1 つの問題は、オブジェクトがセットに含まれると、変更できないことです。これは、ここで実装された方法からの一種のリークです。マップ キーは const であるため、明らかな理由がありますが、実際には、実装に関係なく、とにかく必要なものだと思います。重複がないことを主張している場合は、オブジェクトがリストに入ると、変更によって別のオブジェクトの複製になる場合に備えて、変更可能であってはなりません。

size_t(また、ここで使用して少しごまかしていることにも注意してください。std::vector<const T *>::size_typeより正確には正しいと思います。これは主に簡潔にするためです!)

于 2010-04-01T16:54:45.743 に答える