C # equivalente ao vetor C ++, com memória contígua?

87

Qual é o equivalente em C # do vetor C ++?

Estou procurando este recurso:

Para ter uma matriz dinâmica de memória armazenada de forma contígua, sem penalidade de desempenho para acesso em comparação com matrizes padrão.

Eu estava procurando e eles dizem .NET equivalent to the vector in C++ is the ArrayList, então:

ArrayList tem esse recurso de memória contígua?

c# c++ vector Edgarmtze
fonte
4
O CLR não está suficientemente próximo do metal para você especificar (ou até mesmo esperar de forma consistente) como uma estrutura é alocada na memória?
Aphex

Respostas:

104

Você poderia usar um List<T>e quando Tfor um tipo de valor, ele será alocado na memória contígua, o que não seria o caso se Tfosse um tipo de referência.

Exemplo:

List<int> integers = new List<int>();
integers.Add(1);
integers.Add(4);
integers.Add(7);

int someElement = integers[1];
Darin Dimitrov
fonte
2
@cMinor, a documentação da List<T>classe contém muitos exemplos, mas atualizei minha resposta para incluir um.
Darin Dimitrov
5
Não estou 100% familiarizado com o CLR, mas faz sentido que, mesmo se Tfor um tipo de referência, você ainda terá memória contígua. É basicamente uma série de indicadores ...
josaphatv
"o que não seria o caso se T fosse um tipo de referência" - é tanto o caso quanto para T[]... o OP pediu "nenhuma penalidade de desempenho para acesso vs. matrizes padrão", e List<T>fornece isso. E se Tfor um tipo de referência, é análogo a T*em C ++, então você obtém tanta contiguidade quanto em C ++. Se alguém deseja que os próprios objetos sejam contíguos, então é claro que são necessários tipos de valor ... em ambas as línguas. A diferença, claro, é que em C ++ qualquer tipo pode ser usado como valor ou ref, enquanto em C # é uma propriedade do tipo por meio da distinção de classe / estrutura.
Jim Balter
Aprendi algo hoje. Achei que List<T>é sempre implementado como uma lista vinculada internamente. Então, como ele se expande dinamicamente quando chamamos Add()? Algo como o VB6 Redim Preserveque costumava copiar todo o array para um novo local?
dotNET
@dotNet, List<T>cria internamente um pequeno array T[]. Os itens internamente são adicionados ao array. Assim que o tamanho da matriz for concluído, uma nova matriz será criada com o dobro do tamanho da anterior. Os dados são copiados para o novo array maior, o menor é destruído e assim por diante. Um programador pode dar uma pista para .NET para criar uma matriz interna suficientemente grande, antes de encher a List via construtor: new List<T>(expected_array_size).
Artru
16

usar List<T>. Internamente, ele usa arrays e os arrays usam memória contígua.

Bala R
fonte
2
Não é totalmente verdade. Se T for um tipo de referência, não haverá memória contígua.
Matteo Mosca
2
@Matteo se você olhar a fonte, verá private T[] _items;que é usado para armazenamento de backend, tipo de referência ou não.
Bala R
13
Bem, eu sei disso. Mas me diga. Você tem uma Lista <SomeClass>. As referências às instâncias de SomeClass serão armazenadas na memória contígua, mas não as próprias instâncias. Como tipos de referência, eles estarão no heap e você certamente sabe como funciona o heap.
Matteo Mosca
@MatteoMosca armazenar as referências de forma contígua remove pelo menos um nível de indireção. Melhor do que nada, eu acho.
Tim Seguine
7
@MatteoMosca O OP solicitou "nenhuma penalidade de desempenho para acesso vs. matrizes padrão". Isso é verdade para List <T> independentemente de qual seja T, então todos os seus comentários nesta página são inadequados.
Jim Balter
16

Em primeiro lugar, fique longe de Arraylistou Hashtable. Essas classes devem ser consideradas obsoletas, em favor dos genéricos. Eles ainda estão no idioma para fins de legado.

Agora, o que você está procurando é a List<T>classe. Observe que se T for um tipo de valor, você terá memória contínua, mas não se T for um tipo de referência, por motivos óbvios.

Matteo Mosca
fonte
15

C # tem muitos tipos de referência. Mesmo que um contêiner armazene as referências de forma contígua, os próprios objetos podem estar espalhados pelo heap

Armen Tsirunyan
fonte