14

advance私はいくつかで使用していますがiterators、上記の飛躍の可能性を恐れていますend()。イテレータが境界の間にあることを確認したいのですが、私は考えましたdistanceが、期待したものが返されないようです（イテレータが高架になっている場合は正でない値end()）。リープフロッグがないことをどのように確認しますか？

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main () {
  list<int> mylist;
  for (int i=0; i<10; i++) mylist.push_back (i*10);

  list<int>::const_iterator first = mylist.begin();
  const list<int>::const_iterator last = mylist.end();

  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0
  advance(first, 1);
  cout << "The distance is: " << distance(first,last) << endl; // 10
  advance(first, 10);
  cout << "The distance is: " << distance(first,last) << endl; // 0

  return 0;
}

出力は次のとおりです。

The distance is: 10
The distance is: 0
The distance is: 10
The distance is: 0
4

6 に答える 6

15

Advance（）past end（）は、未定義の動作になります。このスニペットに従ってテストする必要があります。

  template <class Iter, class Incr>
  void safe_advance(Iter& curr, const Iter& end, Incr n)
  {
    size_t remaining(std::distance(curr, end));
    if (remaining < n)
    {
      n = remaining;
    }
    std::advance(curr, n);
  }

全額移動しないとどうなるかを考える必要があります（currとして返されます） end()。

于 2010-10-04T15:26:22.640 に答える
8

distance呼び出し、または次のadvanceモデル以外のものを呼び出すのは非効率的ですRandomAccessIterator。呼び出しはO（n）です。ここで、nは距離を表します。

また、は、そのメソッドが一定（または償却定数）であることが保証されていないという点listで真のモデルではありません。実際、O（n）である可能性があります。Sequencesize

したがって、コードを見ると（そして、以外のものを使用できない場合list）、2つの可能性があります。

  • アドバンスを使用せず、一度に1つのアイテムを移動しend、各ステップで確認します。
  • 最初にサイズを一度だけ計算すると、未定義の動作を呼び出す前にどれだけ進むことができるかがわかります（カウンターを横に置いたり、イテレーターをラップしたりすることができます...）

これに基づいて行動しましょう：

// Advance one at a time
// replace calls to advance by this function

typedef list<int>::const_iterator const_iterator;

const_iterator safe_advance(const_iterator it, const_iterator end, size_t n)
{
  for (size_t i = 0; i != n && it != end; ++i) { ++it; }
  return it;
}


// Precompute size
size_t const size = list.size();

size_t remaining = size;
const_iterator begin = list.begin();

size_t ad = std::min(10, remaining);
advance(begin, ad);
remaining -= ad;

ad = std::min(1, remaining);
advance(begin, ad);
remaining -= ad;

しかし、このカウントを続けるのは面倒です...

編集：

ソリューションを一般化するためのDavidの正当な懸念に対処する：

// Advance `it` from n, or up to end
// returns the number of steps that could not be performed
template <typename Iterator>
size_t safe_advance(Iterator& it, Iterator const& end, size_t n)
{
  size_t i = 0;
  for (; i != n && it != end; ++i, ++it);
  return n - i;
}

双方向イテレータの場合、advance負の距離で使用できますが、これには持ち込みbeginも必要であり、非常に面倒になることに注意してください。そのため、私は2番目の方法を非常に好みます。

template <typename BI>
size_t safe_reverse(BI& it, BI const& begin, size_t n)
{
  for (; n != 0 && it != begin; --n, --it);
  return n;
}

そして最後に、ここでは行いませんがRandomAccessIterator、これらの操作はO（1）でそのようなものを使用して実行できるため、テンプレートを特殊化することをお勧めします。

于 2010-10-04T19:13:03.830 に答える
5

距離はこれを行うことはできません。コンテナがランダムアクセスを提供しない場合、開始を進めることで終了に到達しようとします。これにより、開始が最後に追い越されたときに大混乱が発生します。

有効な開始点から開始し（つまり、開始を進めることで最後に到達できます）、各前進の前に距離を確認し、最後に追い越さないようにX <=（distance（first、last））だけ前進する必要があります。

于 2010-10-04T15:09:28.660 に答える
3

簡単です。.end()超えないようにするには、単に超えないようにします.end()。ポインタなどの使用を避ける場合と同じように状況は変わりNULLません。コードが発生しないように構造化してください。たとえば、などの条件を使用するループを使用しますit != v.end()。一般的な標準ライブラリの実装の中には、これらのエラーを検出して通知するものがありますが、これに依存するのではなく、テスト/デバッグ中にのみ使用してください。

アップデート

