8

std :: vectorには、最初の要素から降順で並べ替えられた要素のコレクションがあります。連続したメモリチャンクに要素を含める必要があるため、ベクトルを使用する必要があります。そして、記述された特性を持つベクトルの多くのインスタンスを保持するコレクションがあります（常に降順でソートされます）。

さて、時々、より大きなコレクション（これらのベクトルを保持するもの）に要素が多すぎることがわかった場合、この擬似コードと同様に、これらのベクトルから最小の要素を破棄します。

grand_collection: collection that holds these vectors
T: type argument of my vector
C: the type that is a member of T, that participates in the < comparison (this is what sorts data before they hit any of the vectors).

std::map<C, std::pair<T::const_reverse_iterator, std::vector<T>&>> what_to_delete;
iterate(it = grand_collection.begin() -> grand_collection.end())
{
     iterate(vect_rit = it->rbegin() -> it->rend())
     {
         // ...
          what_to_delete <- (vect_rit->C, pair(vect_rit, *it))
          if (what_to_delete.size() > threshold)
               what_to_delete.erase(what_to_delete.begin());
         // ...  
     }
}

このコードを実行した後、what_to_deleteこれらのベクトルから削除したい元のベクトル（全体として最小の値）を指すイテレーターのコレクションがあります。元のベクトルは、このコードにヒットする前にソートされることを忘れないでください。つまりwhat_to_delete[0 - n]、位置上のイテレータが、同じベクトルの先頭から、、であるよりも遠い要素を指す方法はありませn - mん。nm > 0

元のベクトルから要素を消去するときは、reverse_iteratorをiteratorに変換する必要があります。これを行うために、私はC++11の§24.4.1/1に依存しています。

reverse_iteratorとイテレータの関係は＆*（reverse_iterator（i））==＆*（i-1）です。

つまり、を削除するvect_ritには、次を使用します。

vector.erase(--vect_rit.base());

現在、C ++ 11標準によると§23.3.6.5/3：

イテレータerase（const_iterator position）; 効果：消去の時点以降のイテレータと参照を無効にします。

これはreverse_iteratorsでどのように機能しますか？reverse_iteratorsは、ベクトルの実際の始まり（vector[0]）を参照して内部的に実装され、そのvect_ritを従来のイテレーターに変換してから消去しても安全ですか？または、reverse_iteratorはrbegin（）（これはvector[vector.size()]）を参照ポイントとして使用し、ベクトルの0インデックスから離れたものを削除しても、逆イテレーターは無効になりますか？

編集：

reverse_iteratorはrbegin（）を参照ポイントとして使用しているようです。私が説明した方法で要素を消去すると、最初の要素が削除された後、差分不可能なイテレータに関するエラーが発生しました。const_iterator一方、挿入中に従来のイテレータ（に変換）を保存すると、what_to_delete正しく機能しました。

さて、将来の参照のために、標準はランダムアクセスreverse_iteratorの場合に参照ポイントとして扱われるべきものを指定していますか？または、これは実装の詳細ですか？

ありがとう！

4

3 に答える 3

3

標準的な観点から（そして私は認めますが、私は標準の専門家ではありません）：§24.5.1.1から：

namespace std {
    template <class Iterator>
    class reverse_iterator ...
    {
        ...
            Iterator base() const; // explicit
        ...
        protected:
            Iterator current;
        ...
    };
}

そして§24.5.1.3.3から：

Iterator base() const; // explicit
    Returns: current.

vectorしたがって、あなたが前に何も消去しない限り、あなたreverse_iteratorのsの1つが指しているものreverse_iteratorは有効であり続けるべきであると私には思えます。

もちろん、あなたの説明を考えると、1つの落とし穴があります：あなたが削除したいと思う2つの連続した要素があなたのベクトルにある場合、あなたが直前の要素への「ポインティング」をvector.erase(--vector_rit.base())無効にしたことを意味するという事実、そしてreverse_iteratorしたがって、次vector.erase(...)は未定義の動作です。

それが泥のようにはっきりしている場合に備えて、別の言い方をしましょう。

