Неэффективно вызывать 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;
Хотя вести этот подсчет утомительно ...
EDIT:
Решение законных задач Дэвида по обобщению решений:
// 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) с такими.