advance()1を超える量でできるかどうか確信が持てない場合は、単に1advance()を超えてはなりません。

于 2010-10-04T15:08:58.363 に答える
3

1つには、終了イテレータを格納し、重要な操作をチェックするイテレータラッパーを作成することもできます。

たとえばiterator_facade、簡潔にするためにブーストを使用し、アンダーフローをチェックしません。

#include <boost/iterator/iterator_facade.hpp>
#include <iterator>
#include <stdexcept>

template <class Iter>
class checked_iterator:
    public boost::iterator_facade<
        checked_iterator<Iter>,
        typename std::iterator_traits<Iter>::value_type,
        typename std::iterator_traits<Iter>::iterator_category
    >
{
    Iter it, end;
public:
    checked_iterator(Iter it, Iter end): it(it), end(end) {} 
    void increment() 
    { 
        if (it == end) { throw std::range_error("checked_iterator: increment beyond end"); }
        ++it;
    }
    void decrement()
    {
        //TODO: this is not checked
        --it;
    }
    bool equal(const checked_iterator& other) const
    {
        return it == other.it;
    }
    typename std::iterator_traits<Iter>::reference dereference() const 
    {
        if (it == end) { throw std::range_error("checked_iterator: dereference end"); }
        return *it;
    }
    void advance(typename std::iterator_traits<Iter>::difference_type n)
    {
        //TODO: not checked for underflow
        if (std::distance(it, end) < n) { throw std::range_error("checked_iterator: advance beyond end"); }
        it += n;
    }
    typename std::iterator_traits<Iter>::difference_type distance_to(const checked_iterator& other) const
    {
        return other.it - it;
    }
    Iter base() const { return it; }
};

//create checked_iterators from containers, could be overloaded for arrays
template <class Container>
checked_iterator<typename Container::iterator> checked_begin(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_begin(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.begin(), c.end());
}

template <class Container>
checked_iterator<typename Container::iterator> checked_end(Container& c)
{
    return checked_iterator<typename Container::iterator>(c.end(), c.end());
}

template <class Container>
checked_iterator<typename Container::const_iterator> checked_end(const Container& c)
{
    return checked_iterator<typename Container::const_iterator>(c.end(), c.end());
}

テストコードの例：

#include <vector>
#include <list>
#include <iostream>
int main()
{
    typedef std::list<int> Container;
    try {
        Container v(10);
        checked_iterator<Container::iterator> it = checked_begin(v);
        std::advance(it, 6);
        std::cout << *it << '\n';
        std::advance(it, 4);
        std::cout << *it << '\n';
        const Container& r = v;
        checked_iterator<Container::const_iterator> cit = checked_begin(r);
        std::advance(cit, 11);
    }
    catch (const std::exception& e) {
        std::cout << e.what() << '\n';
    }
}

関数の実装に関しては、効率上の理由からsafe_advance、これによりランダムアクセスイテレータと他のイテレータを区別することもできます。std::advance

#include <iterator>
#include <stdexcept>

namespace detail
{
    template <class Iter>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        std::random_access_iterator_tag
        )
    {
        if (end - it < n) throw std::range_error("advance beyond end (ra)");
        it += n;
    }

    template <class Iter, class Tag>
    void safe_advance_aux(
        Iter& it, Iter end, 
        typename std::iterator_traits<Iter>::difference_type n, 
        Tag
        )
    {
        for (typename std::iterator_traits<Iter>::difference_type i = 0; i != n; ++i) {
            if (it == end) throw std::range_error("advance beyond end");
            ++it;
        }
    }
}

template <class Iter>
void safe_advance(Iter& it, Iter end, typename std::iterator_traits<Iter>::difference_type n)
{
    detail::safe_advance_aux(it, end, n, typename std::iterator_traits<Iter>::iterator_category());
}
于 2010-10-05T10:22:15.070 に答える
2

ここで間違った問題を解決しようとしていると思います。

advanceを超える可能性のある方法で使用しないでくださいend。現在のイテレータが終了を指している場合、increment（特別な形式のadvance）を使用することはありません。したがって、コンテナに十分な残りの要素があることをコードがすでに認識していない限り、同様にadvanceを使用しないでください。よくわからない場合は、一度に1つずつインクリメントして、各アイテムの終わりを確認する必要があります。advanceその機能を必要としないコードのパフォーマンスが低下するため、チェックを行いません（そしてできません）。

代わりに、コードを調べて、を呼び出すとadvanceコンテナの最後から実行される理由を理解し、代わりにコードでその問題を修正してください。

もう少しコンテキストがあれば、私たちを助けるチャンスが増えるかもしれません。

于 2010-10-04T15:25:13.657 に答える