1 of 150

Programação genérica e�STL (Standard Template Library)

1

2 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

2

3 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

Alexander Stepanov é a principal pessoa por trás da STL.

3

4 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

Alexander Stepanov é a principal pessoa por trás da STL.
A STL não segue o paradigma de orientação o objeto.
Interface de um único tipo que se comporta polimorficamente.

4

5 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

Alexander Stepanov é a principal pessoa por trás da STL.
A STL não segue o paradigma de orientação o objeto.
Interface de um único tipo que se comporta polimorficamente.
A STL adota o paradigma de programação genérica.
Algoritmos vêm em primeiro lugar e a interface é replicada entre tipos.

5

6 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

Alexander Stepanov é a principal pessoa por trás da STL.
A STL não segue o paradigma de orientação o objeto.
Interface de um único tipo que se comporta polimorficamente.
A STL adota o paradigma de programação genérica.
Algoritmos vêm em primeiro lugar e a interface é replicada entre tipos.
David Musser e Matthew Austern também participaram da concepção da STL.

6

7 of 150

Desorientação a objeto

"I find OOP technically unsound... It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras... I find OOP philosophically unsound. It claims that everything is an object - saying that everything is an object is saying nothing at all."

Alexander Stepanov é a principal pessoa por trás da STL.
A STL não segue o paradigma de orientação o objeto.
Interface de um único tipo que se comporta polimorficamente.
A STL adota o paradigma de programação genérica.
Algoritmos vêm em primeiro lugar e a interface é replicada entre tipos.
David Musser e Matthew Austern também participaram da concepção da STL.
Em C++, programação genérica é concretizada via templates.

7

8 of 150

Programação genérica

O foco da programação genérica é projetar algoritmos eficientes que operam sobre representações abstratas. A essência desse processo, chamado de lifting, é encontrar os requisitos mínimos que tipos concretos devem satisfazer para permitir a álgebra necessária sobre as estruturas de dados.

Considere duas funções que somam os elementos de um array, uma para int, outra para float.

8

9 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.

9

10 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting...

10

11 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído.

11

12 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim:
T precisa permitir inicialização a partir do int 0.

12

13 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim:
T precisa permitir inicialização a partir do int 0.
T deve suportar a operação de adição.

13

14 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim:
T precisa permitir inicialização a partir do int 0.
T deve suportar a operação de adição.
E também a operação de atribuição.

14

15 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim:
T precisa permitir inicialização a partir do int 0.
T deve suportar a operação de adição.
E também a operação de atribuição.
Por fim, T tem que ser copiável.

15

16 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim, há requisitos em T.
Mas não paramos por aí, uma implementação genérica deve ser… genérica, certo?
Como seria um sum (onde adição denota concatenação) de string?

16

17 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim, há requisitos em T.
Mas não paramos por aí, uma implementação genérica deve ser… genérica, certo?
Como seria um sum (onde adição denota concatenação) de string?

17

Nossa abstração não está completa!

18 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim, há requisitos em T.
Mas não paramos por aí, uma implementação genérica deve ser… genérica, certo?
Então, precisamos abstrair também o valor de inicialização.

18

Válido apenas para numéricos.

19 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora uma implementação em que o tipo concreto foi abstraído. Ainda assim, há requisitos em T.
Mas não paramos por aí, uma implementação genérica deve ser… genérica, certo?
Então, precisamos abstrair também o valor de inicialização.

19

Genérico!

20 of 150

Lifting

Considere duas funções que somam os elementos de um array, uma para int, outra para float.
A única diferença é o tipo sobre o qual elas operam, mas o algoritmo é exatamente o mesmo.
Vamos fazer o lifting…
Temos agora um implementação em que o tipo foi abstraído, mas não um T qualquer…
Mas não paramos por aí, uma implementação genérica deve ser… genérica, certo?
Então, precisamos abstrair também o valor de inicialização.

O processo de lifting continua, iterativamente, até que atinjamos a genericidade desejada.

20

21 of 150

Concepts

Ao longo do processo de lifting de uma implementação, os requisitos impostos a tipos aumentam. Eventualmente, podemos agrupá-los em uma entidade própria chamada de concept (conceito).

21

Concept	Requirement
DefaultConstructible<T>	T must have a default constructor.
CopyConstructible<T>	T must have a copy constructor.
CopyAssignable<T>	T must have a copy assignment operator.
Addable<T>	T must support operator+ among two T values returning T.

22 of 150

Concepts

Ao longo do processo de lifting de uma implementação, os requisitos impostos a tipos aumentam. Eventualmente, podemos agrupá-los em uma entidade própria chamada de concept (conceito).

A quantidade de requisitos que um conceito deve "empacotar" varia. Assim como em classes, é possível compor ou refinar conceitos através de outros já existentes.

22

Concept	Requirement
DefaultConstructible<T>	T must have a default constructor.
CopyConstructible<T>	T must have a copy constructor.
CopyAssignable<T>	T must have a copy assignment operator.
Addable<T>	T must support operator+ among two T values returning T.

Concept	Requirement
Summable<T>	DefaultConstructible<T>, CopyConstructible<T>, CopyAssignable<T>, Addable<T>

23 of 150

Concepts

Conceitos são o coração da STL…

23

	Concept	Requirement
	Container<T>	Um armazém (com posse) de elementos; sem ordem definida; etc.
	Sequence<T>	Refina container; impõe ordem linear de elementos; permite inserção/ remoção; etc.
	AssociativeContainer<T>	Também refina container; baseado em operações de chave/valor; etc.
	…	…
	TrivialIterator<T>	Um iterador básico para atravessar contêineres; etc.
	InputIterator<T>	Refina iterator; permite dereferenciação para ler do contêiner; etc.
	OutputIterator<T>	Também refina iterator; permite dereferenciação para escrever no contêiner; etc.
	…	…
	Generator<T>	Um objeto que pode ser invocado como função, sem parâmetros.
	UnaryFunction<T>	Um objeto que pode ser invocado como função, recebendo um parâmetro.
	Predicate<T>	Um objeto que pode ser invocado, recebendo um parâmetro, retornando bool¹.
	…

