Os elementos std :: vector são garantidamente contíguos?

111

Minha pergunta é simples: os elementos std :: vector são garantidamente contíguos? Em resumo, posso usar o ponteiro para o primeiro elemento de um std :: vector como um C-array?

Se não me falha a memória, o padrão C ++ não oferecia tal garantia. No entanto, os requisitos std :: vector eram tais que era virtualmente impossível atendê-los se os elementos não fossem contíguos.

Alguém pode esclarecer isso?

Exemplo:

std::vector<int> values;
// ... fill up values

if( !values.empty() )
{
    int *array = &values[0];
    for( int i = 0; i < values.size(); ++i )
    {
        int v = array[i];
        // do something with 'v'
    }
}
Martin Cote
fonte
Eu sei que você está em apuros se sofrer uma mutação valuesdentro daquele ifbloco. Não sei a resposta para sua pergunta, entretanto, estou apenas deixando um comentário. :)
Greg D
@Greg: Que problema - você pode elaborar um pouco?
Reunanen
Suponho que ele quis dizer que o envio de novos valores pode disparar um "realocar" que tornaria o array inválido.
Martin Cote
As chamadas que sofrem mutação values, especificamente aquelas que mudam seu tamanho (por exemplo, push_back()), podem solicitar uma realocação do vetor subjacente que invalida o ponteiro para o qual foi copiado array. É o mesmo princípio por trás do uso de um vector :: iterator em vez de um ponteiro para o vetor. :)
Greg D
1
Sim, eu coloquei os `` 's em torno dos valores para tentar deixar claro que estava falando sobre a classe em si, não os valores contidos nela. :) Nomenclatura infeliz e tudo isso. Eu não acho que isso seja realmente um problema no caso geral em que esta questão é relevante - por que alguém pegaria um ponteiro para a memória e começaria a mucking com o vetor em vez de usar o ponteiro? Bobagem.
Greg D

Respostas:

118

Isso foi omitido no padrão C ++ 98 propriamente dito, mas posteriormente adicionado como parte de um TR. O próximo padrão C ++ 0x irá obviamente conter isso como um requisito.

De n2798 (rascunho de C ++ 0x):

23.2.6 Vetor de modelo de classe [vetor]

1 Um vetor é um contêiner de sequência que suporta iteradores de acesso aleatório. Além disso, ele suporta operações de inserção e exclusão de tempo constante (amortizado) no final; inserir e apagar no meio leva tempo linear. O gerenciamento de armazenamento é feito automaticamente, embora possam ser fornecidas dicas para melhorar a eficiência. Os elementos de um vetor são armazenados contiguamente, o que significa que se v é um vetor onde T é algum tipo diferente de bool, então ele obedece à identidade & v [n] == & v [0] + n para todos os 0 <= n <v .Tamanho().

diretamente
fonte
3
Isso também é afirmado na ISO 14882, 2ª edição: Seção 23.2.4 [lib.vector]: "Os elementos de um vetor são armazenados de forma contígua, o que significa que se v é um vetor <T, Alocador> onde T é algum tipo diferente bool, então ele obedece a identidade & v [n] == & v [0] + n para todos 0 <= n <v.size (). "
Mike Caron
4
so s, TR, TC, :) Na verdade, C ++ 03 também é chamado de C ++ 98-TC1 (retificação técnica) pelo que li
Johannes Schaub - litb
2
E quanto aos vetores de vetores? Os vetores internos estão logo após os vetores internos do último grupo?
huseyin tugrul buyukisik
1
@huseyin tugrul buyukisik você aprendeu a resposta para isso? Também estou me perguntando como isso funciona
David Doria
1
@huseyin tugrul buyukisik É claro que é verdade, mas são as instâncias de subsequentes std::vectorque são contíguas. Ex .: em std::vector<std::vector<int>> velementos v[0], v[1]... são armazenadas posteriormente na memória, mas o elemento v[0].back()e v[1].front()não são garantidos para ser.
jarzec
27

Como outras respostas indicaram, o conteúdo de um vetor é garantidamente contínuo (exceto pela estranheza de bool).

O comentário que eu queria adicionar é que se você fizer uma inserção ou exclusão no vetor, o que poderia fazer com que o vetor realocasse sua memória, você fará com que todos os seus ponteiros e iteradores salvos sejam invalidados.

Bill Lynch
fonte
1
Os elementos ainda estariam armazenados em um bloco de memória contíguo, apenas em um lugar diferente. A questão era especificamente sobre contiguidade.
Dima
2
Mas os ponteiros e iteradores existentes seriam invalidados.
Bill Lynch
Bom ponto. Você deve colocar isso em sua resposta para esclarecer o que quer dizer.
Dima
resposta mais útil para mim
CoffeDeveloper
Agora eu sei por que meu programa estava com falha de segmento ontem, quando fiz um loop duplo removendo certos elementos :) Obrigado!
user2891462
9

