Resolução de problemas/Standard template library

Introdução

Na resolução dos problemas das competições de programação é muito importante que o competidor tenha um bom domínio das estruturas de dados básicas, tais como: pilhas, filas, vetores, strings etc, além de algoritmos diversos. Aqueles que já experimentaram programar usando a linguagem C sabem das dificuldades encontradas na resolução dos problemas: toda vez que precisamos de uma estrutura de dados ou um algoritmo, por mais simples que sejam, devemos implementá-los à partir do zero. Perde-se aí um tempo que pode ser precioso para a resolução de um problema mais complexo.

Os competidores que optarem pela linguagem C++ poderão poupar esse tempo: existe uma biblioteca padrão do C++ que reúne um conjunto de implementações genéricas dos algoritmos e estruturas de dados mais básicos. Essa biblioteca é a STL.

O que é a STL?

A Standard Template Library, ou STL, é uma biblioteca de algoritmos, containers e iteradores que implementa as estruturas de dados e algoritmos básicos da Ciência da Computação. A STL é baseada no conceito de programação genérica e é implementada usando-se do conceito de templates do C++ (donde origina-se o seu nome). Essa técnica nos fornece um polimorfismo muito poderoso em tempo de compilação. Além disso, podemos abstrair os aspectos complexos da implementação e também reutilizar os componentes já implementados de maneira prática e fácil.

Conteúdo da STL

Containers

"One of the most useful kinds of classes is the container class, that is, a class that holds 
objects of some (other) type" -- Bjarne Stroustrup, desenvolvedor e implementador original
 da linguagem C++.

As classes containers são classes cujo objetivo é agrupar objetos. Na STL, todas essas classes são templates e podem ser instanciadas para agrupar qualquer tipo de objeto. Os containers da STL pode ser dividida em três categorias:

Sequences

Como o próprio nome sugere, são aqueles que organizam um grupo finito de objetos do mesmo tipo de forma estritamente linear.

• Vector
• Lists
• Deques -- Double Ended QUEues

Associative Containers

Eles provêem mecanismos de recuperação dos dados através do uso de chaves associativas além de manterem uma ordenação entre os seus elementos.

• Set
• Multiset
• Map
• Multimap

O Map e o Set permitem apenas uma instância de objeto por conjunto. Se múltiplas instâncias de objetos são necessárias, devemos usar o Multimap ou o Multiset.

Containers Adapters

Eles são apenas variações dos containers acima. Eles não suportam iteradores.

• Stacks
• Queues
• Priority Queues

Iterators

Os iteradores são generalizações dos ponteiros: eles são objetos que apontam para outros objetos. Como o próprio nome sugere, iteradores são usados para iterar sobre um conjunto de objetos: se um iterador aponta para um elemento do conjunto, é possível incrementá-lo de modo a apontar para o elemento seguinte.

Os iteradores são peças fundamentais para a programação genérica pois fazem a interface entre os containers e os algoritmos: os algoritmos geralmente têm como parâmetro os iteradores, então, basta os containers proverem acesso aos seus elementos através dos iteradores. Isso torna possível escrever algoritmos genéricos que operam sobre diferentes tipos de containers, por mais distintos que sejam.

A STL define diversos iteradores pré-definidos e um conjunto de funções para manipulá-los.

Algorithms

A STL já traz implementado um grande número de algoritmos de uso geral, sendo assim uma das partes mais importantes e úteis. Um mesmo algoritmo pode ser usado com a maioria, se não todos, os containers providos pela STL.

Ligações externas

Para um guia mais aprofundado sobre a STL, veja:

• Standard Template Library Programmer's Guide (em inglês)