Containers

Iterators

Functors

1) Estritamente dizendo, o tipo de retorno deve ser conversível para bool.

24 of 150

Tipos associados a concepts

É comum que abstrações necessitem de informações adicionais a respeito de um conceito para implementar determinada operação. Exemplo: Qual o tipo do elemento de um contêiner?

24

25 of 150

Tipos associados a concepts

É comum que abstrações necessitem de informações adicionais a respeito de um conceito para implementar determinada operação. Exemplo: Qual o tipo do elemento de um contêiner?

Por isso, conceitos frequentemente exigem, além de interfaces, que tipos sejam associados a suas definições. Por exemplo, Container<T> exporta, entre outros, os seguintes tipos associados.

25

Tipo Associado	Significado
ContainerT::value_type	Tipo do elemento armazenado.
ContainerT::iterator	Tipo do iterator usado nesse contêiner.
ContainerT::reference_type	Tipo que se comporta como referência - normalmente &T, mas pode variar com endereçamentos "especiais" de memória.
ContainerT::pointer_type	Tipo que se comporta como ponteiro - normalmente T*, mas pode ser usado para proxies.
ContainerT::size_type	Tipo que representa o número de elementos no contêiner.

26 of 150

Tipos associados a concepts

É comum que abstrações necessitem de informações adicionais a respeito de um conceito para implementar determinada operação. Exemplo: Qual o tipo do elemento de um contêiner?

Por isso, conceitos frequentemente exigem, além de interfaces, que tipos sejam associados a suas definições. Por exemplo, Container<T> exporta, entre outros, os seguintes tipos associados.

26

Tipo Associado	Significado
ContainerT::value_type	Tipo do elemento armazenado.
ContainerT::iterator	Tipo do iterator usado nesse contêiner.
ContainerT::reference_type	Tipo que se comporta como referência - normalmente &T, mas pode variar com endereçamentos "especiais" de memória.
ContainerT::pointer_type	Tipo que se comporta como ponteiro - normalmente T*, mas pode ser usado para proxies.
ContainerT::size_type	Tipo que representa o número de elementos no contêiner.

27 of 150

Modelando um conceito

É claro… Uma implementação genérica não depende apenas de um "conceito". No fim das contas, precisamos de tipos concretos como argumentos. Tais tipos devem modelar determinado conceito.

Tipos primitivos automaticamente modelam nosso conceito Summable<T>.
Para conceitos mais complexos, como o de um RandomAccessContainer<T>, a implementação de uma classe é necessária. Conhecemos várias da STL...

27

Container

RandomAccessContainer

Sorted�AssociativeContainer

Associative�Container

Reversible�Container

Forward�Container

Sequence

BackInsertion�Sequence

UniqueSorted�AssociativeContainer

PairAssociative�Container

Unique�AssociativeContainer

std::vector

std::map

28 of 150

Conceitos (ainda) não existem na linguagem

Conceitos não são cidadãos de primeira-classe em C++, atualmente são apenas "documentação". Houve algumas tentativas de incorporá-los nativamente. Porém... foram todas frustradas.

A primeira proposta de conceitos, projetada por várias pessoas e liderada por Douglas Gregor, quase entrou em C++11. Chegou a fazer parte do draft, mas foi excluída na "última hora".
Uma das críticas dessa versão, implementada no ConceptGCC, foi a complexidade dos concept-map e arquétipos. Então, Stroustrup e Andy Sutter resolveram investir em uma versão simplificada.
A "nova" proposta ficou conhecida como Concepts Lite e era prevista para C++17. Porém, acabou ficando de fora. Um dos problemas foi a ausência da especificação de conceitos para componentes da biblioteca padrão. Ainda que a implementação estivesse pronta em um branch do GCC.

28

29 of 150

Conceitos (ainda) não existem na linguagem

Conceitos não são cidadãos de primeira-classe em C++, atualmente são apenas "documentação". Houve algumas tentativas de incorporá-los nativamente. Porém... foram todas frustradas.

A primeira proposta de conceitos, projetada por várias pessoas e liderada por Douglas Gregor, quase entrou em C++11. Chegou a fazer parte do draft, mas foi excluída na "última hora".
Uma das críticas dessa versão, implementada no ConceptGCC, foi a complexidade dos concept-map e arquétipos. Então, Stroustrup e Andy Sutter resolveram investir em uma versão simplificada.
A "nova" proposta ficou conhecida como Concepts Lite e era prevista para C++17. Porém, acabou ficando de fora. Um dos problemas foi a ausência da especificação de conceitos para componentes da biblioteca padrão. Ainda que a implementação estivesse pronta em um branch do GCC.

Eventualmente, com a introdução de conceitos (algum dia), escreveremos código assim:

Versão curta

Versão com requires

29

30 of 150

Conceitos (ainda) não existem na linguagem

Mas qual é exatamente a diferença entre as versões de sort com e sem conceito?

Versão curta

Versão com requires

Versão template pura

30

31 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.

31

32 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.
Porém, a motivação original e talvez mais importante para a introdução de concepts é melhorar a inteligibilidade (ou simplificação) dos erros de compilação com templates.

32

Qual o erro desse programa?

Continua...

33 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.
Porém, a motivação original e talvez mais importante para a introdução de concepts é melhorar a inteligibilidade (ou simplificação) dos erros de compilação com templates.

O motivo dessas "monstruosidades" no diagnóstico é o seguinte:

Ao encontrar um template de função (ou de classe), o compilador realiza uma primeira passada para verificação básica de sintaxe em nomes não-dependentes.
Posteriormente, perante um uso do template em questão, o compilador realiza sua instanciação, substituindo os parâmetros T por tipos concretos.

33

O que é um dependent name?

