4

C++ドラフトはstd::lower_boundについて述べています：

§ 25.4.3.1 lower_bound [lower.bound]  
template<class ForwardIterator, class T>  
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& value);  
template<class ForwardIterator, class T, class Compare>  
ForwardIterator lower_bound(ForwardIterator first, 
                            ForwardIterator last, 
                            const T& value, 
                            Compare comp);  

Requires: The elements e of [first,last) shall be partitioned with respect 
    to the expression e < value or comp(e, value).
Returns: The furthermost iterator i in the range [first,last] such that for 
    any iterator j in the range [first,i) the following corresponding 
    conditions hold: *j < value or comp(*j, value) != false.
Complexity: At most log2(last − first) + O(1) comparisons.

これにより、（含意によって）*ForwardIterator返されるものとは異なる（しかし比較可能な）タイプを比較できますが、イテレーターの進歩の数に複雑さの制限はありません。（ノードベースのコンテナの場合、これはO（最後-最初）のイテレータの進歩になります。）

§ 23.4.6.1
class set { 
   ...
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
   ...
}

標準ではこれらの関数について詳しく説明していませんが、これらはO（log2（last − first））の比較と進歩のためのものであることが暗示されていますが、検索キーは含まれているタイプと同じである必要があります。

だから私の質問は次のとおりです：
（1）検索タイプの速度std::set::lower_boundと柔軟性を取得する方法はありstd::lower_boundますか？
（2）なぜstd::lower_bound専門化する必要がないのですstd::set::iteratorか？
（3）に特化した実装std::lower_bound はstd::set::iteratorありますか、それとも理由はありますか？

私は次のようなものを見つけたいと思っていました：

template< class Key, class Comp, class Alloc, class Lookup>  
std::set<Key, Compare, Alloc>::const_iterator 
    lower_bound(
        std::set<Key, Comp, Alloc>::const_iterator begin, 
        std::set<Key, Comp, Alloc>::const_iterator end, 
        const Lookup& find,
        Compare comp);
template< class Key, class Comp, class Alloc, class Lookup>  
std::set<Key, Compare, Alloc>::iterator 
    lower_bound(
        std::set<Key, Comp, Alloc>::iterator begin, 
        std::set<Key, Comp, Alloc>::iterator end, 
        const Lookup& find,
        Compare comp);

また：

template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> >
class set {
   ...
    template<class Lookup>
    iterator lower_bound(const Lookup& x);
    template<class Lookup>
    const_iterator lower_bound(const Lookup& x) const;
   ...
}

しかし、私はそれが存在することを疑っています。明らかに、これらすべてを他のツリーベースのコンテナや他のアルゴリズムに拡張できます。自分でコーディングしますが、実装固有のコードを使用する必要があります。このアイデアは、この質問から生まれました。非キータイプのセットでの効果的な検索

4

1 に答える 1

4

std::setコンテナは、構築時に指定された比較オブジェクトに従って順序付けられます。がstd::lower_bound呼び出されると、一致する比較オブジェクトが渡されたことを確認する方法がないため、実装は標準アルゴリズムを使用するか、セットに特化したアルゴリズムを使用するかを判断できません。後者は、使用される比較オブジェクトを使用する場合にのみ有効です。セットの順序（または同じ結果が得られる順序）。

追加した2つのプロトタイプの例は機能しません。

  1. イテレータstd::lower_boundでの作業に特化：std::set

    これは、上記の理由で機能しません。指定された比較オブジェクトが、セットのコンストラクターで指定されたものと一致するかどうかを確認する方法はありません。プロトタイプは、比較オブジェクトのタイプが一致することのみをチェックしますが、同じタイプの異なる比較オブジェクトが存在する可能性があります。

  2. テンプレートstd::set::lower_bound引数を取るようにする：

    これにより、セットの比較オブジェクトとの互換性が失われる可能性があります。これは、そのオブジェクトoperator()は通常テンプレート化されず、タイプが引数のみを想定しているためですT。

于 2011-09-20T17:15:37.443 に答える