quinta-feira, 12 de fevereiro de 2015

Consulta Rápida de C++ (atualizado para C++11)

Este material eu elaborei para meus alunos de Estrutura de Dados I, do curso de Ciência da Computação da Universidade de Passo Fundo com o objetivo de ser apenas uma consulta básica e rápida, offline, da linguagem C++ para ser utilizada principalmente nas avaliações práticas da disciplina. Não é uma apostila ou material para se usar para aprender a linguagem. Para este propósito eu recomendo os livros do Deitel (C++ Como Programar), do Savitch (C++ Absoluto) ou o do Stroustrup (The C++ Programming Language), este último para quem quer conhecer a linguagem mais a fundo.


Como o bom guia publicado pela Editora Novatec (C++ - Guia de Consulta Rápida) está esgotado há muito tempo, decidi socializar este material que eu produzi aqui no blog, para quem quiser usá-lo. Já está atualizado para o C++11. Permanentemente pretendo atualizar com novos conteúdos (está faltando a classe string, por exemplo) mas sem estender demais. O formato é PDF e os termos de uso estão apresentados abaixo.

normal




Copyright Marcos José Brusso - Todos os direitos reservados

Este documento se encontra disponível em http://profbrusso.blogspot.com/2015/01/consulta-rapida-cpp.html

Você pode realizar o download deste material e imprimi-lo, ao todo ou em partes, para seu próprio uso. Qualquer outra forma de cópia, redistribuição, retransmissão ou publicação não é permitida sem o expresso consentimento do autor.

Ao fazer uso deste material você concorda em não modificar ou eliminar qualquer parte do seu conteúdo.

terça-feira, 27 de janeiro de 2015

Três alternativas para alocação dinâmica de array bidimensional (matriz) em C++

Com alguma frequencia sou consultado por alunos de outras disciplinas que estão precisando alocar dinamicamente um array 2D (matriz) em C++. Existem  diversas soluções, com suas vantagens e desvantagens. Irei apresentar algumas alternativas para criação dinâmica de uma matriz de N linhas e M colunas de um tipo T, sendo os valores de N e M conhecidos em tempo de execução.

1) Alocação dinâmica como um array de arrays


Nesta solução, alocamos um vetor com N ponteiros para T e, para cada um destes ponteiros, alocamos um array de tamanho M. Como o primeiro array a ser alocado é um vetor de ponteiros, precisamos armazenar seu endereço em um ponteiro para ponteiro para T.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>

using namespace std;

int main()
{
    int n;    cout << "N: ";     cin >> n; //Num linhas
    int m;    cout << "M: ";     cin >> m; //Num colunas

    // Aloca dinamicamente um array de N ponteiros para float
    float **mat = new float*[n];
    // Para cada um dos N ponteiros é alocado um array de M floats
    for(int i=0; i<n; ++i)
        mat[i] = new float[m];
    // TODO: testar bad_alloc em ambos os casos

    // Usa como uma matriz normal
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            mat[i][j] = (i * j)/2.0;
            cout << mat[i][j] << '\t';
        }
        cout << endl;
    }

    // Deleta o array de cada uma das linhas
    for(int i=0; i<n; ++i)
        delete[] mat[i];
    // Deleta o array de ponteiros
    delete[] mat;

    return 0;
}

Desvantagens:  a) Muito código; b) Fraca localidade de referência (localidade espacial) entre as linhas; c) Dificulta para mudar o tamanho (de qualquer dimensão) depois dela ter sido alocada;
Vantagens: a) Acesso com a notação natural de matrix [i][j]; b) Como cada linha é alocada individualmente, não precisariam ter o mesmo tamanho, ou seja, podemos ter uma matriz não retangular.

 2) Alocar como um único array


Outra alternativa é alocar como um único array de tamanho N*M. Como um array C++ sempre é contíguo na memória, podemos usar aritmética de endereços para localizar os valores dentro deste. Uma matriz seria armazenada por linhas, então primeiro temos os elementos da linha [0], depois da [1] e assim por diante. Sendo M o tamanho de cada linha, a posição m[i][j] no array bidimensional corresponde ao elemento m[i+(j*M)] em um unidimensional.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>

using namespace std;