34 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.
Porém, a motivação original e talvez mais importante para a introdução de concepts é melhorar a inteligibilidade (ou simplificação) dos erros de compilação com templates.

O motivo dessas "monstruosidades" no diagnóstico é o seguinte:

Ao encontrar um template de função (ou de classe), o compilador realiza uma primeira passada para verificação básica de sintaxe em nomes não-dependentes.
Posteriormente, perante um uso do template em questão, o compilador realiza sua instanciação, substituindo os parâmetros T por tipos concretos.

Apenas nesse momento certos erros são encontrados!

34

O que é um dependent name?

35 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.
Porém, a motivação original e talvez mais importante para a introdução de concepts é melhorar a inteligibilidade (ou simplificação) dos erros de compilação com templates.

O motivo dessas "monstruosidades" no diagnóstico é o seguinte:

Ao encontrar um template de função (ou de classe), o compilador realiza uma primeira passada para verificação básica de sintaxe em nomes não-dependentes.
Posteriormente, perante um uso do template em questão, o compilador realiza sua instanciação, substituindo os parâmetros T por tipos concretos.

Apenas nesse momento certos erros são encontrados!

Como consequência, o diagnóstico aponta para a implementação do template, enquanto que a causa real do erro está no seu Point Of Instantiation (POI).

35

O que é um dependent name?

36 of 150

O por quê de concepts

A primeira vantagem do suporte, em nível de linguagem, para concepts é expressividade.
Porém, a motivação original e talvez mais importante para a introdução de concepts é melhorar a inteligibilidade (ou simplificação) dos erros de compilação com templates.
Enquanto os conceitos não forem adotados em C++, temos algumas opções:
Utilizar uma biblioteca de "concept-check" (ou escrever a nossa própria).
Restringir a verificação apenas em componentes da STL (quando disponível).
Depender de ferramenta externa para decifrar os erros de templates.
Ser foda e aprender a entender as mensagens obscuras.
Ser mais foda ainda e nunca produzir um erro de compilação.

36

37 of 150

Técnicas de templates: especialização

Especialização: instanciação customizada de templates.

Ao encontrar Arithmetics<int>, Arithmetics<short>, etc, o compilador instanciará o template automaticamente utilizando a implementação padrão.

37

38 of 150

Técnicas de templates: especialização

Especialização: instanciação customizada de templates.

Ao encontrar Arithmetics<int>, Arithmetics<short>, etc, o compilador instanciará o template automaticamente utilizando a implementação padrão.
E se houver uma versão especial de divisão de double? Podemos definir uma especialização!

38

39 of 150

Técnicas de templates: especialização

Especialização: instanciação customizada de templates.

Ao encontrar Arithmetics<int>, Arithmetics<short>, etc, o compilador instanciará o template automaticamente utilizando a implementação padrão.
E se houver uma versão especial de divisão de double? Podemos definir uma especialização!
Ah… templates de classes podem ser parcialmente especializadas (de funções, não).

39

O que é um parâmetro não-tipo de template?

40 of 150

Técnicas de templates: especialização

Especialização: instanciação customizada de templates.

Ao encontrar Arithmetics<int>, Arithmetics<short>, etc, o compilador instanciará o template automaticamente utilizando a implementação padrão.
E se houver uma versão especial de divisão de double? Podemos definir uma especialização!
Ah… templates de classes podem ser parcialmente especializadas (de funções, não).
Não se esqueça, templates também podem ter parâmetros default.

40

41 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.

41

42 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.
Uma dessas propriedades é a categoria do iterator: iterator_category.

42

43 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.
Uma dessas propriedades é a categoria do iterator: iterator_category.
A seguintes categorias estão disponíveis na STL, cada uma representada por uma classe vazia.

43

44 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.
Uma dessas propriedades é a categoria do iterator: iterator_category.
A seguintes categorias estão disponíveis na STL, cada uma representada por uma classe vazia.
Como exemplo, o iterador de std::vector, uma especialização de std::iterator_traits para ponteiros, é definido com a categoria random_access_iterator_tag_t.

44

45 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.
Uma dessas propriedades é a categoria do iterator: iterator_category.
A seguintes categorias estão disponíveis na STL, cada uma representada por uma classe vazia.
Como exemplo, o iterador de std::vector, uma especialização de std::iterator_traits para ponteiros, é definido com a categoria random_access_iterator_tag_t.

45

46 of 150

Técnicas de templates: traits

Traits: associação, em tempo de compilação, de informações sobre tipos.

std::iterator_traits armazena propriedades do tipo do iterador de determinado contêiner.
Uma dessas propriedades é a categoria do iterator: iterator_category.
A seguintes categorias estão disponíveis na STL, cada uma representada por uma classe vazia.
Como exemplo, o iterador de std::vector, uma especialização de std::iterator_traits para ponteiros, é definido com a categoria random_access_iterator_tag_t.

46

47 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.

47

48 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Podemos implementá-la invocando ++it repetidamente, já que essa é uma expressão suportada por todos iteradores de entrada, os quais modelam InputIterator<T>.

48

49 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Podemos implementá-la invocando ++it repetidamente, já que essa é uma expressão suportada por todos iteradores de entrada, os quais modelam InputIterator<T>.
Mas para iteradores que modelam RandomAccessIterator<T> existe uma maneira mais eficiente: simplemente some n ao iterador.

49

50 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Podemos implementá-la invocando ++it repetidamente, já que essa é uma expressão suportada por todos iteradores de entrada, os quais modelam InputIterator<T>.
Mas para iteradores que modelam RandomAccessIterator<T> existe uma maneira mais eficiente: simplemente some n ao iterador.
Porém, devemos restringir essa versão de std::advance apenas para essa categoria de iteradores.

50

51 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Podemos implementá-la invocando ++it repetidamente, já que essa é uma expressão suportada por todos iteradores de entrada, os quais modelam InputIterator<T>.
Mas para iteradores que modelam RandomAccessIterator<T> existe uma maneira mais eficiente: simplemente some n ao iterador.
Porém, devemos restringir essa versão de std::advance apenas para essa categoria de iteradores.
Então, usamos std::iterator_traits para criar sobrecargas alternativas.

