Perguntas sobre o C++/STL [RESOLVIDO]

Thihup
(usa Manjaro Linux)

Enviado em 14/04/2015 - 23:06h

E ae galera , tudo bem ?

Decidi aprimorar meus conhecimentos sobre o C++ , mas tenho algumas dúvidas / curiosidades sobre algumas coisas ;

Vamos lá :



Sei que são perguntas meio besta, mas sabe como é a curiosidade , se não pergunta aquela vontade de saber vai crescendo e te domina.

Um PS: Como utilizar o std::vector ?

Grato desde Já

Thiago

paulo1205
(usa Ubuntu)

Enviado em 15/04/2015 - 15:57h

Primeiro seria bom você entender para que servem templates. Já tem esse conhecimento?

Eu acho didático pensar através de exemplos.

Imagine um programa de controle de agência de viagens, escrito em C puro. Suponha para esse programa um modelo de dados muito, muito simples, com as seguintes entidades: pessoas, destinos (cidades), locais de hospedagem (hotéis, pousadas, albergues etc.), atrações (museus, parques, edifícios etc.) e companhias de transporte (aéreo, marítimo, fluvial e terrestre). Você até tem o apoio de um banco de dados, mas também precisa manipular em memória pequenos conjuntos desses objetos. No entanto, como você não sabe a priori quais os tamanhos desses conjuntos, em lugar de arrays, você vai trabalhar com alocação dinâmica, usando listas encadeadas para cada um dos tipos de objetos básicos mencionados acima.

Como você sabe, toda lista tem três operações básicas, que são inclusão, remoção e busca. Uma vez que você tem cinco tipos de dados para os quais deve implementar listas, você tem duas escolhas óbvias na implementação do seu programa:

a) definir cinco tipos diferentes de listas, e implementar, para cada uma delas separadamente, cada uma das três operações fundamentais (cinco tipos mais quinze funções); ou

b) definir um tipo de lista totalmente genérico (usando ponteiros para void, por exemplo), com apenas uma implementação de cada uma das operações fundamentais, mas fazendo com que essas implementações recebessem um argumento a mais, que seria um ponteiro de função encarregado de converter, no momento adequado, o ponteiro para void no tipo real de dado representado ou vice-versa (um tipo de dados para a lista com suas três funções mais algo entre cinco e quinze funções de conversão, dependendo de se será possível aproveitar a mesma função de conversão de cada tipo de dado em todas as operações fundamentais da lista ou não).

A opção (a) sugere código mais verborrágico, com a possível necessidade de reescrever várias vezes código muito parecido. Além disso, se surgirem uma sexta ou sétima entidade fundamental, ou se você quiser modelar a associação entre entidades fundamentais por meio de um tipo de dados agregador e esse tipo também tiver de ser disposto em lista, teria de copiar mais vezes ainda o código de para criar novos tipos de listas e implementar as operações básicas sobre esses novos tipos. Já a opção (b) eliminaria a quantidade de diferentes tipos de listas e poderia diminuir a quantidade de multiplicação de código quase-idêntico, mas tem a desvantagem do total desacoplamento entre o dado armazenado e o que ele representa; seria plenamente possível cometer o equívoco de se tentar incluir um hotel na lista de pessoas, e o compilador não teria como detectar esse erro.

A programação genérica, feita em C++ por meio de templates e sobrecarga de funções (particularmente funções que implementam operadores), é uma forma de abordar problemas semelhantes a esse. O programador codifica um algoritmo (função) ou tipo de dados (classe, estrutura) que tem em aberto, geralmente, o tipos de dados dos argumentos ou campos internos. Em outras partes do código, o programador usa a função ou classe genérica ao aplicar um dado concreto no lugar do argumento que tinha ficado em aberto, o que obriga o compilador a gerar o código especializado para o tipo do dado concreto que foi usado, o que ele geralmente consegue fazer automaticamente.

Essa técnica procurar reunir as vantagens de cada uma das abordagens (a) e (b) reunidas acima, a saber: pouca verborragia, reusabilidade (i.e. poder ser estendido da outros tipos de dados, inclusive tipos definidos pelo usuário) e alto acoplamento. Veja o exemplo trivial abaixo.

/* Função genérica que retorna o maior entre dois valores do mesmo tipo. */

template <typename T> const T &max(const T &a, const T &b){

  return a>b? a: b;

}



/*

  Não existe mágica (mas também não há grandes dificuldades): a função genérica

  usa uma comparação, logo, para poder ser usada com um tipo de dados qualquer,

  esse tipo tem de oferecer uma forma de comparar valores.



  Abaixo, eu crio um comparador para o tipo 'struct timeval' (em <sys/time.h>).

*/

bool operator>(const timeval &t1, const timeval &t2){

  return

    t1.tv_sec>t2.tv_sec ||

    (t1.tv_sec==t2.tv_sec && t1.tv_usec>t2.tv_usec)

  ;

}



/* Uma classe para a qual eu NÃO defino o operador ‘>’. */

class without_greater_than {

  /* ... */

};