std::vector<T> v=...;
...
// it_1 and it_2 are contiguous
std::vector<T>::reverse_iterator it_1=v.rend();
std::vector<T>::reverse_iterator it_2=it_1;
--it_2;

// Erase everything after it_1's pointee:

// convert from reverse_iterator to iterator
std::vector<T>::iterator tmp_it=it_1.base();

// but that points one too far in, so decrement;
--tmp_it;

// of course, now tmp_it points at it_2's base:
assert(tmp_it == it_2.base());

// perform erasure
v.erase(tmp_it);  // invalidates all iterators pointing at or past *tmp_it
                  // (like, say it_2.base()...)

// now delete it_2's pointee:
std::vector<T>::iterator tmp_it_2=it_2.base(); // note, invalid iterator!

// undefined behavior:
--tmp_it_2;
v.erase(tmp_it_2);

実際には、2つの可能な実装に遭遇するのではないかと思います。より一般的には、基iteratorになるものは（適切にラップされた）生のポインターにすぎないため、すべてが完全に正常に機能します。あまり一般的ではありませんが、イテレータは実際に無効化の追跡/境界チェックの実行を試み（Dinkumware STLは、ある時点でデバッグモードでコンパイルされたときにそのようなことをしませんでしたか？）、あなたに怒鳴る可能性があります。

于 2012-07-15T08:01:18.987 に答える
3

質問では、あなたはすでに標準が言っていることを正確に引用していますreverse_iterator：

reverse_iteratorとイテレータの関係は＆*（reverse_iterator（i））==＆*（i-1）です。

reverse_iteratoraは、基になるイテレータ（）の上にある単なる「アダプタ」であることを忘れないでくださいreverse_iterator::current。あなたが言うように、「参照点」reverse_iteratorは、ラップされたイテレータですcurrent。のすべての操作は、reverse_iterator実際にはその基礎となるイテレータで行われます。関数を使用してそのイテレータを取得できreverse_iterator::base()ます。

消去--vect_rit.base()すると、事実上消去されている--currentため、current無効になります。

ちなみに、式--vect_rit.base()は常にコンパイルされるとは限りません。イテレータが実際には単なる生のポインタである場合（の場合のようにvector）、vect_rit.base()右辺値（C ++ 11用語ではprvalue）を返すため、pre-decrement演算子は、その演算子が必要とするため、それに対して機能しません。変更可能な左辺値。Scott Meyersによる「EffectiveSTL」の「Item28： reverse_iterator'sbaseの使用方法を理解する」を参照してください。（アイテムの初期バージョンは、 http：iterator //www.drdobbs.com/three-guidelines-for-effective-iterator/184401406の「ガイドライン3」でオンラインで見つけることができます）。

(++vect_rit).base()その問題を回避するために、さらに醜い式を使用することができます。または、ベクトルとランダムアクセスのイテレータを扱っているので：vect_rit.base() - 1

いずれにせよ、vect_ritは無効になっているため、消去によってvect_rit.current無効になります。

vector::erase()ただし、これは、消去されたばかりの要素に続く要素の新しい場所に有効なイテレータを返すことを忘れないでください。これを使用して「再同期」することができますvect_rit：

vect_rit = vector_type::reverse_iterator( vector.erase(vect_rit.base() - 1));
于 2012-07-15T09:21:56.237 に答える
0

はreverse_iterator、通常のようiteratorに、ベクトル内の特定の位置を指します。実装の詳細は関係ありませんが、知っておく必要がある場合は、両方とも（通常の実装では）内部の単なる古いポインターです。違いは方向です。逆イテレータには、通常のイテレータ（およびand、など）との+逆-イテレータ++が--あり>ます<。

これは知っておくと面白いですが、実際には主な質問に対する答えを意味するものではありません。

言語を注意深く読むと、次のようになります。

消去の時点以降のイテレータと参照を無効にします。

参照には、方向性が組み込まれていません。したがって、この言語は、コンテナ自体の方向性を明確に示しています。消去点以降の位置は、インデックスが高い位置です。したがって、ここではイテレータの方向は関係ありません。

于 2012-07-15T09:09:03.887 に答える