51

52 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Para implementá-la corretamente precisamos conhecer a categoria do iterador. Invocar ++it repetidamente é uma opção, já que é uma expressão suportada por InputIterator<T>.
Mas para iteradores que modelam RandomAccessIterator<T> existe uma maneira mais eficiente: simplemente some n ao iterador.
Porém, devemos restringir essa versão de std::advance apenas para essa categoria de iteradores.
Então, usamos std::iterator_traits para criar sobrecargas alternativas.

52

53 of 150

Técnicas de templates: tag dispatching

Tag dispatching: distinção de comportamento via sobrecarga baseada em propriedades de tipos.

Considere a função std::advance, a qual incrementa n vezes um iterador.
Para implementá-la corretamente precisamos conhecer a categoria do iterador. Invocar ++it repetidamente é uma opção, já que é uma expressão suportada por InputIterator<T>.
Mas para iteradores que modelam RandomAccessIterator<T> existe uma maneira mais eficiente: simplemente some n ao iterador.
Porém, devemos restringir essa versão de std::advance apenas para essa categoria de iteradores.
Então, usamos std::iterator_traits para criar sobrecargas alternativas.

53

54 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo¹.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.

1) Similar ao design pattern Template Method do GoF.

54

55 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.

55

56 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.

56

57 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.

57

58 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.
Mas muitas vezes, ambos andam acompanhados…

58

59 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.
Mas muitas vezes, ambos andam acompanhados…

59

60 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.
Mas muitas vezes, ambos andam acompanhados…
Um exemplo de política na STL é o allocator dos contêineres. Por padrão, std::allocator.

60

61 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.
Mas muitas vezes, ambos andam acompanhados…
Um exemplo de política na STL é o allocator dos contêineres. Por padrão, std::allocator.
Se precisamos de alocação/desalocação customizadas (diferente de new/delete), devemos definir nosso próprio alocador e passá-lo como argumento para os templates da STL.

61

62 of 150

Técnicas de templates: policy classes

Policy classes: configuração de comportamento interno a um algoritmo.

A "casca" da implementação é a mesma, mas parte do comportamento é parametrizável.
Dizemos que há políticas diferentes para execução de uma tarefa.
Classes de política estão para comportamento, assim como traits estão para propriedades de tipos.
Mas muitas vezes, ambos andam acompanhados…
Um exemplo de política na STL é o allocator dos contêineres. Por padrão, std::allocator.
Se precisamos de alocação/desalocação customizadas (diferente de new/delete), devemos definir nosso próprio alocador e passá-lo como argumento para os templates da STL.
As principais funções a serem implementadas por um alocador são as seguintes:

62

Note a semelhança com os operadores new e delete.

63 of 150

Técnicas de templates: template de template

Parâmetros template template: não é typo, é isso mesmo.

Você observou alguma inconveniência no exemplo do PoolAllocator?

63

64 of 150

Técnicas de templates: template de template

Parâmetros template template: não é typo, é isso mesmo.

Você observou alguma inconveniência no exemplo do PoolAllocator?
Tivemos que especificar o tipo base duas vezes, para o vetor e para o alocador. Essa duplicação poderia ser evitada se, na época da construção da STL, já existissem parâmetros template template.

64

65 of 150

Técnicas de templates: template de template

Parâmetros template template: não é typo, é isso mesmo.

Você observou alguma inconveniência no exemplo do PoolAllocator?
Tivemos que especificar o tipo base duas vezes, para o vetor e para o alocador. Essa duplicação poderia ser evitada se, na época da construção da STL, já existissem parâmetros template template.

65

66 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.

66

Definição de A

67 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.

67

Definição de A

1) A instanciação é apenas ilustrativa, realizada internamente pelo compilador.

68 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.

68

1) A instanciação é apenas ilustrativa, realizada internamente pelo compilador.

Instanciação¹

Definição de A

69 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.

69

70 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.

70

Instanciação¹

O tipo do parâmetro "produzido" não existe (sequer faz sentido). Mas isso não implica em erro de compilação:�o efeito é apenas a eliminação dessa sobrecarga para fins de resolução.

71 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.
SFINAE nos permite "filtrar" tipos em função de suas propriedades. O template abaixo, por exemplo, serve para verificar se determinado tipo é uma classe.

71

72 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.
SFINAE nos permite "filtrar" tipos em função de suas propriedades. O template abaixo, por exemplo, serve para verificar se determinado tipo é uma classe.

72

Se T é classe, então ponteiro para membro existe.

Senão, ocorre falha de substituição: versão … é escolhida.

Tamanho de char é 1.

73 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.
SFINAE nos permite "filtrar" tipos em função de suas propriedades. O template abaixo, por exemplo, serve para verificar se determinado tipo é uma classe.
O header <type_traits> de C++11 utiliza técnicas de SFINAE para fornecer informações sobre tipos.

73

74 of 150

Técnicas de templates: SFINAE

SFINAE: Substitution Failure Is Not An Error

Durante a resolução de sobrecarga, templates de função que podem produzir um tipo inválido (dependendo do argumento T) são simplesmente descartadas, sem que um erro seja gerado.
SFINAE nos permite "filtrar" tipos em função de suas propriedades. O template abaixo, por exemplo, serve para verificar se determinado tipo é uma classe.
O header <type_traits> de C++11 utiliza técnicas de SFINAE para fornecer informações sobre tipos.
Outra aplicação de SFINAE em C++11 é o template std::enable_if.

74

75 of 150

Técnicas de templates: templates variádicas

Templates variádicas: similares a funções variádicas, só que com tipos - desde C++11

A ellipsis … após o palavra-chave class (ou typename) denota um template parameter pack, indicando que o template possui um número arbitrário de parâmetros de tipos.