O padrão de fato garante que a vectorseja contínuo na memória e que &a[0]possa ser passado para uma Cfunção que espera um array.

A exceção a esta regra é vector<bool>que usa apenas um bit por, boolportanto, embora tenha memória contínua, ela não pode ser usada como um bool*(isso é amplamente considerado uma otimização falsa e um erro).

BTW, por que você não usa iteradores? É para isso que servem.

Motti
fonte
1
> BTW, por que você não usa iteradores? É para isso que servem. Talvez ele tenha lido o novo artigo de Alexanrescu sobre o assunto: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/…
Nemanja Trifunovic
Obrigado pelo link, vou colocá-lo na minha lista de leitura (procuro não perder os artigos do Alexandresu)
Motti
Mwahaha, todo mundo parece estar falando sobre essa apresentação nos dias de hoje. Olha, a discussão ainda está quente sobre isso: groups.google.com/group/comp.lang.c++.moderated/browse_thread/…
Johannes Schaub - litb
Se você ler cuidadosamente, o artigo de Alexandrescu não diz realmente "Não use iteradores em C ++", ele diz "Confira D". A abordagem que ele descreve nesse artigo é muito semelhante a quaisquer linguagens e frameworks existentes que absorveram a herança funcional (List, Scheme, Haskell) e eu duvido seriamente que outra sintaxe baseada em C seja um ponto de partida ideal para melhor tratamento de lista. Em algum momento do ano passado, tentei brevemente persuadi-lo a usar seus consideráveis ​​talentos para melhorar uma linguagem já estabelecida como o C #, mas temo sem sucesso! :)
Daniel Earwicker
6

Como outros já disseram, vector internamente usa uma matriz contígua de objetos. Os ponteiros para essa matriz devem ser tratados como inválidos sempre que qualquer função de membro não const for chamada de IIRC.

Contudo, há uma exceção!!

vector<bool>possui uma implementação especializada projetada para economizar espaço, de forma que cada bool use apenas um bit. A matriz subjacente não é uma matriz contígua de bool e a aritmética da matriz vector<bool>não funciona como vector<T>faria.

(Suponho que também seja possível que isso seja verdade para qualquer especialização de vetor, uma vez que sempre podemos implementar uma nova. No entanto, std::vector<bool>é a única, err, especialização padrão em que a aritmética de ponteiro simples não funciona.)

Wuggy
fonte
O usuário não tem permissão para se especializar std::vectore todos os outros vetores são obrigados a usar o armazenamento contíguo. Portanto, std::vector<bool>é (felizmente) o único vetor padrão que é estranho. (Acredito fortemente que esta especialização deve ser descontinuada e substituída, por exemplo, por um std::dynamic_bitsetcom praticamente a mesma funcionalidade. Não é uma estrutura de dados ruim, apenas não é um vetor.)
Arne Vogel
3

Eu encontrei esse segmento porque tenho um caso de uso em que vetores que usam memória contígua são uma vantagem.

Estou aprendendo a usar objetos de buffer de vértice em OpenGL. Eu criei uma classe de wrapper para conter a lógica do buffer, então tudo que preciso fazer é passar uma matriz de floats e alguns valores de configuração para criar o buffer. Quero ser capaz de gerar um buffer a partir de uma função com base na entrada do usuário, portanto, o comprimento não é conhecido no momento da compilação. Fazer algo assim seria a solução mais fácil:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

Agora posso passar os flutuadores do vetor como um array para as funções relacionadas ao buffer do OpenGL. Isso também elimina a necessidade de sizeof para determinar o comprimento da matriz.

Isso é muito melhor do que alocar um grande array para armazenar os floats e esperar que eu o torne grande o suficiente, ou fazer meu próprio array dinâmico com armazenamento contíguo.

Ninguém importante
fonte
2
esta função não faz sentido para mim. você quer dizer passar uma referência ou um ponteiro para vao invés de vsi mesmo? porque passar vsozinho fará com que uma cópia seja feita dentro da função, que deixará de existir após o término da função. Portanto, você está empurrando algo para o vetor apenas para excluí-lo quando a função terminar.
johnbakers,
1

cplusplus.com:

Os contêineres de vetor são implementados como matrizes dinâmicas; Assim como os arrays regulares, os contêineres de vetor têm seus elementos armazenados em locais de armazenamento contíguos, o que significa que seus elementos podem ser acessados ​​não apenas usando iteradores, mas também usando offsets em ponteiros regulares para os elementos.

Igor Oks
fonte
1

Sim, os elementos de um std :: vector são garantidamente contíguos.

Benoît
fonte
Certo. Acho que uso demais :)
Benoît