void f(int a, int b, const timeval &t1, const timeval &t2){

  int i1, i2, i3;

  timeval tv;



  i1=max(0, 1);    // OK

  i2=max(a, b);    // OK

  tv=max(t1, t2);  // OK - reusabilidade

  i3=max(a, t1);   // Erro: violação de acoplamento de tipo

}



void g(const without_greater_than &wgt1, const without_greater_than &wgt2){

  without_greater_than wgt=max(wgt1, wgt2);  // Erro

  /* (a não existência do operador deixa de atender um requisito da programação genérica) */

} 

Dito tudo isso, espero que tenha uma ideia do valor de programação genérica.

A STL é uma biblioteca que utiliza programação genérica para suportar operações comuns a várias categorias de programas. Em particular, ela provê classes para armazenamento de dados (listas, vetores, conjuntos, filas, mapas etc.), mecanismos de iteração sobre tais dados e algoritmos genéricos que podem ser usados sobre tipos nativos ou tipos da STL (tais como busca, ordenação, particionamento etc.).



A verdadeira questão não deveria ser “por que”, mas sim “quando”. Num programa em que arrays nativos atendam perfeitamente, não há razão para trocar por std::vector ou std::array.

std::vector é mais adequado como substituto não de arrays nativos, mas de pseudo-arrays por meio de alocação dinâmica, feita em C geralmente através de malloc()/realloc()/free(). Algumas vantagens são encapsular junto com os dados armazenados os metadados necessários para seu controle e as funções (ou métodos) para manipulação desses dados (tais como insert(), push_back(), erase() etc.) e, até por causa disso, a compatibilidade com algoritmos genéricos que esperam trabalhar com um container da STL. Veja a comparação em código.

/* Programa em C, usando padrão do C de 2011. */



/* Tentativa de acoplar dados e rastreamento de tamanho. */

struct dyn_arr_SomeType {

  SomeType *data;

  size_t size;  /* nº de elementos */

};



void f(void){

  /* Declaração de array dinâmico. */

  struct dyn_arr_SomeType my_arr;



  /* XXX: neste ponto, os campos internos de my_arr têm valores indefinidos. */



  /* Alocação inicial de memória. */

  my_arr.size=100;

  my_arr.data=malloc(my_arr.size*sizeof(*my_arr.data));

  if(my_arr.data==NULL)

    abort();



  /*

    XXX: neste ponto, os elementos do array têm valores indefinidos.

         Eu poderia ter usado calloc() acima, de modo a saber que os

         elementos teriam valores correspondentes a todos os bits iguais

         a zero, mas eu vou usar realocação mais abaixo, e realloc() não

         tem a mesma propriedade de zerar os novos elementos.  Além

         disso, ter todos os bits zerados pode não fazer sentido para todo

         e qualquer tipo de dado armazenado.

  */



  /* Acrescento mais alguns elementos. */

  size_t new_size=my_arr.size+50;

  void *new_data;

  new_data=realloc(new_size*sizeof(*my_arr.data));

  if(new_data==NULL)

    abort();

  my_arr.data=new_data;

  my_arr.size=new_size;

  /*

    XXX: "beleza" de acoplamento, né? todo feito manualmente! :(

         Imagine se eu esquecesse de atualizar um dos campos...

  */



  /* Manipulação de conteúdo. */

  for(size_t n=0; n<my_arr.size; n++)

    /*

      Constrói um valor do tipo SomeType a partir do inteiro e

      grava no ponteiro para dado do tipo SomeType.  Se a

      construção falhar, retorna zero.

    */

    if(!make_SomeType_value(n, &my_arr.data[n]))

      abort();



  /*

    XXX: Antes do fim da função, é necessário liberar a memória do

         array dinâmico.  Caso contrário, o ponteiro será perdido e a

         memória para ele alocada não poderá ser recuperada.  E não

         se pode esquecer que, se o tipo de dados do elemento for

         complexo, os próprios elementos têm de ser liberados antes de

         liberar o nosso array.

  */

  for(size_t n=0; n<my_arr.size; n++)

    free_SomeType_value(&my_arr.data[n]);

  free(my_arr.data);

} 

/* Programa equivalente em C++, usando padrão do C++ de 2011. */



void f(void){

  /* Declaração de array dinâmico, já definindo tamanho inicial. */

  std::vector<SomeType> my_arr(100);



  /*

    OBS: os campos internos de std::vector não interessam, e se SomeType

         tiver um construtor default, todos os elementos já terão um valor útil

         definido, pronto para uso.  Por outro lado, se a alocação falhar ou um

         dos elementos não puder ser construído, uma exceção será disparada,

         e eu posso optar por interceptá-la (o que não faço aqui para ficar equi-

         valente ao código em C, que abortava ao detectar qualquer erro).

  */



  /* Acrescento mais alguns elementos. */

  my_arr.resize(my_arr.size()+50);

  /* Outro modo de fazer: my_arr.insert(my_arr.end(), 50, SomeType()); */



  /* Manipulação de conteúdo. */

  int i=0;

  for(auto &elem: my_arr)  // Inferência automática de tipo.

    /*

      Usa construtor de conversão de tipo de SomeType com argumento

      inteiro, supondo que uma construção que falhe vai gerar exceção.

    */

    elem=i++;  // XXX: às vezes é necessário chamar o construtor explicitamente.



  /*

    OBS: Ao fim da função, my_arr sai de escopo, invocando automaticamente

         seu destrutor, que vai se encarregar de chamar também os destrutores

         de cada elemento.  O processo de liberação acontece sem que nós pre-

         cisemos escrever uma só linha de código.

  */

} 