75

76 of 150

Técnicas de templates: templates variádicas

Templates variádicas: similares a funções variádicas, só que com tipos - desde C++11

A ellipsis … após o palavra-chave class (ou typename) denota um template parameter pack, indicando que o template possui um número arbitrário de parâmetros de tipos.
A ellipsis … após o tipo "empacotado" denota um function parameter pack, representando todos os parâmetros variádicos, em conjunto, através de um nome.

76

77 of 150

Técnicas de templates: templates variádicas

Templates variádicas: similares a funções variádicas, só que com tipos - desde C++11

A ellipsis … após o palavra-chave class (ou typename) denota um template parameter pack, indicando que o template possui um número arbitrário de parâmetros de tipos.
A ellipsis … após o tipo "empacotado" denota um function parameter pack, representando todos os parâmetros variádicos, em conjunto, através de um nome.
A ellipsis … após esse nome denota um parameter pack expansion, disparando uma recursão que, no caso, extrairá o primeiro elemento e deixará os restantes ainda "empacotados".

77

78 of 150

Técnicas de templates: templates variádicas

Templates variádicas: similares a funções variádicas, só que com tipos - desde C++11

A ellipsis … após o palavra-chave class (ou typename) denota um template parameter pack, indicando que o template possui um número arbitrário de parâmetros de tipos.
A ellipsis … após o tipo "empacotado" denota um function parameter pack, representando todos os parâmetros variádicos, em conjunto, através de um nome.
A ellipsis … após esse nome denota um parameter pack expansion, disparando uma recursão que, no caso, extrairá o primeiro elemento e deixará os restantes ainda "empacotados".
Eventualmente, a recursão deve parar em uma sobrecarga com o caso base.

78

Qual a generalização de std::pair que utiliza templates variádicas?

79 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.

79

Qual foi a primeira implementação da STL?

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

80 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.

80

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

81 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.
Iteradores são a "ponte" e única interface entre contêineres e algoritmos.

81

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

Iteradores

82 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.
Iteradores são a "ponte" e única interface entre contêineres e algoritmos.
Function objects auxiliam os algoritmos em operações sobre elementos.

82

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

Iteradores

Functors

83 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.
Iteradores são a "ponte" e única interface entre contêineres e algoritmos.
Function objects auxiliam os algoritmos em operações sobre elementos.
Adaptadores compõe novos contêineres a partir de outros já existentes.

83

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

Iteradores

Functors

std::stack

std::queue

std::priority_queue

84 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.
Iteradores são a "ponte" e única interface entre contêineres e algoritmos.
Function objects auxiliam os algoritmos em operações sobre elementos.
Adaptadores compõe novos contêineres a partir de outros já existentes.
Utilidades gerais também estão disponíveis.

84

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

Iteradores

Functors

std::stack

std::queue

std::priority_queue

std::pair�std::tuple

85 of 150

STL (Standard Template Library)

A STL é uma coleção de algoritmos, implementados genericamente, que interage com estruturas de dados através de abstrações independentes.

Contêineres gerenciam objetos.
Algoritmos processam elementos dos contêineres.
Iteradores são a "ponte" e única interface entre contêineres e algoritmos.
Function objects auxiliam os algoritmos em operações sobre elementos.
Adaptadores compõe novos contêineres a partir de outros já existentes.
Utilidades gerais também estão disponíveis.
Interfaces são definidas em termos de conceitos.

85

Qual foi a primeira implementação da STL?

std::find

std::copy

std::sort

std::transform

std::lower_bound

...

std::vector

std::list

std::set

std::multiset

std::map

std::multimap

std::unordered_map

...

Iteradores

Functors

std::stack

std::queue

std::priority_queue

std::pair�std::tuple

Concepts

86 of 150

Alguns contêineres: std::array

É importante escolher o contêiner apropriado para uma tarefa, pois cada contêiner tem suas vantagens, mas também restrições. Inclusive com relação ao tipo armazenado. Por exemplo, pode ser exigido que T suporte cópia, construção padrão, entre outras.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Seu tamanho deve ser determinado em tempo de compilação.

86

Qual a semântica dos contêineres: valor ou referência?

87 of 150

Alguns contêineres: std::array

É importante escolher o contêiner apropriado para uma tarefa, pois cada contêiner tem suas vantagens, mas também restrições. Inclusive com relação ao tipo armazenado. Por exemplo, pode ser exigido que T suporte cópia, construção padrão, entre outras.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Seu tamanho deve ser determinado em tempo de compilação.
A função membro data() fornece acesso direto ao array.

87

Qual a semântica dos contêineres: valor ou referência?

88 of 150

Alguns contêineres: std::vector

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
É possível reservar espaço no vetor, sem que objetos sejam construídos nessas posições.

88

89 of 150

Alguns contêineres: std::vector

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
É possível reservar espaço no vetor, sem que objetos sejam construídos nessas posições.
Isso é interessante, pois uma eventual realocação invalida todos os iteradores para o vetor!

89

90 of 150

Alguns contêineres: std::vector

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
É possível reservar espaço no vetor, sem que objetos sejam construídos nessas posições.
Isso é interessante, pois uma eventual realocação invalida todos os iteradores para o vetor!
Como o vetor não cresce de um-em-um, vale à pena solicitar, desde C++11, a devolução de memória não ocupada.

90

91 of 150

Alguns contêineres: std::vector

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
É possível reservar espaço no vetor, sem que objetos sejam construídos nessas posições.
Isso é interessante, pois uma eventual realocação invalida todos os iteradores para o vetor!
Como o vetor não cresce de um-em-um, vale à pena solicitar, desde C++11, a devolução de memória não ocupada.
A partir de C++11, prefira em todos contêineres que o suportam, emplace_back() ao invés de push_back().

91

92 of 150

Alguns contêineres: std::deque

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Implementado como um conjunto de blocos, então não há como reservar espaço.

92

93 of 150

