4

コンテナーが必要です。ここで:

  • まだ存在しない新しい要素を追加すると、リストの一番上に追加されます
  • 既に存在する要素を追加すると、追加されず、リストにそのインデックスが取得されます
  • 要素が挿入されると、常に同じインデックスを持ち、このインデックスを使用してアクセスできます

std::setで要素にアクセスできないため、単独では不十分[index]です。std::listどちらも、一意の要素のみを格納しないためです。

listand との混合ソリューションを使用しましたmapが、そのための標準的で汎用的なテンプレートがあるのでしょうか?

ブーストは使いたくない。list::unique挿入のたびに呼び出すことは解決策ではありません。

4

1 に答える 1

3

a std::list(またはstd::vector、さらに言えば) を使用している場合、重複を避けたくないが元の順序を維持したい場合は、線形検索を回避することはできません。シンプルな std::vectorソリューションは次のとおりです。

int
createIndex( std::vector<T>& references, T const& newValue )
{
    int results = std::find( references.begin(), references.end(), newValue )
                                    - references.begin();
    if ( results == references.size() ) {
        references.push_back( newValue );
    }
    return results;
}

または、次を使用できますstd::map。

int
createIndex( std::map<T, int>& references, T const& newValue )
{
    st::map<T, int>::iterator results = references.find( newValue );
    if ( results == references.end() ) {
        results = references.insert(
                    std::make_pair( newValue, references.size() ) ).first;
    }
    return results->second;
}

(これは が をTサポートしていると仮定します<。そうでない場合は、順序付け基準を確立する必要があります。またはunordered_map、ハッシュ コードを使用して定義する必要があります。)

于 2012-04-20T10:25:21.263 に答える