Могу ли я выполнить итерацию по элементам, которые находятся в одном диапазоне итераторов, но не в другом?

Question

Допустим, у меня есть последовательный контейнер и диапазон (пара итераторов) внутри этого контейнера элементов, которые в данный момент "активны".В какой-то момент я вычисляю новый диапазон элементов, который должен быть активным, который может перекрывать предыдущий диапазон.Затем я хочу выполнить итерацию по элементам, которые были в старом активном диапазоне, но которых нет в новом активном диапазоне, чтобы "деактивировать" их (и аналогично выполнить итерацию по элементам, которые находятся в новом диапазоне, но не в старом диапазоне, чтобы "активировать" их).

Возможно ли это?

Станет ли это проще, если я буду знать, что начало нового активного диапазона всегда будет позже в контейнере, чем начало старого активного диапазона?

Для целей вопроса предположим, что контейнер является вектором.

Answer 1

Вы можете использовать два набора для последнего активного диапазона и еще один для текущего активного диапазона.Используйте set_difference алгоритм для активации / деактивации объектов.

Answer 2

То, что вам нужно, это range_difference функция.Я подумал, что Boost.Range мог бы предоставить что-то подобное, но я ничего не нашел в их документе (ну, я не очень тщательно искал ...), поэтому я свернул свой собственный.

Следующая функция возвращает пару range, содержащую результат разности между диапазоном, обозначенным (first1,last1), и диапазоном, обозначенным (first2,last2).Предварительным условием является то, что first1 должен быть расположен до или в том же положении, что и first2.

template <typename InputIterator>
std::pair<
    std::pair<InputIterator, InputIterator>, 
    std::pair<InputIterator, InputIterator> >
range_difference(InputIterator first1, InputIterator last1,
                 InputIterator first2, InputIterator last2)
{
    typedef std::pair<InputIterator, InputIterator> Range;

    InputIterator it;

    // first1 must be <= first2
    for (it = first1 ; it != last1 && it != first2 ; ++it);

    Range left_range = std::make_pair(first1, it); // Left range

    if (it == last1) 
        return std::make_pair(left_range, std::make_pair(first2, first2));

    // it == first2
    while (it != last1 && it != last2) ++it;

    return std::make_pair(left_range, std::make_pair(it, last1)); // Right range
}

Результат разности может состоять из двух частей, если range2 полностью включен в range1.В итоге вы получаете левый диапазон и правый диапазон:

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

В этом случае функция возвращает (first1, first2),(last2, last1).

В этой другой конфигурации,

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

функция возвращает (first1, last1),(first2, first2).Существует множество других возможных конфигураций.Однако важно знать одну вещь: в случае, когда нужный диапазон пуст, он будет расположен в макс (first2, last1).Вы увидите, как это необходимо в примере.

Наконец, если first1 и first2 находятся в одной и той же позиции, возвращаемый левый диапазон будет пустым, т.е.(первый1,первый1).

Теперь, как мы можем использовать эту функцию для решения вашей проблемы?Ну, это довольно просто для диапазона "деактивировать", но немного сложнее для диапазона "активировать":

typedef std::vector<Activable>::iterator Iterator;

Iterator old_beg, old_end, new_beg, new_end; // Old and new ranges

typedef std::pair<Iterator, Iterator> Range;
typedef std::pair<Range, Range> SplitRange;

SplitRange deactivate = range_difference(old_beg, old_end, new_beg, new_end);

// Left range
for (Iterator it = deactivate.first.first;
     it != deactivate.first.second;
     ++it)
    it->deactivate();

// Right range
for (Iterator it = deactivate.second.first;
     it != deactivate.second.second;
     ++it)
    it->deactivate();


SplitRange activate = 
    range_difference(new_beg, new_end, new_beg, deactivate.second.first);
// Note the use of the previously returned right range -------^

for (Iterator it = activate.second.first;
     it != activate.second.second;
     ++it)
    it->activate();

И вот вы здесь.Возможно, это решение немного излишне для вашей проблемы, но я думаю, что range_difference функция может быть полезна во многих местах.

Answer 3

Вот простое решение:

typedef std::pair<std::vector<T>::iterator, std::vector<T>::iterator> Range;
void Update(std::vector<T>& v, Range oldActive, Range newActive)
{
    int op = 0;
    for (std::vector<T>::iterator i = v.begin(), end = v.end(); i != end; ++i)
    {
        if (i == oldActive.first) op += 1;
        if (i == oldActive.second) op -= 1;
        if (i == newActive.first) op += 2;
        if (i == newActive.second) op -= 2;
        if (op == 1) i->Deactivate();
        if (op == 2) i->Activate();
    }
}

Это намеренно ставит простоту выше эффективности в качестве отправной точки, поскольку сканирует весь вектор;с другой стороны, это однопроходный процесс, и копирование не выполняется.

Answer 4

Я думаю, что постараюсь сделать это проще:

// Iterators denoting the old and new ranges (might be cleaner to use some kind
// of typedef like James Hopkin's did, but that's not the most important)
std::vector<Activable>::iterator old_beg,
                                 old_end,
                                 new_beg,
                                 new_end;

std::vector<Activable>::iterator it;

// Deactivate
for (it = old_beg ;                   // go from the beginning of the old range
     it != old_end && it != new_beg ; // to either the end of the old one or the
     ++it)                            // beginning of the new one
    it->deactivate();

// "Jump" to the correct position
if (it == old_end) it = new_beg; // no overlap
else               it = old_end; // overlap

// Activate
for (; it != new_end ; ++it)
    it->activate();

Вы заметите, что я предположил, что новый диапазон не может быть полностью включен в старый (напримеру вас не может быть старого диапазона от индекса 4 до 10, а нового - от 5 до 7).Если это так, вам нужно будет немного изменить алгоритм.