Alguns contêineres: std::deque

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Implementado como um conjunto de blocos, então não há como reservar espaço.
Mas a inserção/remoção, seja na frente ou atrás, é em tempo constante (amortizada).

93

94 of 150

Alguns contêineres: std::deque

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Implementado como um conjunto de blocos, então não há como reservar espaço.
Mas a inserção/remoção, seja na frente ou atrás, é em tempo constante (amortizada).
Inserir/remover no meio, assim como em std::vector, é caro.

94

95 of 150

Alguns contêineres: std::list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas suportam inserção/remoção eficiente em qualquer ponto. E iteradores não sofrem invalidação!

95

96 of 150

Alguns contêineres: std::list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas suportam inserção/remoção eficiente em qualquer ponto. E iteradores não sofrem invalidação!
Porém, std::list não possuir operator[].

96

97 of 150

Alguns contêineres: std::list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas suportam inserção/remoção eficiente em qualquer ponto. E iteradores não sofrem invalidação!
Porém, std::list não possuir operator[].
Seus iteradores não serem RandomAccessIterator implica em restrições. Lembra do exemplo de std::sort?

97

98 of 150

Alguns contêineres: std::forward_list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
A interface, assim como características de inserção/remoção, são parecidas com a de std::list.

98

99 of 150

Alguns contêineres: std::forward_list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
A interface, assim como características de inserção/remoção, são parecidas com a de std::list.
Mas por questões de eficiência, operações que dependem da travessia da lista não são oferecidas.

99

100 of 150

Alguns contêineres: std::forward_list

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
A interface, assim como características de inserção, são parecidas com a de std::list.
Mas por questões de eficiência, operações que dependem da travessia da lista não são oferecidas.
Naturalmente, seus iteradores também não são BidirectionalIterator, como os de std::list.

100

101 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map¹.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.

101

1) O padrão não exige que a implementação seja com árvores, mas, pelos requisitos de complexidade, são a melhor opção: red-black trees.

102 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map¹.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.

102

1) O padrão não exige que a implementação seja com árvores, mas, pelos requisitos de complexidade, são a melhor opção: red-black trees.

103 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map¹.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.
Por padrão, o critério de strict weak ordering é encapsulado pelo functor std::less, que utiliza o operator<.

103

1) O padrão não exige que a implementação seja com árvores, mas, pelos requisitos de complexidade, são a melhor opção: red-black trees.

104 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map¹.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.
Por padrão, o critério de strict weak ordering é encapsulado pelo functor std::less, que utiliza o operator<.

104

1) O padrão não exige que a implementação seja com árvores, mas, pelos requisitos de complexidade, são a melhor opção: red-black trees.

105 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map¹.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.
Por padrão, o critério de strict weak ordering é encapsulado pelo functor std::less, que utiliza o operator<.
Tipos definidos pelo usuário deve sobrecarregar esse operador ou fornecer um functor equivalente.

105

1) O padrão não exige que a implementação seja com árvores, mas, pelos requisitos de complexidade, são a melhor opção: red-black trees.

106 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.
Por padrão, o critério de strict weak ordering é encapsulado pelo functor std::less, que utiliza o operator<.
Tipos definidos pelo usuário deve sobrecarregar esse operador ou fornecer um functor equivalente.
Como a chave determina a organização da estrutura de dados, ela não pode ser modificada.

106

107 of 150

Alguns contêineres: std::set e std::map

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
std::set armazena apenas uma chave, já std::map permite sua associação a um valor.
Ambos contêineres mantêm seus elementos de forma ordenada.
Por padrão, o critério de strict weak ordering é encapsulado pelo functor std::less, que utiliza o operator<.
Tipos definidos pelo usuário deve sobrecarregar esse operador ou fornecer um functor equivalente.
Como a chave determina a organização da estrutura de dados, ela não pode ser modificada.
Ambos contêineres possuem versões que suportam duplicatas: std::multiset e std::multimap.

107

108 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.

Apesar de utilizarem o mesmo nome, a interface não era exatamente a mesma, levando a problemas de incompatibilidade. Para pior, elas eram indevidamente colocadas dentro do namespace std.

108

109 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.

109

110 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.
As interface desses contêineres é similar àquela dos contêineres de árvores - ambos são dicionários.

110

111 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.
As interface desses contêineres é similar àquela dos contêineres de árvores - ambos são dicionários.
Como o próprio nome eles, eles não mantém os elementos ordenados.

111

112 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.
As interface desses contêineres é similar àquela dos contêineres de árvores - ambos são dicionários.
Como o próprio nome eles, eles não mantém os elementos ordenados.
Tipos definidos pelo usuário precisam de sua própria função hash.

112

113 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.
As interface desses contêineres é similar àquela dos contêineres de árvores - ambos são dicionários.
Como o próprio nome eles, eles não mantém os elementos ordenados.
Tipos definidos pelo usuário precisam de sua própria função hash.
A implementação da tabela segue a estratégia de separate chaining (closed addressing).

113

114 of 150

Alguns contêineres: std::unordered_map/set.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Anteriormente, em C++98/03, cada implementação da STL oferecia sua própria tabela de hash.
Para evitar confusão, o nome std::unordered_sufixo foi utilizado durante a padronização.
As interface desses contêineres é similar àquela dos contêineres de árvores - ambos são dicionários.
Como o próprio nome eles, eles não mantém os elementos ordenados.
Tipos definidos pelo usuário precisam de sua própria função hash.
A implementação da tabela segue a estratégia de separate chaining, baseada em closed addressing.
Se precisar, pode criar sua própria implementação em open addressing. Eu criei uma…

https://www.codeproject.com/articles/23085/a-generic-open-address-hash-table-implementation-w

114

115 of 150

Alguns contêineres: std::stack.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Um exemplo de container adapter é std::stack (uma pilha).
std::stack adapta um contêiner de tal maneira que sua interface seja aquela de uma pilha (LIFO).

115

116 of 150