int main()
{
    int n;    cout << "N: ";     cin >> n; //Num linhas
    int m;    cout << "M: ";     cin >> m; //Num colunas

    // Aloca dinamicamente um array de N*M floats
    // TODO: testar bad_alloc
    float *mat = new float[n*m];

    // Usa a "matriz" 
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            // m[i][j] está na memória no endereço (i+(j*m))
            mat[j + i*m] = (i * j)/2.0;
            cout << mat[j + i*m] << '\t';
        }
        cout << endl;
    }

    // Deleta o array
    delete[] mat;

    return 0;
}

Desvantagens:  a) Não usa  a notação natural de matrix [i][j]. Poderia ser criada uma classe para encapsular o código e sobrecarregar operador (int i, int j) para retornar uma referência ao elemento [i][j] ou criar um vetor de acesso indireto, com N ponteiros para o primeiro elemento de cada uma das linhas; b) A matriz precisa ser retangular; c) Dificulta mudar o tamanho (de qualquer dimensão) depois dela ter sido alocada.
Vantagens: a) Localidade de referência ótima, pois toda a matriz está sequencial na memória, da mesma forma que as matrizes "normais" (não alocadas dinamicamente). b) Mais fácil de interfacear com bibliotecas externas que aceitem matrizes tradicionais como parâmetro.

3) Criar como um vector<vector<T>>


Sempre que viável, recomendo usar os containers da STL para armazenamento de dados. Neste caso criaremos a matriz como um vector de vector de T.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;    cout << "N: ";     cin >> n; //Num linhas
    int m;    cout << "M: ";     cin >> m; //Num colunas

    // 'mat' é um vector de vector de float
    // Foi construído como um vector de N elementos, cada um deles inicializado com um vector de floats tamanho M
    vector<vector<float>> mat(n, vector<float>(m));

    // Usa como uma matriz normal
    for(int i=0; i<n; ++i)
    {
        for(int j=0; j<m; ++j)
        {
            mat[i][j] = (i * j)/2.0;
            cout << mat[i][j] << '\t';
        }
        cout << endl;
    }

    return 0;
}

Desvantagens:  a) Fraca localidade espacial;
Vantagens: a) Código conciso; b) A classe vector gerencia a memória alocada (não precisa delete); c) A matriz não precisa ser retangular. d) É possível redimensionar facilmente a matriz depois de criada. Para acrencentar um novo elemento à linha i, basta mat[i].push_back(valor); Para adicionar uma nova linha de tamanho m, basta: mat.push_back(move(vector<float>(m)));

Quanto ao uso com bibliotecas externas, existem muitas que são compatíveis com a STL então pode não ser um problema. Na própria biblioteca padrão encontramos <numeric> e <valarray> que poderiam facilmente ser aproveitadas nesta alternativa. Se a biblioteca foi criada para ter interface binária com C puro então teríamos problema de compatibilidade.  Então, não coloco este ponto nem como vantagem nem desvantagem.

Conclusão

Considerando-se as vantagens e desvantagens de cada solução a terceira alternativa se destaca e é a que eu recomendaria, a priori, sem conhecer os requisitos do problema em questão. Mas, como sempre, a melhor solução depende do caso. Se o desempenho for fundamental ou for necessário no projeto uma biblioteca como a BLAS ou MPI, aí a segunda alternativa é mais apropriada (toda a matriz poderia ser transmitida em um único MPI_Send, por exemplo).
Como quarta alternativa, caso o seu projeto já estiver usando a BOOST, ou você pretende fazer uso desta importante ferramenta, vale a pena dar uma olhada na Boost.MultiArray.

Qual vocês optam? Comentem aí!


quinta-feira, 15 de janeiro de 2015

C++14: Finalmente teremos um literal binário!

O novo standard da linguagem, C++14 já foi aprovado pelo comitê e está aguardando publicação pela ISO. Mesmo assim, diversos compiladores já estão implementando algumas das novas funcionalidades para testarmos. É uma pequena revisão na linguagem, nada radical, comparado com o C++11.

Umas das novidades que eu aguardava a mais tempo é possibilidade de codificar literais em binário. Até então tínhamos as opções de codificar literais numéricos inteiros em decimal, octal e hexadecimal:

