Puis-je itérer sur les éléments qui se trouvent dans une gamme de itérateurs, mais pas dans un autre?

Question

Disons que je suis un conteneur séquentiel, et une série (deux itérateurs) à l'intérieur de ce conteneur d'éléments qui sont actuellement « actif ». À un moment donné, je calcule une nouvelle gamme d'éléments qui devraient être actifs, qui peuvent se chevaucher la gamme précédente. Je veux itérer ensuite sur les éléments qui se trouvaient dans l'ancienne gamme active, mais qui ne sont pas dans la nouvelle gamme active pour « désactiver » les (et itérer De même sur les éléments qui se trouvent dans la nouvelle gamme, mais pas l'ancienne gamme de « activer 'eux).

Est-ce possible?

Est-il devenu plus facile si je sais que le début de la nouvelle gamme active toujours plus tard dans le récipient que le début de l'ancienne plage active?

Aux fins de la question, supposons que le conteneur est un vecteur.

Answer 1

Vous pouvez utiliser deux jeux pour la dernière plage active et une autre pour la gamme active. Utilisez le algorithme pour set_difference obtenir les objets à être activés / désactivés.

Answer 2

Qu'est-ce que vous avez besoin est une fonction range_difference. Je pensais Boost.Range fournirais quelque chose comme ça, mais je ne trouve rien dans leur doc (bien, je ne cherchais pas très bien ...), donc je roulais mon propre.

La fonction suivante retourne une paire de gamme, contenant le résultat de la différence entre la plage désignée par (Premier1, last1) et celui désigné par (first2, dernier2). Une condition préalable est que Premier1 doit être placée avant ou à la même position que 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
}

Le résultat de la différence peut être composée de deux parties, si range2 est complètement inclus dans range1. Vous vous retrouvez avec une gamme gauche et une gamme droite:

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

Dans ce cas, la fonction retourne (Premier1, first2), (dernier2, last1).

Dans cette autre configuration,

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

renvoyé par la fonction (Premier1, last1), (first2, first2). Il y a beaucoup d'autres configurations possibles. Cependant, une chose importante à savoir est que dans le cas où la gamme de droite est vide, il sera positionné à max (first2, last1) . Vous verrez comment cela est nécessaire dans l'exemple.

Enfin, si Premier1 et first2 sont à la même position, le retour gamme gauche sera vide, diamètre interne (Premier1, Premier1).

Maintenant, comment pouvons-nous utiliser cette fonction pour résoudre votre problème? Eh bien, c'est assez facile pour la gamme « désactiver », mais un peu plus délicat pour le « activate » un:

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

Et là vous allez. Peut-être que cette solution est un peu exagéré à votre problème, mais je pense que la fonction pourrait être utile <=> dans de nombreux lieu.

Answer 3

Voici une solution simple:

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

Cela met délibérément la simplicité avant l'efficacité comme point de départ, car il scanne le vecteur entier; d'autre part, il est seul passage et ne fait pas de copie.

Answer 4

Je pense que je vais le garder 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();

Vous remarquerez que je suppose que la nouvelle gamme ne pouvait pas être totalement contenue dans l'ancien (par exemple, vous ne pouvez pas avoir une vieille gamme allant de l'indice 4 à 10, et une nouvelle passe du 5 au 7 ). Si cela est un cas, vous aurez besoin de changer un peu l'algorithme.