std::array seria um substituto direto dos arrays nativos, uma vez que não apresenta as funções de aumento ou redução de tamanho, nem inserção ou remoção de elementos. No entanto, ele traz outros métodos da STL (por exemplo: iteradores e acesso com bound checking) que podem ajudar a usar codificação mais segura ou a integração com algoritmos da STL.



Algumas das razões são as mesmas que para usar containers da STL (sobretudo std::vector) em lugar de arrays nativos ou ponteiros mais alocação dinâmica. Mas há mais, como, por exemplo:

  - sintaxe mais intuitiva em casos como o de atribuição ou comparação de valores (str="teste" e str1==str2, em lugar de strcpy(str, "teste") e strcmp(str1, str2)==0, respectivamente);
  - chance quase-zero de usar um ponteiro nulo no lugar da string (a não ser que você deliberadamente misture de forma pouco consistente std::string com ponteiros ou faça uma barbeiragem gritante do tipo “str=static_cast<const char *>(nullptr)” -- mas aí terá sido você quem pediu...);
  - possibilidade de ter uma quantidade qualquer de bytes nulos como parte da string;
  - não obrigação de lembrar de colocar um byte nulo após o final da string;
  - strings idênticas apontam internamente para os mesmos caracteres, residentes na mesma região de memória, até o momento em que uma delas for modificada; quando nenhuma delas apontar para a área original, ela será liberada;
  - integração com algoritmos genéricos da STL.



Não. Quando usado com classes, o operador new invoca um construtor (se existir) para o objeto alocado (ou objetos, se o operador for new[]). Analogamente, delete e (delete[]) invoca(m) o destrutor (se existir) do(s) objetos) que for(em) desalocado(s).

Além disso, os operadores do C++ sinalizam erros por meio de exceções, diferentemente das funções do C, que só retornam um ponteiro nulo. Isso aumenta a chance de não deixar uma falha de alocação passar despercebida, eventualmente fazendo o programa capotar mais tarde.



Eu não vejo grandes problemas nas perguntas (exceto por um aspecto, falo a respeito mais abaixo). No entanto, se de alguma maneira você se incomodar em deixar alguém julgar você pela qualidade das perguntas, existe sempre a alternativa de procurar o conhecimento em livros textos ou outros materiais de referência, e publicar apenas as dúvidas que não puderem ser sanadas com o que esses materiais apresentarem.

O que pareceu, pela forma como você perguntou alguns dos itens, é que você está colocando o carro na frente dos bois e, de certo modo, querendo meter a mão na massa com C++ sem mudar muito sua maneira de pensar, orientada a C. É uma tentação forte, dada a semelhança das duas linguagens, e eu mesmo incorri nesse erro na época dos meus primeiros contatos com C++. Por isso mesmo, eu garanto a você que é um erro.

O que eu sugiro é que você estude um pouco de C++ tentando manter o viés de C de lado. Claro que você não vai precisar reaprender a sintaxe da declaração de um inteiro ou a forma de usar um if/else, e provavelmente vai poder pular a seção ou o capítulo do livro que gasta tempo com essas questões. Mas o ponto é que uma linguagem com mecanismos muito diferentes de outra que já se conheça pode ter (e tem) formas novas de resolver velhos problemas, e nem sempre é só uma questão de sintaxe, mas sim de modo de pensar o problema e o programa desde o começo.



Pergunta complicada se você não disser o propósito dessa utilização. Ensinar tudo o que ele tem para oferecer pega um capítulo inteiro de um livro.

paulo1205
(usa Ubuntu)

Enviado em 15/04/2015 - 21:10h

Acabei de fazer algumas edições na postagem anterior, corrigindo alguns erros e acrescentando exemplos comparativos entre o uso de std::vector do C++11 e alocação dinâmica manual do C11 (nessa comparação eu não usei VLAs do C11 porque o exemplo incluía redimensionamento, coisa que um VLA não tem).

paulo1205
(usa Ubuntu)

Enviado em 15/04/2015 - 22:57h

Mais uma coisa: se você realmente quer aprender C++, eu realmente recomendo a quarta edição do The C++ Programming Language, do Bjarne Stroustrup (ninguém menos do que o criador da linguagem). Eu já gostava da terceira edição, mas a quarta está ainda melhor porque, além de cobrir o padrão de 2011 (que é o mais recente (sem contar a revisão de 2014, mas é só uma revisão); a terceira edição usava o de 1998), o Stroustrup escreve muito bem, e o formato da nova edição facilita a leitura inclusive para iniciantes.

Não sei se já existe uma edição em Português. Mesmo que exista, eu recomendo fortemente a edição em Inglês.