1

これはおそらくばかげた質問だと思いますが、確認したかったので、この情報をすぐに見つけることができませんでした。

順序付けされていないマップでのfind（）のパフォーマンス特性は何ですか？通常のルックアップと同じくらい速い/ほぼ同じくらい速いですか？

つまり

std::string defaultrow = sprite.attribute("defaultrow").value();
auto rclassIt = Rows::NameRowMap.find(defaultrow);
if (rclassIt != Rows::NameRowMap.end())
    defRow = rclassIt->second;

対。

std::string defaultrow = sprite.attribute("defaultrow").value();
defRow = Rows::NameRowMap[defaultrow];

ここRows::NameRowMapで、は文字列インデックスをintにマッピングする順序付けられていないマップです。

私の場合、キーが事前に存在するかどうかはわかりません。そのため、最初の解決策の方が安全だと思われましたが、存在を保証できれば、2番目のケースの方が高速です（追加のチェックを無視します）。 ？もしそうなら、なぜですか？重要な場合は、1.46ブーストの実装を使用しています

4

3 に答える 3

4

内部でandをoperator[]使用する可能性はかなりあります。たとえば、IIRC は、Miscrosoft の実装に当てはまります。findinsertstd::map

編集：私が言おうとしていたoperator[]のは、それは魔法ではなく、最初にルックアップを行う必要があるということです。Boost 1.46.0 で見たものから、両方findのオペレーターがfind_iterator内部で使用しています。

findコードがより再利用可能で堅牢になるため (たとえば、何かを誤って挿入することはありません)、特にある種の一般的なコードでは、通常はルックアップに使用することをお勧めします。

于 2011-08-11T00:35:18.427 に答える
3

find順序付けられoperator[]ていないコンテナーでは、平均 O(1)、最悪の場合 O(n) です。これは、ハッシュ関数の品質に依存します。

于 2011-08-11T00:30:10.860 に答える
1

それらは O(1) と同じ償却された複雑さを持ちますが、値が見つからない場合、演算子は新しい要素も作成します。値が見つかった場合、パフォーマンスの違いはわずかです。私のブーストは少し古い - バージョン 1.41 ですが、問題にならないことを願っています。コードは次のとおりです。

// find
//
// strong exception safety, no side effects
template <class H, class P, class A, class G, class K>
BOOST_DEDUCED_TYPENAME hash_table<H, P, A, G, K>::iterator_base
hash_table<H, P, A, G, K>::find(key_type const& k) const
{
    if(!this->size_) return this->end();

    bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
    node_ptr it = find_iterator(bucket, k);

    if (BOOST_UNORDERED_BORLAND_BOOL(it))
        return iterator_base(bucket, it);
    else
        return this->end();
}

// if hash function throws, basic exception safety
// strong otherwise
template <class H, class P, class A, class K>
    BOOST_DEDUCED_TYPENAME hash_unique_table<H, P, A, K>::value_type&
hash_unique_table<H, P, A, K>::operator[](key_type const& k)
{
    typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;

    std::size_t hash_value = this->hash_function()(k);
    bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);

    if(!this->buckets_) {
        node_constructor a(*this);
        a.construct_pair(k, (mapped_type*) 0);
        return *this->emplace_empty_impl_with_node(a, 1);
    }

    node_ptr pos = this->find_iterator(bucket, k);

    if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
        return node::get_value(pos);
    }
    else {
        // Side effects only in this block.

        // Create the node before rehashing in case it throws an
        // exception (need strong safety in such a case).
        node_constructor a(*this);
        a.construct_pair(k, (mapped_type*) 0);

        // reserve has basic exception safety if the hash function
        // throws, strong otherwise.
        if(this->reserve_for_insert(this->size_ + 1))
            bucket = this->bucket_ptr_from_hash(hash_value);

        // Nothing after this point can throw.

        return node::get_value(add_node(a, bucket));
    }
}
于 2011-08-11T00:51:12.027 に答える