Alguns contêineres: std::stack.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Um exemplo de container adapter é std::stack (uma pilha).
std::stack adapta um contêiner de tal maneira que sua interface seja aquela de uma pilha (LIFO).

A implementação, de fato, é composta a partir do parâmetro template Container. Por padrão, std::deque é utilizado, mas podemos instanciar uma std::stack com qualquer contêiner que modele o conceito Sequence.

116

117 of 150

Alguns contêineres: std::stack.

O contêiner mais leve é std::array, introduzido em C++11. Ele é um wrapper de um array puro.
Um wrapper de array puro com maior flexibilidade é std::vector, que suporta crescimento automático.
std::deque é similar a std::vector, mas suporte inserção eficiente em ambas as pontas.
Listas duplamente encadeadas são implementadas por std::list.
Listas simplesmente encadeadas são implementadas, desde C++11, por std::forward_list.
Árvores binárias balanceadas estão presente na STL via std::set e std::map.
Tabelas de hash só foram adicionadas em C++11: std::unordered_set e std::unordered_map.
Um exemplo de container adapter é std::stack (uma pilha).
std::stack adapta um contêiner de tal maneira que sua interface seja aquela de uma pilha (LIFO).

A implementação, de fato, é composta a partir do parâmetro template Container. Por padrão, std::deque é utilizado, mas podemos instanciar uma std::stack com qualquer contêiner que modele o conceito Sequence.
Suas principais funções são: push(), top(), e pop().

117

118 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.

118

119 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.

119

Essa abordagem requer que contêineres já possuam espaço suficiente para a operação em questão, pois iteradores não são capazes de alterar a estrutura dos contêineres em si, apenas seus elementos.

120 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.

120

121 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.

Quando o algoritmo opera em mais de um intervalo, tal como um de entrada e um de saída, apenas o iterador para o início do segundo é necessário (tipicamente, ambos deve ser ter o mesmo tamanho).

121

122 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.

122

123 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.

123

124 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.

As versões que realizam cópia tem o sufixo _copy em seus nomes.

124

125 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.
Normalmente, algoritmos que operam condicionalmente possuem duas sobrecargas: uma que o filtro é representado por um valor; outra em que ele é representado por um predicado.

125

126 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.
Normalmente, algoritmos que operam condicionalmente possuem duas sobrecargas: uma que o filtro é representado por um valor; outra em que ele é representado por um predicado.

Tais algoritmos têm o sufixo _if.

126

127 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.
Normalmente, algoritmos que operam condicionalmente possuem duas sobrecargas: uma que o filtro é representado por um valor; outra em que ele é representado por um predicado.
Por fim, temos algoritmos que "removem" (atenção nas aspas) elementos de um contêiner.

127

128 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.
Normalmente, algoritmos que operam condicionalmente possuem duas sobrecargas: uma que o filtro é representado por um valor; outra em que ele é representado por um predicado.
Por fim, temos algoritmos que "removem" (atenção nas aspas) elementos de um contêiner.

Porém, a remoção é apenas lógica. O elemento continua no contêiner e um novo iterador após-fim é retornado.

128

129 of 150

Algoritmos

Os algoritmos da STL estão declarados no header <algorithm>, com exceção daqueles de processamento numérico, que estão em <numeric>.
Todos eles processam ao menos um intervalo de elementos denotado por um par de iteradores: �o primeiro apontando para o início; o segundo para após-o-fim.
Vários algoritmos permitem que uma função (ou um functor) seja passado como argumento. Sua assinatura depende do conceito a ser modelado. Por exemplo: UnaryFunction ou BinaryFunction.
Se essa função deve retornar o tipo bool, então ela é chamada de predicado. Predicados também têm conceitos associados: Predicate, BinaryPredicate, etc.
Alguns algoritmos modificam os elementos in-place, outros os copiam para um novo destino.
Normalmente, algoritmos que operam condicionalmente possuem duas sobrecargas: uma que o filtro é representado por um valor; outra em que ele é representado por um predicado.
Por fim, temos algoritmos que "removem" (atenção nas aspas) elementos de um contêiner.

Porém, a remoção é apenas lógica. O elemento continua no contêiner e um novo iterador após-fim é retornado.

Para realmente removermos o elemento utilizamos o erase-remove idiom.

129

130 of 150

Biblioteca padrão

Originalmente, a STL era uma implementação independente. Em C++98/03, seus componentes foram incorporados à biblioteca padrão. Esta última contém ainda outras "sub-bibliotecas" tais como de IOStreams e de strings. Em C++11, as seguintes novidades foram introduzidas:

Expressões regulares
Nos permite realizar matching, busca, tokenização e substituição em strings.
Suportam gramáticas variadas: ECMAScript, grep, POSIX, awk, etc.
Oferecem opções para criação, do algoritmo e do formato de substituição.
Reside no header <regex>.

130

Exemplo: Matching de telefone e nome.

131 of 150

Biblioteca padrão

Originalmente, a STL era uma implementação independente. Em C++98/03, seus componentes foram incorporados à biblioteca padrão. Esta última contém ainda outras "sub-bibliotecas" tais como de IOStreams e de strings. Em C++11, as seguintes novidades foram introduzidas:

Expressões regulares
Nos permite realizar matching, busca, tokenização e substituição em strings.
Suportam gramáticas variadas: ECMAScript, grep, POSIX, awk, etc.
Oferecem opções para criação, do algoritmo e do formato de substituição.
Reside no header <regex>.

131

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

132 of 150

Biblioteca padrão: expressões regulares

Expressões regulares

132

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

Exemplo: Tags HTML com captura, (), certificando que as tags se correspondem.

133 of 150

Biblioteca padrão: expressões regulares

Expressões regulares

133

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

Exemplo: Tags HTML com captura, (), certificando que as tags se correspondem.

134 of 150

Biblioteca padrão: expressões regulares

Expressões regulares

134

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

Exemplo: Tags HTML com captura, (), certificando que as tags se correspondem.

