Matrizes Dinâmicas

Matrizes Dinâmicas
Escrito por Bruno Crivelari Sanches

Voltando um pouco as bases vamos analisar neste tutorial algumas possibilidades para criação de matrizes dinâmicas usando C++. Tem sido bem comum em fóruns e listas de emails o pessoal dar cabeçada com esse problema, neste tutorial vou apresentar as soluções mais conhecidas e as características de cada uma.

Alocando cada Linha

A técnica que parece ser a mais popular é alocar um vetor de ponteiros e depois alocar uma linha da matriz para cada ponteiro deste vetor:

int main(int, char **)
{
    int nlinhas = 5;
    int ncol = 5;
    int **mat = new int*[nlinhas];

    for(int i = 0;i < nlinhas; ++i)
        mat[i] = new int[ncol];

    //iniciando ela com zero
    for(int i = 0;i < nlinhas; ++i)
        for(int j = 0;j < ncol; ++j)
            mat[i][j] = 0;

    //liberar memória
    for(int i = 0;i < nlinhas; ++i)
        delete []mat[i];

    delete []mat;     

    return 0;
}

O problema dessa técnica é o grande desperdício de espaço e tempo que ela gera. O desempenho desta é o pior, principalmente pelo fato de serem necessárias varias alocações e alocações de memória em C/C++ são operações que costumam ser bem caras.

Mesmo ignorando o tempo de criação da matriz, o uso dela também vai ser comprometido devido a possibilidade de cada linha dela estar numa região de memória diferente e é bem provável que o cache do processador tenha dificuldades em se manter atualizado por causa disso.

Já o desperdício de espaço ocorre devido a necessidade de se realizar varias alocações e é comum cada alocação precisa alocar um pouco mais de espaço do que o requisitado para a estrutura de controle usada internamente para gerenciar a memória.

A única vantagem em utilizar este método é quando precisamos de uma matriz absurdamente grande e alocamos cada linha apenas quando existe necessidade, mas mesmo nesse caso acredito que existam técnicas melhores para se implementar uma matriz esparsa.

Usando Apenas um Vetor

Uma maneira mais simples de se implementar uma matriz é utilizando apenas um vetor e realizar o acesso dos elementos como se fossem uma matriz:

int main(int, char **)
{
    int nlinhas = 5;
    int ncol = 3;

    //alocando a "matriz"
    int *mat = new int[nlinhas * ncol];

    //colocando 5 na linha 3, coluna 2
    mat[3 * ncol + 2] = 5;

    //liberando a memoria
    delete []mat;

    return 0;
}

Note como o código nesse caso é muito mais simples que o anterior, o único incomodo deste código é a necessidade de armazenar o tamanho da matriz (o número de linhas para ser mais preciso) e ficar passando ele como parâmetro a todo momento na hora de acessar um elemento, mas não é nada complicado criar uma classe para encapsular isso.

Para acessar um elemento usamos a fórmula: elem[linha * ncol + col], onde linha é o numero da linha que se quer acessar, ncol o número de colunas da matriz e col o número da coluna que se deseja acessar.

Como é feita apenas uma alocação é usado o minimo de memória possível, além de deixar o cache feliz na hora de acessar os dados.

Utilizando std::vector

Por fim, podemos utilizar o std::vector e não precisamos assim nos preocupar mais em gerenciar a memória da matriz e deixar o programa mais alinhado com o RAII:

#include <iostream>
#include <vector>

int main(int, char **)
{
    int ncol = 4;
    int nlinha = 3;

    std::vector mat(ncol * nlinha);

    //acessando elemento 2, 1 (linha 2, coluna 1)
    mat[2 * nlinha + 1] = -1;

    std::cout << mat[2 * nlinha + 0] << std::endl;
    std::cout << mat[2 * nlinha + 1] << std::endl;

    return 0;
}

Esse código é muito semelhante ao anterior, mas as operações de gerenciamento de memória foram encapsuladas com o uso de um std::vector, utilizando-se uma boa implementação de std::vector não deve existir diferença alguma de performance e uma diferença minima de consumo de memória entre este exemplo e o anterior.

Esta é a maneira mais simples que conheço para lidar com matrizes dinâmicas, mas o ideal mesmo seria construir uma template que encapsule estas operações, mas isto fica para um outro tutorial.

Adicionar novo

Comentários (15)

06/11/2009 09:13:20 |201.86.82.xxx| Adriano Waltrick - Muito bom

Primeiro.. parabéns pelo site!
Estive olhando os tutorias e estou gostando muito!

Excelente tutorial esse sobre matrizes, eu mesmo não fazia idéia dessa técnica de índices.

Usando vector então, show de bola!
Obrigado pelo excelente tutorial!

Responder Citar

22/10/2010 17:59:00 |189.45.194.xxx| adriano josé waltrick

OI adriano.voce tem mesmo nome que eu

Responder Citar

12/03/2010 15:22:07 |200.151.92.xxx| gokernel

Olá Bruno.

Também dou os parabéns pelo site, principalmente por tratar de um assunto do qual no momento estou interessado.

Estou usando esse tipo de dado para criar uma CLIST(Lista com colunas).
---------------------------------------------
struct AS_clist_str { // 8 Bytes

char *text;

struct AS_clist_str *str_next;

};

struct AS_clist_iten { // 8 Bytes

struct AS_clist_str *str_first;

struct AS_clist_iten *iten_next;

};
---------------------------------------------

E vejo que esse modelo consome "muita" memoria, então venho pedir a sua opinião sobre este outro,
e saber se é possível algumas vezes criar "dados" com o número de colunas diferentes, e como.

