Can I iterate over the elements that are in one range of iterators but not in another?

Question

Let's say I have a sequential container, and a range (pair of iterators) within that container of elements that are currently 'active'. At some point, I calculate a new range of elements that should be active, which may overlap the previous range. I want to then iterate over the elements that were in the old active range but that are not in the new active range to 'deactivate' them (and similarly iterate over the elements that are in the new range but not the old range to 'activate' them).

Is this possible?

Does it become easier if I know that the start of the new active range will always be later in the container than the start of the old active range?

For the purposes of the question, assume the container is a vector.

Answer 1

You can use two sets for the last active range and another for the current active range. Use the set_difference algorithm to get the objects to be activated/deactivated.

Answer 2

Here's a simple solution:

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();
    }
}

This deliberately puts simplicity before efficiency as a starting point, since it scans the entire vector; on the other hand it's single pass and does no copying.

Answer 3

I think I'll keep it simple:

// 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();

You'll note that I assumed that the new range couldn't be totally contained into the old one (e.g. you can't have an old range going from index 4 to 10, and a new one going from 5 to 7). If this is a case, you'll need to change a little the algorithm.

Answer 4

What you need is a range_difference function. I though Boost.Range would provide something like this, but I didn't find anything in their doc (well, I didn't search very thoroughly...), so I rolled up my own.

The following function returns a pair of range, containing the result of the difference between the range denoted by (first1,last1) and the one denoted by (first2,last2). A pre-condition is that first1 must be positioned before or at the same position as 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
}

The result of the difference can be composed of two parts, if range2 is completely included into range1. You end up with a left range and a right range:

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

In this case, the function returns (first1, first2),(last2, last1).

In this other configuration,

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

the function returns (first1, last1),(first2, first2). There are many other possible configurations. However, one important thing to know is that in the case where the right range is empty, it will be positioned at max(first2, last1). You'll see how this is necessary in the example.

Finally, if first1 and first2 are at the same position, the returned left range will be empty, i.d. (first1,first1).

Now, how can we use this function to solve your problem? Well that's rather easy for the "deactivate" range, but a little trickier for the "activate" one:

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

And there you go. Maybe this solution is a little overkill to your problem, but I think the range_difference function could be useful in many place.