10 Sequências
Há dois principais tipos de sequências: lista e colônia4.
Listas são estruturas de dados cujos elementos podem ser acessados sequencialmente preservando a ordem destes.
Colônias, por sua vez, sacrificam a ordem dos elementos para garantir outras propriedades desejadas.
10.1 Listas
10.1.1 Modelo abstrato e operações em listas
Para definir o nosso modelo abstrato de lista, vamos começar pelas operações desejáveis.
| Operação | Parâmetros | Descrição |
|---|---|---|
| Criar | Capacidade | Cria uma lista com capacidade especificada (potencialmente ilimitada5). |
| Copiar | Cria uma cópia da lista. | |
| Esvaziar | Esvazia a lista. | |
| Acessar | Posição | Acessa um elemento da lista dada uma posição. |
| Inserir | Elemento, Posição | Insere um elemento numa posição específica da lista. |
| Remover | Posição | Remove o elemento numa posição específica da lista. |
| Concatenar | Lista | Concatena outra lista no fim da lista. |
| Separar | Posição | Separa a lista em duas a partir duma determinada posição. |
Além dessas operações, há outras mais triviais, como consultar o tamanho, consultar a capacidade, verificar se está cheia, e verificar se está vazia.
Em C++17, podemos definir uma interface6 básica:
template <typename T> class list {
public:
explicit list(std::size_t capacity);
~list() noexcept;
list(const list&);
list(list&&) noexcept;
auto operator=(const list&) -> list&;
auto operator=(list&&) noexcept -> list&;
auto empty() -> void;
auto size() const -> std::size_t;
auto capacity() const -> std::size_t;
auto is_empty() const -> bool;
auto is_full() const -> bool;
auto at(std::size_t) -> T&;
auto front() -> T&;
auto back() -> T&;
auto insert(std::size_t, T) -> void;
auto remove(std::size_t) -> void;
auto concat(list<T>) -> void;
auto split(std::size_t) -> list<T>;
};Uma vez que levantamos as operações desejáveis da lista, veremos diferentes estruturas de dados que contemplam essa finalidade. Veremos também que cada uma delas apresentará diferentes vantagens e desvantagens em termos de complexidade de tempo.
Além disso, dependendo da estrutura que escolhermos, mudaremos alguns detalhes da nossa interface para melhor adequá-la ao contexto.
10.1.2 Implementações de listas
Nas implementações, não vamos usar os containers da STL (std::vector,
std::list, etc) por motivos didáticos.
10.1.2.1 Lista contígua estática
template <typename T, std::size_t N> class list {
public:
list() = default;
// ...
private:
using storage_type = std::aligned_storage_t<sizeof(T), alignof(T)>;
std::array<storage_type, N> values_;
std::size_t size_ = 0u;
};Não precisamos implementar o construtor.
Exercício: Por que o construtor padrão (gerado pelo compilador) é suficiente neste caso?
Limpando a lista:
template <typename T, std::size_t N>
auto list<T, N>::empty() {
if constexpr (!std::is_trivially_destructible_v<T>)
for (std::size_t i = 0; i < size_; ++i)
std::destroy_at(std::address_of(values_[i]));
size_ = 0;
}Com esta operação, a implementação do destrutor torna-se bastante simples:
template <typename T, std::size_t N>
list<T, N>::~list() noexcept {
empty();
}Checando as margens:
template <typename T, std::size_t N>
auto list<T, N>::is_empty() const -> bool {
return size_ == 0;
}
template <typename T, std::size_t N>
auto list<T, N>::is_full() const -> bool {
return size_ == N;
}Os construtores de cópia e movimentação são triviais:
template <typename T, std::size_t N>
list<T, N>::list(const list& source) {
for (std::size_t i = 0; i < source.size_; ++i)
::new (std::address_of(values_[i])) T(source.values_[i]);
size_ = source.size_;
}
template <typename T, std::size_t N>
list<T, N>::list(list&& source) noexcept {
for (std::size_t i = 0; i < source.size_; ++i)
::new (std::address_of(values_[i])) T(std::move(source.values_[i]));
size_ = std::exchange(source.size_, 0u);
}Exercícios:
- Implementar as operações de atribuição (cópia e movimentação) eficientemente.
- Implementar versão destas operações (construtores e atribuições) garantias de exceção fortes nestas operações (sem utilizar funções prontas da biblioteca padrão).