Posso repetir os elementos que estão em uma gama de iteradores, mas não em outro?

Question

Vamos dizer que eu tenho um contêiner sequencial, e uma gama (par de iteradores) dentro desse recipiente de elementos que estão atualmente 'ativo'. Em algum ponto, calcular um novo conjunto de elementos que devem ser activos, que possam sobrepor-se a gama anterior. Quero, em seguida, iterar sobre os elementos que estavam no antigo gama ativa, mas que não estão na nova gama ativo para 'desactivar' eles (e da mesma forma iterar sobre os elementos que estão no novo intervalo, mas não o velho gama para 'ativar 'eles).

Isso é possível?

Se torna mais fácil se eu sei que o início da nova gama ativa será sempre no final do recipiente do que o início da antiga gama ativa?

Para efeitos da questão, assumir o recipiente é um vetor.

Answer 1

Você pode usar dois conjuntos para a última amplitude ativa e outra para a faixa ativa atual. Use o set_difference algoritmo para obter os objetos a ser ativado / desativado.

Answer 2

O que você precisa é uma função range_difference. I embora Boost.Range daria algo assim, mas eu não encontrar nada em seu doc ??(bem, eu não procurar muito bem ...), então eu rolei a minha própria.

A seguinte função retorna um par de gama, que contém o resultado da diferença entre o intervalo indicado por (first1, last1) e a uma denotado por (first2, last2). Uma pré-condição é que first1 deve ser posicionado antes ou na mesma posição como 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
}

O resultado da diferença pode ser composto de duas partes, se range2 está completamente incluído na range1. Você acaba com uma gama esquerda e uma faixa direita:

  |_____________________|__________________|________________________|    
first1                first2             last2                    last1

Neste caso, a função retorna (first1, first2), (last2, last1).

Nesta outra configuração,

  |_____________________|                 |________________________|    
first1                last1             first2                    last2

A função retorna (first1, last1), (first2, first2). Há muitas outras configurações possíveis. No entanto, uma coisa importante a saber é que, no caso em que a faixa direita está vazio, ele será posicionado em max (first2, last1) . Você vai ver como isto é necessário no exemplo.

Finalmente, se first1 e first2 estão na mesma posição, a faixa esquerda retornada será vazia, i.d. (First1, first1).

Agora, como é que podemos usar essa função para resolver o seu problema? Bem, isso é bastante fácil para a faixa "deactivate", mas um pouco mais complicado para a "ativar" um:

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

E lá vai você. Talvez esta solução é um pouco exagerado para o seu problema, mas acho que a função range_difference poderia ser útil em muitos lugar.

Answer 3

Aqui está uma solução simples:

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

Esta deliberadamente coloca simplicidade antes eficiência como um ponto de partida, uma vez que varre todo o vector; por outro lado, é única passagem e faz nenhuma cópia.

Answer 4

Eu acho que vou mantê-lo simples:

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

Você vai notar que eu assumi que a nova gama não pode ser totalmente contida no antigo (por exemplo, você não pode ter uma gama de idade indo de índice de 4 a 10, e um novo vai 5-7 ). Se este é um caso, você precisa mudar um pouco o algoritmo.