---------------------------------------------
struct AS_clist_iten { // 8 Bytes

char **text;

struct AS_clist_iten *iten_next;

};
---------------------------------------------

OBS: Os dados(números de "linhas" e "colunas" são desconhecidos.

Espero que tinha sido +ou- claro.

Abraços.

gokernel
gokernel@hotmai.com

Responder Citar

12/03/2010 15:34:16 | Bruno Crivelari Sanches

Olá gokernel,

obrigado.

Sobre a nova estrutura você pretende usar um vetor dinâmico? Nesse caso eu sugiro usar um std::vector mesmo, como sugerido na ultima parte do artigo.

Provavelmente você vai ter que implementar mais de uma técnica e ver qual se sai melhor na sua aplicação.

Responder Citar

12/03/2010 18:16:16 |201.12.130.xxx| gokernel

Olá Bruno.

Bruno disse:
------------------------------------------------
Sobre a nova estrutura você pretende usar um vetor dinâmico? Nesse caso eu sugiro usar um std::vector mesmo, como sugerido na ultima parte do artigo.
------------------------------------------------

std::vector... num rola.

Infelizmente não dá, pois entre os compiladores que uso o LCC é somente C.

Mas deste novo modo que mostrei, testei e ficou melhor/mais_economico em relação ao uso de memória.

Abraços.

gokernel
gokernel@hotmail.com

Responder Citar

12/03/2010 18:25:03 | Bruno Crivelari Sanches

Não sabia que era código C puro, nesse caso nada como o bom e velho malloc .

Responder Citar

24/03/2010 16:00:49 |200.151.92.xxx| gokernel

Baseado no que aqui foi exposto...

Este programa esta correto?

// Programa somente C PURO.

#include
#include
#include

struct COLUNA {
char *text;

short
size,
center,
space;
};

struct COLUNA **criar_colunas (int count) {
int cc;
char str[80];
struct COLUNA **col;

col = (struct COLUNA**) malloc( sizeof(struct COLUNA*) * count );

for(cc=0; cc < count; cc++) {

sprintf(str, "ISTO EH UM TESTE --- e finalizando: COLUNA[%d]", cc);

col[cc] = malloc( sizeof(struct COLUNA) );
col[cc]->text = strdup(str);
col[cc]->size = 100;
col[cc]->center = 0;
col[cc]->space = 16;
}

return col;
}

#define TAMANHO 30

int main () {
int cc; // Counter.
struct COLUNA **my_col;

my_col = criar_colunas ( TAMANHO );

printf("-------------------------------------------\n";
for(cc=0; cc < TAMANHO; cc++)
printf("RESULT >>: %s\n", my_col[cc]->text);

printf("-------------------------------------------\n";
printf("Aparentemente esta tudo correndo bem, antao... HELLO WORLD\n";

return 0;
}

Responder Citar

24/03/2010 16:04:35 | Bruno Crivelari Sanches

Depende do que você quer fazer, se a intenção era alocar um array de ponteiros e alocar uma estrutura para cada ponteiro do array esta certo sim.

Era para ser uma matriz?

Responder Citar

24/03/2010 17:30:47 |189.71.74.xxx| Anônimo - re:

Bruno Crivelari Sanches Escreveu:
Depende do que você quer fazer, se a intenção era alocar um array de ponteiros e alocar uma estrutura para cada ponteiro do array esta certo sim.

Era para ser uma matriz?
RESPOSTA:
Era uma arrray.

Agora qual a direfença se fosse uma matriz?

Faria diferença?

gokernel
gokernel@hotmail.com

Responder Citar

24/03/2010 18:19:08 | Bruno Crivelari Sanches

A diferença é que você aloca memória demais.

Pois você aloca um array de ponteiros, depois uma estrutura para cada um, seria muito mais simples alocar apenas um array de estruturas e trabalhar com elas.

Curiosidade, porque você não usa C++?

Responder Citar

25/03/2010 08:59:02 |200.151.92.xxx| gokernel

Só acrescentando...

Estão nos planos portar a libAS para uso com LUA(Embedded):
http://www.eluaproject.net/pt_status.html

Imagina só em um futuro próximo usar essa por exemplo em um RECEPTOR DE TV DIGITAL.

Lógico precisa o porte da parte gráfica.

gokernel
gokernel@hotmail.com

Responder Citar

25/03/2010 07:12:18 |200.151.92.xxx| gokernel

Bruno disse:
-------------------------------------------------
Curiosidade, porque você não usa C++?
-------------------------------------------------

Eu uso C++ sim, mas somente com o:
01 - Borland C++ Builder.
02 - Bibliotecas QT e FLTK.

Agora para o meu projeto libAS(ALLEGRO ou SDL), que programo como Hobby uso apenas C PURO pois esse também eh compilado usando o LCC e para MS-DOS(não consigo instalar correto o DJGPP com C++).

Abraços.

gokernel
gokernel@hotmail.com

Responder Citar

25/03/2010 09:14:21 | Bruno Crivelari Sanches

Bacana! Tem site sobre o projeto?

Responder Citar

25/03/2010 17:44:24 |201.12.130.xxx| gokernel

Atualmente estou REESCREVENDO a libAS Ver 0.6.0 e no dia 30/03/2010 estarei lançando oficialmente... pois conpletará 1 ANO... VIVA \o/.

Mas quem quiser antes eh só solicitar via E-MAIL.

A versão 0.5.2 pode conferir aqui:
http://sourceforge.net/projects/libas/files/

DEPENDENCIA:
ALLEGRO ou SDL.
LUA 5.1.4.

Lembrando o programa AS-IDE 0.6.0 cria e executa OBJETOS EM TEMPO REAL.

gokernel
gokernel@hotmail.com

Responder Citar