كيف تتأكد من أن المتكررين لا ينتهيون ()؟

Question

لقد كنت استخدم 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

Answer 1

تقدم () الماضي () يؤدي إلى سلوك غير محدد. سيتعين عليك الاختبار كما تذهب لكل مقتطف:

  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().

Answer 2

من غير الفعال الاتصال distance أو advance على أي شيء آخر غير نماذج RandomAccessIterator: المكالمات هي o (n) حيث تمثل n المسافة.

أيضا ، list ليس حقا نموذج ل Sequence في ذلك size الطريقة غير مضمونة لتكون ثابتة (أو حتى ثابتة مطفأة) ، في الواقع يمكن أن يكون O (N) بشكل جيد.

النظر إلى الكود (وإذا لم تتمكن من استخدام أي شيء آخر غير أ list) لذلك هناك احتمالان:

• لا تستخدم تقدمًا ، ثم انقل عنصرًا واحدًا في كل مرة 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;

من الممل أن تبقي هذا العدد مستمرًا على الرغم من ...

تعديل:

معالجة مخاوف ديفيد الشرعية لتعميم الحلول:

// 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 كذلك وسيصبح مملة حقًا. على هذا النحو ، أفضّل كثيرًا الطريقة الثانية:

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) مع هذه العمليات.

Answer 3

المسافة لا يمكن أن تفعل هذا. عندما لا توفر الحاوية الخاصة بك وصولًا عشوائيًا ، فإنها تحاول الوصول إلى النهاية من خلال تقدم البداية ، مما سيؤدي إلى الخراب عند بدء تشغيله في الماضي.

يجب أن تبدأ من نقطة انطلاق صالحة (أي عن طريق التقدم في البداية ، يمكنك الوصول أخيرًا) والتحقق من المسافة قبل كل تقدم وتتقدم فقط بواسطة x <= (المسافة (الأولى ، الأخيرة) حتى لا تتغلب على الماضي.

Answer 4

إنه بسيط. لتجنب تجاوز .end() ببساطة تجنب تجاوز .end(). لا يختلف الموقف كما في تجنب الاستخدام NULL المؤشر وما إلى ذلك. بنية الكود الخاص بك بحيث لا يحدث أبدًا. على سبيل المثال ، استخدم الحلقات التي تستخدم ظروفًا مثل it != v.end() إلخ. بعض تطبيقات المكتبة القياسية الشهيرة تكتشف هذه الأخطاء وتعلمك ولكن يجب ألا تعتمد عليها ، فقط تستخدمها أثناء الاختبار/التصحيح.

تحديث

إذا لم تتمكن من التأكد من أنك تستطيع advance() بمقدار أكبر من واحد ، ثم يجب عليك ببساطة advance() بأكثر من واحد.

Answer 5

أعتقد أنك تحاول حل المشكلة الخاطئة هنا.

لا تستخدم advance بطريقة يمكن أن تؤدي إلى تجاوز end. لن تستخدم أبدًا الزيادة (شكل خاص من التقدم) عندما يشير التكرار الحالي الخاص بك إلى النهاية ، لذلك يجب ألا تستخدم التقدم أبدًا إلا إذا عرفت الكود بالفعل أن هناك عناصر متبقية كافية في الحاوية. إذا لم تكن متأكدًا ، فأنت بحاجة إلى زيادة واحدة تلو الأخرى والتحقق من النهاية على كل عنصر. advance لا (ولا يمكن) القيام بأي فحص لك لأنه سيكون أداءً للأداء للرمز الذي لا يحتاج إلى هذه الوظيفة.

بدلاً من ذلك ، قم بفحص الكود الخاص بك واكتشف سبب مكالمة إلى advance يمكن أن يتسبب في تشغيل نهاية الحاوية الخاصة بك ، وإصلاح هذه المشكلة مع التعليمات البرمجية بدلاً من ذلك.

قد يمنحنا المزيد من السياق فرصة أفضل للمساعدة.

Answer 6

لشيء واحد ، يمكنك أيضًا كتابة غلاف التكرار الذي يخزن التكرار النهائي ويتحقق من العمليات الحرجة.

على سبيل المثال باستخدام Boost's 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());
}