n = 241;    // Decimal, pois inicia com dígitos 1..9
n = 0361;   // Octal, por causa do prefixo 0  (3618==24110)
n = 0xF1;   // Hexa, por causa do prefixo 0x (F116==24110)


A nova versão está incluindo um prefixo para notação de literais em binário. É o 0b (ou 0B).

n = 0b11110001;    // Binário (111100012==24110)

A notação hexadecimal é apenas uma forma abreviada de escrever valores binário e, geralmente, mais recomendada, pois temos mais chances de erros de  digitação e pior leitura em um número com 16 dígitos binários do que apenas quatro hexadecimais. Ou você prefere "1010000001010000" do que "A050"? Mesmo assim, em algumas situações específicas, os literais binários são úteis, como na criação de máscara para fazer operação and bit-a-bit a fim de testar bits individuais dentro de um número. Meus (ex-)alunos de Arquitetura e Organização de Computadores que tiveram que implementar um montador/simulador de arquitetura de 8 bits, por exemplo, poderiam ter aproveitado este recurso se já estivesse disponível.


Compilando com o gcc/g++


Como é um padrão ainda não publicado da linguagem,  está disponível apenas em caráter experimental em muitos compiladores. O GNU já tinha uma extensão para estes literais antes mesmo de ser aprovado pelo comitê.

A documentação do g++ cita que deve ser usada a chave -std=c++14, a partir do GCC 4.8. Eu, porém, para conseguir compilar no Ubuntu 14.04, com GCC 4.8.2 precisei usar a chave -std=c++1y. (com a -std=c++11 já funcionaria por causa daquela extensão).

g++ -std=c++1y testbin.cpp

1
2
3
4
5
6
7
8
9
#include <iostream>

int main()
{
    int n{0b11110001};

    std::cout << n << '\n';
    return 0;
}



segunda-feira, 12 de janeiro de 2015

E este tal de C++11? Inferência de tipo e Sintaxe (não tão) uniforme de inicialização


Seguindo com as informações iniciadas em post anterior sobre os novos recursos do C++11, veremos agora algumas das mais simples e práticas destas novidades, mesmo para programadores iniciantes.

Inferência de tipo com auto

A palavra reservada auto sempre existiu na linguagem C++ pois foi herdada das suas antecessoras. Ainda assim era uma das menos utilizadas, pois indicava que uma variável local deveria usar alocação automática. Como este é o armazenamento padrão para este caso, colocar ou omitir este modificador costumava fazer pouca diferença.

Já no C++11 foi definido outro significado bem mais útil para o auto. Agora ele é usado para declarar variáveis cujo tipo vai ser descoberto automaticamente pelo compilador a partir do valor que está sendo usado na inicialização desta variável (a inicialização é obrigatória).

auto v1=sin(1.5);   // 'v1' é um double
auto c='X';         // 'c' é um char

map<int, string> m;
auto i=m.begin();        // 'i' é um map<int, string>::iterator


Esta facilidade é mais útil quando inicializamos uma variável com o valor retornado por uma função, pois  delegamos ao compilador a tarefa de descobrir qual o tipo retornado. Principalmente no caso de iterators, que costumam ter uma declaração bem extensa.

Sintaxe uniforme de inicialização

A inicialização de variáveis em C++  pode ser feita usando-se sintaxes diferenciadas. Em alguns casos, o programador tem escolha, em outros não. Vejamos alguns exemplos:

int n=100;
int vet[]={10, 20, 30, 40};
float var(1.5);
string s("aeiou");


Nos dois primeiros casos, herdou-se da linguagem C uma sintaxe para inicialização que faz uso do mesmo símbolo do operador de atribuição (=). O primeiro exemplo é a forma clássica de inicialização para variáveis simples. O segundo caso, com os valores entre chaves,  é empregada para inicializar arrays e variáveis de estrutura.

Os dois últimos casos são uma sintaxe específica do C++, onde o valor é fornecido entre parênteses. No terceiro caso está sendo simulada a chamada de um construtor, pois não existe um construtor a ser executado visto que  float é um tipo fundamental. Já no último exemplo, a string está sendo inicializada pelo construtor da classe, com o valor passado como argumento para este construtor.