Exemplo: O mesmo que o anterior, só que com a gramática do grep ao invés de ECMAScript.

135 of 150

Biblioteca padrão: expressões regulares

Expressões regulares

Precisamos escapar os parêntesis do agrupamento.

135

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

Exemplo: Tags HTML com captura, (), certificando que as tags se correspondem.

Exemplo: O mesmo que o anterior, só que com a gramática do grep ao invés de ECMAScript.

136 of 150

Biblioteca padrão: expressões regulares

Expressões regulares

136

Exemplo: Matching de telefone e nome.

Exemplo: Tags HTML.

Exemplo: Tags HTML com captura, (), certificando que as tags se correspondem.

Exemplo: O mesmo que o anterior, só que com a gramática do grep ao invés de ECMAScript.

Exemplo: std::regex_search realiza um std::regex_match em qualquer parte da string.

false

true

137 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores
Chamada de chrono, a biblioteca foi projetada com neutralidade de precisão.
Seus dois principais componentes são a duration e o timepoint.
Ela oferece três tipos de clock.
Reside no header <chrono>.
Suporta a interface de C e POSIX através do header <ctime>

137

138 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

138

Duration: std::chrono::duration, representa o número de ticks por uma fração, em segundos.

Tipo utilizado para a duração.

Fração em segundos: default de 1 segundo.

139 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

Para as principais unidades, já existem typedefs pré-definidos.

139

Duration: std::chrono::duration, representa o número de ticks por uma fração, em segundos.

Tipo utilizado para a duração.

Fração em segundos: default de 1 segundo.

140 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

Para as principais unidades, já existem typedefs pré-definidos.

140

Duration: std::chrono::duration, representa o número de ticks por uma fração, em segundos.

Tipo utilizado para a duração.

Fração em segundos: default de 1 segundo.

Em C++14 podemos usar os operadores literais de tempo.

141 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

141

Timepoint: std::time_point, representa a associação de um época com uma duration.

142 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

142

Timepoint: std::time_point, representa a associação de um época com uma duration.

Unidade de tempo

143 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

143

Timepoint: std::time_point, representa a associação de um época com uma duration.

Unidade de tempo

std::system_clock

Clock associado àquele do sistema. Logo, pode ser alterado pelo usuário (efeito visível ao programa).

std::steady_clock

Seu avanço é relativo ao tempo real. Porém, oferece a garantia de que nunca é ajustado: monotônico.

std::high_resolution_clock

Clock com o menor período de tick. Se ele pode ser ajustado ou não, depende da plataforma. A função std::clock::is_steady() fornece a informação.

144 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

144

Exemplo: imprime a época do clock e o instante atual.

145 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

145

Exemplo: imprime a época do clock e o instante atual.

Exemplo: benchmark simples.

146 of 150

Biblioteca padrão: clocks e temporizadores

Expressões regulares
Clocks e temporizadores

Para converter de unidades de tempo mais precisas para outras menos precisas: duration_cast.

146

Exemplo: imprime a época do clock e o instante atual.

Exemplo: benchmark simples.

147 of 150

Biblioteca padrão: concorrência

Expressões regulares
Clocks e temporizadores
Concorrência e multithreading
Veremos no próximo módulo!

147

148 of 150

Exercícios

Itere mais uma vez sobre a função sum() e faça um lifting que a permita funcionar com listas encadeadas.
Resolva o problema de invocar std::sort() em um contêiner do tipo std::list.
Coloque um default template argument em Accumulator e generalize-o para utilizar iteradores (ao invés de ponteiros). Qual conceito de iterador a implementação exige?
Pesquise na Internet, apenas para conhecimento, sobre o Curiously Recurring Template Pattern.
Como exercício de variadic templates, reproduzam a implementação da função n_sum().
Termine a implementação de PoolAlloc de maneira que a instanciação de std::vector<int, PoolAlloc<int>> compile sem erros. Não é permitido herdá-lo de std::allocator.
Verifique se o template IsClassType funciona conforme você espera.
Como você invocaria a função n_sum?
Instancie, com o tipo Person, os contêineres std::map e std::unordered_map e veja quais operadores precisa em cada caso.
Experimente a interface de std::unordered_map, adicionando valores com insert, procurando-os com find e removendo-os com erase. Faça também alterações no loading factor da tabela de hash.
Qual o problema de se verificar a existência de um elemento em std::map com o operator[]?
Qual a diferença entre std::sort(), std::partial_sort() e std::stable_sort()? Teste-os com a seguintes elementos, usando como critério de ordenação apenas o inteiro de cada par: <4, "a">, <3, "a">, <9, "b">, <9, "a">, <1, "a">, <10, "a">, <1, "b">, <2, "a">, <7, "a">.
Utilize a sobrecarga de std::regex_search que recebe um std::match_results para iterar e imprimir as partes da string tag <foo> 123 </foo> gat com o padrão R"(<(.*)>.*</\1>)".

148

149 of 150

Algumas referências

http://en.cppreference.com
https://www.sgi.com/tech/stl
http://www.generic-programming.org/
http://www.stlport.org/resources/StepanovUSA.html
https://gcc.gnu.org/onlinedocs/libstdc++/manual/concept_checking.html
http://www.bdsoft.com/tools/stlfilt.html
https://en.wikipedia.org/wiki/Substitution_failure_is_not_an_error
https://isocpp.org/blog/2013/02/concepts-lite-constraining-templates-with-predicates-andrew-sutton-bjarne-s
The C++ Programming Language, 4th. Ed.
C++ Templates: The Complete Guide
C++ Coding Standards
The C++ Standard Library, 2nd. Ed.
Effective STL
From Mathematics to Generic Programming
STL Tutorial and Reference Guide, 2nd. Ed.
Generic Programming and the STL

149

150 of 150

150

Curso de C++ moderno

Leandro T. C. Melo, PhD

www.ltcmelo.com

LTCMELO@GMAIL.COM

Perguntas?