O redimensionamento de um vector Invalidate iterators?

Question

Eu achei que este código C ++:

vector<int> a;
a.push_back(1);
a.push_back(2);
vector<int>::iterator it = a.begin();
a.push_back(4);
cout << *it;

imprimir algum número aleatório grande; mas se você adicionar a.push_back(3) entre 3ª e 4ª linhas, ele irá imprimir 1. Você pode explicar isso para mim?

Answer 1

editado com formulação mais cuidadosa

Sim, redimensionando um vetor pode invalidar todas as iteradores que apontam para o vector.

O vector é implementado através da atribuição internamente um array onde os dados são armazenados. Quando o vector cresce, essa matriz pode ficar sem espaço, e quando isso acontece, os aloca vetor uma nova, mais grande, variedade, cópias os dados para que, em seguida, exclui a matriz de idade.

Assim, seus antigos iterators, que apontam para a memória de idade, já não são válidos. Se o vector for redimensionada baixo (por exemplo, por pop_back()), no entanto, a mesma matriz é usado. A matriz nunca é reduzido automaticamente.

Uma maneira de evitar essa realocação (e ponteiro invalidação) é chamar vector::reserve() primeiro lugar, para reservar espaço suficiente para que esta cópia não é necessária. No seu caso, se você chamou a.reserve(3) antes da primeira operação push_back(), então a matriz interna seria grande o suficiente para que as do push_back pode ser realizada sem ter que realocar a matriz, e assim seus iterators permanecerá válido.

Answer 2

iterators Vector só são invalidadas quando os executa vetor uma realocação
A chamada para push_back(4) está causando o vector para alocar um novo bloco de memória -. Isso é o que faz com que seu iterador para se tornar inválido. Quando você também usar push_back(3), nenhuma realocação é realizada para push_back(4) para que o iterador permanece válido.

Answer 3

Sim, qualquer acção que possa alterar o tamanho do vector pode invalidar iteradores.

Editar: Que inclui as operações (por exemplo erase(), resize()) que reduz o tamanho do recipiente. erase() não invalida todas iteradores, mas isso não invalida qualquer iteradores que se referem a qualquer ponto após o elemento apagado (s). resize() é definido em termos de insert() e erase(), por isso tem o mesmo potencial.

Answer 4

As regras para iterador invalidação são específicos para um recipiente.

Agora invalidação pode ter 2 significados com um vector:

1. invalidação = ponto fora do intervalo definido por [início, fim]
2. Invalidação = ponto a partir do original para um objeto diferente

Como você pode ver, a segunda é muito mais rigoroso:

std::vector<int> myVector;
myVector.push_back(0);
myVector.push_back(1);

std::vector<int>::iterator it = myVector.begin(); // it points to 0
myVector.erase(it); // it points to 1
myVector.erase(it); // it == myVector.end()

Neste caso, é 'válido' em que é sempre na faixa inclusivo [início, fim] e por isso pode ser usado com segurança para qualquer operação em myVector. Por outro lado a expressão (* it) continua a mudar: primeiro ele retorna 0, 1, então ele tem um comportamento indefinido ...

Em geral, as pessoas vão preferir falar sobre a segunda exigência, e invalidar um iterador significa simplesmente que (* it) pode não produzir o mesmo resultado como antes.

---

Agora que isso é dito, existem várias maneiras de invalidar um iterador em um Vector (na verdade, é a estrutura menos estável do STL).

Durante adições de elementos:

• Isto pode provocar um realocação (1) se myVector.size () == myVector.capacity (), uma vez que a verificação é propenso a erros, nós geralmente consideram que qualquer adição irá invalidar os iteradores
• Se você quer ser 'exigente e sabe que a realocação não é acionado, então você ainda tem que se preocupar com insert. Inserindo um elemento invalida as iterators que apontam para esta posição actual e todos os subsequentes uma vez que os elementos s deslocados um passo no sentido da extremidade do vector.

Durante a remoção de elementos:

• Não há realocação, mesmo se o buffer é agora muito maior do que o necessário. É possível forçar isso, porém, usando o encolher para caber expressão (2).
• Todos iteradores que apontam passado o elemento removido são invalidados. Especialmente, o 'fim' anterior iterador é agora além do [início, fim] gama e não pode ser usado com segurança dentro de algoritmos STL, por exemplo.

(1) A estrutura interna de um std :: vector é uma matriz de T, isto é devido à compatibilidade com os programas-C (usando myVector.front & () como o endereço da matriz) e porque garante contiguidade e uma sobrecarga de espaço mínimo (isto é, a quantidade de espaço ocupado pelos dados próprios vector vs a quantidade de espaço ocupado por um objecto)

A qualquer momento, você pode saber quantos objetos um vetor pode segurar usando o método A capacidade ().

Quando você deseja inserir um objeto e o vetor não tem a capacidade necessária, uma chamada para o método .reserve (size_t) é acionado. Este método, se o número de itens necessários é superior à capacidade atual, gatilhos um realocação .

O vector então atribui um novo conjunto de elementos (o seu tamanho é geralmente de 2 * n + 1 em que n é a capacidade de corrente), copia os elementos do array de corrente para a nova matriz, as devoluções a matriz corrente.

Porque ele descarta a matriz atual, seus iteradores são invalidadas como iterators vetor são ponteiros geralmente simples (para eficiência).

Note que, se os iteradores foram implementadas como: uma referência ao vector + uma contagem, e dereferencing foi realmente * (& m_vector.front () + n) realocação não invalidaria-los ... mas seria menos eficiente.

(2) Reduzir para ajustar:. Atenção, esta desencadeia uma cópia dos elementos e invalida iterators

// myVector has 10 elements, but myVector.capacity() == 1000
myVector.swap(std::vector<int>(myVector));

O primeiro cria um vector temporária, que vai alocar apenas a quantidade de memória como é necessário (com um mínimo dependendo da biblioteca), e copiar os elementos de myVector. Em seguida, a troca operação de swap os buffers de myVector e essa cópia, e assim myVector agora HOLS um tampão com a quantidade mínima de memória necessária. No final da operação, o temporário é destruído e a memória que detém liberado.

Answer 5

Para referência futura, todos os tipos STL de petiscos como este são no site da SGI: http://www.sgi.com/tech/stl/Vector.html

Se precisar de iteradores para ficar válida depois de adicionar ou apagar a uma coleção, dar uma olhada em um outro tipo de coleção, como uma lista.

A melhor coisa a fazer, porém, é para identificar fora da matriz de características que você quer de uma coleção (acesso aleatório, etc.), em seguida, escolher o recipiente certo.

Veja o artigo da Wikipedia sobre Standard_Template_Library Contentores para um ponto de partida. Se você tiver o dinheiro, eu recomendo "STL efetiva: 50 maneiras específicas para melhorar o uso da Standard Template Library" de Scott Meyer.

Desculpas por falta de apoio links, eu sou um novato aqui e não têm a reputação de postar isso com mais de um.