Com o objetivo de unificar as formas de inicialização, foi adicionado ao C++ uma nova sintaxe. Coloca-se o valor entre chaves, sem o símbolo de atribuição:

int n{100};
int vet[]{10, 20, 30, 40};
float var{1.5};
string s{"aeiou"};

Falando-se historicamente não me parece uma sintaxe tão nova assim, pois já era usada na linguagem B, precursora do C e portanto "avó" do C++, como pode ser visto aqui.

Com este novo formato conseguimos alguns recursos adicionais úteis, de forma que a diferença não ficou apenas na sintaxe. Ele pode ser utilizado para prevenir o narrowing, que é a atribuição de um valor de tipo mais "amplo" (em capacidade de armazenamento) para um mais "estreito", que possa levar a perda de valores. Por exemplo, usar um float para inicializar um int:

    float var;
    cin >> var;
    int a = var;  // Ok
    int b{var};   // Warning: narrowing conversion from 'float' to 'int'

Os formatos antigos aceitavam este estreitamento, mas na nova sintaxe vai gerar uma advertência. Sou da opinião que este tipo de alerta serve para construir software mais seguro. Uma das (muitas) coisas que gosto na linguagem C# é que ela impede narrowing implícito em qualquer situação (inicialização, atribuição, operações aritméticas, passagem de parâmetros, ...). Se o programador tem certeza que não vai haver perda de informação, precisa fazer um cast explícito. Como no C++ isto só vale para a inicialização, o ganho é limitado.

Outro recurso é que pode-se inicializar facilmente uma variável ou mesmo todos os elementos de um array com valor default do tipo, o que para os tipos numéricos fundamentais é 0. Basta deixar as chaves vazias, como no exemplo:

long long int bign{};   // bign=0LL;
float vet[1000]{};      // Todos os 1000 elementos com valor 0.0


Casos em que não recomendo usar:
  1. Para inicializar a variável de controle de um laço for: Em vez de for(int i{0}; ...) eu continuo escrevendo for(int i=0; ..;). Não é só pelo costume adquirido, mas por que em alguns casos eu tenho a variável de controle do loop já definida anteriormente (principalmente iterators), aí usaria apenas a atribuição. Mas aqui já é uma questão de estilo de escrita. E com o range based for disponível no C++11, esta situação é cada vez menos comum.
  2. Substituindo indiscrinadamente os parênteses na chamada de construtores, exceto construtores sem parâmetros (quando parênteses vazios não funcionam). Particularmente deve-se ter cuidado com classes que tenham construtor com initializer_list como parâmetro, pois este é o que será usado, como no exemplo comentado abaixo:
vector<int> vet(10);   // Cria um vector com 10 elementos  
vector<int> vet{10};  // Cria um vector com 1 elemento de valor 10

Não junte as duas coisas, exceto se estiver convicto!


Ansioso por usar as novidades, lá fui eu querendo escrever auto e T t{val} em todos os meus códigos. Até que compilei um arquivo com algo simples assim:

auto flag{true};

while(flag){
   // ...
}

Para mim, estava definindo uma variável bool inicializada com valor true. Mas não... Deu erro de compilação na condição do while.
Motivo: No contexto em que uma expressão entre {} puder ser usada como uma  initializer_list será isto que o compilador vai usar. Então estava definindo uma initializer_list<bool>  com um único valor igualtrue. Precisei corrigir alterando para bool flag{true};

Fica a dica! Tomando-se alguns cuidados, podemos usar os novos recursos sem medo.

sexta-feira, 2 de janeiro de 2015

Com quantos bits se faz um byte e com quantos bytes se faz um short int?

Um dos primeiros conceitos conhecidos pelo pessoal da Computação é que o bit (binary digit) é a unidade básica da informação digital correspondente a um único dígito binário (0 ou 1). Já o byte costuma ser definido como um grupo de oito bits, tradição iniciada com o IBM System 360. Este tamanho, no entanto até pode ser considerado um padrão de fato, mas não o é de direito. Vejam que o padrão IEEE 1541-2002 ("IEEE Standard for Prefixes for Binary Multiples") apenas define byte como sendo um grupo consecutivo de bits e chama de octeto o byte de 8 bits. Até onde sei, o padrão IEC 80000-13 ("Quantities and units -- Part 13: Information science and technology")  apenas recomenda que a quantidade de bits em um byte sejam oito.

No caso do C++, a especificação da linguagem define que byte é a unidade de armazenamento e terá tamanho suficiente (em bits consecutivos) para acomodar o conjunto de caracteres básicos do ambiente de execução e os 8 bits do UTF-8. Atendidos estes requisitos, cada implementação tem liberdade de definir o tamanho em bits de um byte. Ainda está previsto que o tamanho de um char, em bytes é 1 (ou seja, sizeof(char)==1). O Stroustrup, em "The C++ Programming Language" prefere descrever que o operador sizeof retorna a quantidade de chars ocupada por uma expressão ou tipo em vez de quantidade de bytes. Então, em se tratando de C++, não devemos assumir que um byte tenha 8 bits, embora este seja o caso mais comum.

O tamanho dos diversos tipos fundamentais


Não é incomum encontrarmos em materiais sobre a linguagem, até mesmo em alguns livros, tabelas especificando o tamanho em bits, ou em bytes, para os tipos de dados fundamentais da linguagem, como neste exemplo:



Em relação aos tipos inteiros, a linguagem apenas estabelece que cada um dos tipos signed char, short int, int, long int e long long int utilizam, no mínimo, o mesmo espaço de armazenamento do seu anterior nesta ordem. Ou seja, podemos resumir a regra a isto:

1 == sizeof(char) <= sizeof(short int) <= sizeof(int) <= sizeof(long int) <= sizeof(long long int)

Percebam que, embora isto seja incomum na prática, nada impede que um long long int, por exemplo, possua o mesmo tamanho, em bytes, de um short int e portanto, o mesmo intervalo de armazenamento.

Ao declararmos uma variável apenas como int, ela terá, normalmente o tamanho da palavra de máquina para aquela arquitetura e irá oferecer a aritmética mais eficiente disponível para inteiros.

Quanto aos tipos em ponto-flutuante a linguagem estabelece que existem três tipos: float, double e long double. Cada um destes, na ordem apresentada, oferece, no mínimo, a precisão do antecessor. Geralmente as implementações seguem o padrão IEEE 754-1985, e utilizam 32 bits para os números em precisão simples e 64 bits para a precisão dupla. Já a precisão extendida (long double), não é um tamanho padronizado, correspondendo, na arquitetura x86 ao formato extendido de 80 bits.

Verifique o tamanho de cada tipo em seu compilador com o código a seguir [disponível no Ideone]:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
    #include <iostream>
    using namespace std;
     
    int main() {
        cout << "signed char: " << sizeof(signed char) << endl;
        cout << "short int: " << sizeof(short int) << endl;
        cout << "int: " << sizeof(int) << endl;
        cout << "long int: " << sizeof(long int) << endl;
        cout << "long long int: " << sizeof(long long int) << endl;
     
        cout << "float: " << sizeof(float) << endl;
        cout << "double: " << sizeof(double) << endl;
        cout << "long double: " << sizeof(long double) << endl;
        return 0;
    }

Os tamanhos exatos em <cstdint>


Se precisarmos de tipos inteiros de tamanho determinado, podemos recorrer ao #include<cstdint>. Estão previstos tipos inteiros com ou sem sinal para os tamanhos de 8, 16, 32 e 64 bits, como segue:

// Com sinal
int8_t
int16_t
int32_t
int64_t
// Sem sinal
uint8_t
uint16_t
uint32_t
uint64_t

 
O padrão da linguagem, no entanto, define que estes tipos são opcionais naquele header. Ou seja, se a implementação em questão não puder oferecer algum destes tamanhos, ela pode omiti-lo, o que causaria erro de compilação nos programas que os usam.

O emprego sem critérios destes tipos podem reduzir, portanto, a portabilidade do código, o que se opõem ao objetivo de criação deste include. Devemos usa-los com precaução, apenas nos casos em que se quer a garantia de tamanho para uma determinada variável ou campo de struct ou class. Exemplos de aplicação seria onde a interface com outros dispositivos ou aplicações ocorrem em binário, como geração de arquivos binários que serão lidos por outros aplicativos ou na construção de devices drivers.