PRG29003: Introdução a Listas

[Próxima aula]

• Um video introdutório da Khan Academy
• Estruturas de dados
• Um guia sobre estruturas de dados
• Leis de desenvolvimento de software famosas

Uma lista encadeada é uma estrutura de dados em que os dados são armazenados dinamicamente em memória, de forma a se organizarem em uma sequência. Qualquer dado em uma lista pode ser acessado, independente de sua posição, assim como pode ser adicionados ou removidos de uma posição qualquer. Além disso, a ordem dos dados em uma lista pode ser modificada de diferentes maneiras (ordenamento, embaralhamento, inversão, ...). Tudo isso graças à forma com que uma lista encadeia os dados, em que cada dado armazenado possui referências tanto a seu sucessor quanto seu antecessor. Pode-se fazer um paralelo com listas reais, que aparecem em diversas situações do dia-a-dia, como estas:

Uma playlist

Uma lista de tarefas

Do ponto de vista computacional, podem-se citar estas aplicações de listas:

• Armazenar um conjunto de dados cuja quantidade não pode ser conhecida de antemão. Exemplos são resultados de consultas a bancos de dados, listagens de arquivos de um diretório, resultados de separação de string em substrings.
• Armazenar dados cuja ordem em memória é modificada frequentemente. Exemplos são listas de processos em execução mantidas por sistemas operacionais, listas de mensagens a serem transmitidas cuja ordem depende de suas prioridades, listas de tarefas a serem realizadas por um simulador, listas de reprodução em tocadores de músicas.

Praticamente todas as linguagens de programação usadas atualmente possuem sua própria implementação de lista. Seguem alguns exemplos:

• Java
• Python
• C++
• C#
• Ruby

A lista da STL

A STL apresenta duas estruturas de dados relacionadas com armazenamento de sequências de dados, os quais podem ser acessados randomicamente:

• vector: um vetor dinâmico em que dados podem ser adicionados e removidos de qualquer posição (porém com certo custo computacional), e também acessados diretamente (referenciados por suas posições) com eficiência
• list: uma lista em que dados podem ser adicionados e removidos de qualquer posição com eficiência, porém acessados de forma iterativa (sempre a partir do início ou final da lista)

Ambas estruturas de dados podem ser usadas para armazenar conjuntos de dados em sequência. As diferenças entre elas dizem respeito a como os dados estão de fato armazenados na memória do programa, e isso influencia a eficiência das operações dessas estruturas de dados.

Em vector, os dados estão sempre contíguos em memória. Um vector usa uma área de memória capaz de guardar a quantidade de dados armazenados, estando os dados gravados sequencialmente ali dentro. A figura a seguir mostra como um vector usa memória para armazenar dados.

Um vector com alguns dados armazenados

Em list, cada dado ocupa uma área de memória sob medida, e para formar uma sequência essas áreas de memória são encadeadas (ligadas). Como consequência, os dados não ficam contíguos.

Uma lista com alguns dados

Em geral, vector é adequado quando os dados são armazenados e removidos do final da área de armazenamento, e também quando se precisam acessá-los diretamente (por suas posições) e/ou aleatoriamente. Com list é o contrário, pois ela é adequada quando dados precisam ser inseridos e removidos de qualquer posição. Cabe ao programador escolher a estrutura mais adequada em cada situação. Os pontos listados a seguir buscam esclarecer melhor o que está em jogo.

• Com list, não é necessária uma área de memória contígua: como dados são armazenados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos dados em memória e sua ordem na lista. No caso de vector, a localização dos dados em memória está diretamente ligada a suas posições na área de armazenamento.
• Com list não é possível indexar os dados, por isso para acessar um dado deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada sucessor ou antecessor até chegar àquele procurado.
• Com vector podem-se indexar os dados, acessando-os diretamente por suas posições, uma vez que suas localizações em memória podem ser calculadas em função de suas posições.
• Com list, acrescentar uma dado implica modificar a referência ao sucessor do dado que deve antecedê-lo na lista. Assim, não é necessário "empurrar" os dados seguintes para frente (como seria o caso quando se usa vector).
• Para remover um dado é a mesma coisa: basta modificar a referência de seu antecessor. Assim, não é necessário "deslocar pra trás" os dados seguintes (como seria o caso de vector).

Essas estruturas de dados possuem algumas operações em comum, como mostrado na tabela a seguir.

Descrição	vector	list
Adicionar um dado ao final	push_back	push_back
Adicionar um dado no início	??	push_front
Insere um dado em uma determinada posição	insert	insert
Remove um ou mais dados a partir de uma determinada posição	erase	erase
Acessa o dado que está no início	front	front
Acessa o dado que está no final	back	back
Obtém a quantidade de dados armazenados	size	size
Remove todos os dados (esvazia)	clear	clear

Abaixo seguem exemplos de uso de algumas operações de vector e list:

vector

list

#include <cstdlib> #include <vector> #include <iostream> #include <string> using namespace std; void mostra_vetor(vector<string> & v) { // itera o vetor for (auto & dado: v) { cout << dado << ","; } cout << endl; } int main(int argc, char** argv) { // cria um vector de string vector<string> nomes; // anexa três dados ao final do vector nomes.push_back("manuel"); nomes.push_back("maria"); nomes.push_back("bilica"); // mostra comprimento e conteúdo do vector cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_vetor(nomes); // insere dado no início do vector (ineficiente ...) nomes.insert(nomes.begin(), "maneca"); cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_vetor(nomes); // remove dado do início do vector (ineficiente...) nomes.erase(nomes.begin()); cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_vetor(nomes); // ao final, vector é automaticamente destruído, e a memória utilizada // é liberada return 0; }

#include <cstdlib> #include <list> #include <iostream> #include <string> using namespace std; void mostra_lista(list<string> & lista) { // itera a lista for (auto & dado: lista) { cout << dado << ","; } cout << endl; } int main(int argc, char** argv) { // cria uma lista de string list<string> nomes; // anexa três dados ao final da lista nomes.push_back("manuel"); nomes.push_back("maria"); nomes.push_back("bilica"); // mostra comprimento e conteúdo da lista cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_lista(nomes); // insere dado no início da lista nomes.push_front("maneca"); cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_lista2(nomes); // remove dado do início da lista nomes.pop_front(); cout << "Comprimento: " << nomes.size() << ", dados: "; mostra_lista(nomes); // ao final, lista é automaticamente destruída, e a memória utilizada // é liberada return 0; }

Ao usar essa nova estrutura de dados, existem algumas novidades em comparação com a fila e a pilha. A primeira delas diz respeito à iteração da lista. Tanto a fila quanto a pilha possibilitavam acessar apenas os dados em suas extremidades. A lista é muito mais flexível, possibilitando acessar dados em qualquer posição. No entanto, devido à forma como os dados ficam armazenados dentro da lista, para acessá-los é necessário usar um iterador.

Atividade

1. Lista de números inteiros

Um resumo sobre a notação para complexidade de algoritmos

Figura obtida deste artigo sobre estruturas de dados em Python

Operações quer percorrem a lista

• Exceções: avisos de erros ou situações inesperadas em um programa

A lista encadeada da Prglib ofere outras operações além daquelas para adicionar, obter e remover dados. Duas outras operações são de grande utilidade:

• iteração: possibilita obter sucessivamente de forma eficiente os dados da lista;
• procura: possibilita procurar dados dentro da lista

Iteração

Quando se necessitam acessar em sequência todos (ou uma boa parte) dos dados de uma lista, a melhor forma é por meio da operação de iteração. A lista é capaz de ser iterada por meio dos métodos inicia, proximo e fim. Esses métodos são usados em conjunto para acessar cada dado da lista sucessivamente, a partir do início da lista. O exemplo a seguir mostra como usá-los:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração
  numeros.inicia();

  // enquanto não chegar ao fim da lista, continua a iteração
  while (! numeros.fim()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.proximo();

    cout << "Numero: " << algo << endl;
  }
}

Essa forma de percorrer os dados de uma lista é muito mais eficiente do que acessar os dados a partir de suas posições (usando o método obtem ou o operador []). Para ter uma ideia, percorrer uma lista com 10 dados é 10 vezes mais rápido com iteração. Se a lista tiver 100 dados, a iteração é 100 vezes mais rápida. Se a lista tiver 1000 dados, a uteração é 1000 vezes mais rápida, e assim por diante. O tempo que se leva para percorrer todos os dados com iteração é proporcional à quantidade de dados, porém se for usado o método obtem (ou operador []), o tempo necessário é proporcional ao quadrado da quantidade de dados.

A iteração pode ser feita também em sentido contrário se forem usados os métodos iniciaPeloFim, anterior, e inicio:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // inicia a iteração pelo fim da lista
  numeros.iniciaPeloFim();

  // enquanto não chegar ao início da lista, continua a iteração
  while (not numeros.inicio()) {
    // obtém o próximo dado da iteração 
    int algo = numeros.anterior();

    cout << "Numero: " << algo << endl;
  }
}

Procura por dados

Uma outra operações da lista útil e genérica diz respeito à busca de todos os dados que atendam algum critério de comparação, retornando uma outra lista com os dados encontrados.

A procura de um dado é uma operação que retorna todos os dados da lista de acordo com uma comparação de igualdade. Assim, os dados armazenados precisam ser comparáveis para que isso possa ser feito. Em outras palavras, o tipo de dados armazenado deve definir o operador de igualdade (==). Essa operação de procura está declarada assim na classe lista da prglib:

  // Retorna uma referência a um dado que seja equivalente a "algo"
  T& procura(const T &algo) const; 

  // Procura todos os dados equivalentes a "algo", e os
  // anexa a "lista". Retorna uma referência à própria lista "result" que foi passada como parâmetro.
  lista<T> & procuraMuitos(const T &algo, lista<T> & result) const;

Existem dois métodos para procura de dados na lista:

• procura: procura a primeira ocorrência de um dado que seja igual a algo, retornando uma referência ao dado encontrado. Caso não o encontre, dispara uma exceção.
• procuraMuitos: procura todos os dados que sejam iguais a algo, e os armazena na lista result. Caso nada encontre, não modifica a lista result e termina sem avisar qualquer erro.

O método procura pode ser testado com uma lista de inteiros. O programa de teste a seguir demonstra o uso de procura (obs: o programa depende da lista ter implementado o método escrevaSe):

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> l;

  l.anexa(5);
  l.anexa(1);
  l.anexa(5);
  l.anexa(5);
  l.anexa(1);
  l.anexa(8);
  l.anexa(2);

  // "procura" dispara uma exceção se não encontrar o dado, então 
  // deve-se capturar essa exceção para tratá-la.
  try {
    int res = l.procura(5);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 5 na lista" << endl;    
  }

  try {
    int res = l.procura(9);
    cout << "Encontrou o valor " << res << " na lista" << endl;
  } catch (...) {
    cout << "NÃO encontrou o valor 9 na lista" << endl;    
  }

  lista<int> lr;

  l.procuraMuitos(5, lr);
  cout << "Encontrou " << lr.comprimento() << " valores iguais a 5" << endl;
  lr.escrevaSe(cout, ",");
  cout << endl;
}

Comparação de igualdade

As operações de procura dependem da comparação de igualdade dos dados contidos numa lista. Isso significa que deve existir o operador == para o tipo desses dados. Esse operador existe na linguagem para tipos básicos, tais como int, float, char e outros. Mas o mesmo não vale para tipos de dados definidos pelo programador, ou mesmo classes. Nesse caso, o programador deve definir o operador == , pois somente ele sabe como valores desses tipos devem ser comparados. Observe-se também que a comparação dos dados não é um problema da lista, que apenas usa a comparação. Em suma, cada tipo e dados ou classe deve saber como comparar seus valores ou objetos.

A linguagem C++ possibilita definir como um determinado operador deve funcionar. Isso aplicado ao operador == resolve o problema da comparação de um tipo de dados definido pelo programador. A implementação de um operador pode ser feita de duas maneiras:

1. Incluindo-o ao tipo struct ou à classe:

   struct Registro {
     // atributos do tipo Registro
   
     bool operator==(const Registro & outro) const;
   };
   

2. Criando uma função:

   // compara "este" com "outro"
   bool operator==(const Registro & este, const Registro & outro) const {
     // implementação da comparação
   }
   

Ambas as formas de implementar um operador são válidas e resolvem o problema. Uma observação diz respeito à implementação com uma função, a qual tem precedência sobre a implementação dentro da struct ou classe. Isso significa que mesmo que já exista o operador em questão definido dentro de uma struct ou classe, ele pode ser substituído por outra implementação desse operador em uma função. A isso se chama sobrecarga de operador.

Atividade

Faça estes exercícios que envolvem iteração e/ou procura por dados:

1. Copiar uma lista usando iteração
2. Filtra valores de uma lista
3. Lista de contadores
4. Palavras repetidas
5. Contador de palavras

Operações que reorganizam a lista

Três operações disponíveis na lista reorganizam a ordem dados dados armazenados:

• ordenamento: ordena os dados de forma eficiente
• embaralhamento: mistura os dados aleatoriamente
• inversão: inverte a ordem dos dados

Ordenamento da lista

A lista possui o método ordena, que ordena seus dados. O ordenamento é feito por um algoritmo com razoável eficiência (ele tem custo de tempo computacional O(n log n)), e isso é importante porque esse tipo de operação tem custo computacional considerável (pode ser proporcional ao quadrado da quantidade de dados se não for bem feito). O único requisito para ordenar uma lista é que os dados armazenados possuam uma relação de precedência. Em outras palavras, que possam ser comparados com operador < (menor que). O exemplo a seguir mostra o ordenamento de uma lista:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  numeros.escrevaSe(cout);

  cout << endl;
}

Como o método ordena depende da existência do operador < para o tipo dos dados armazenados, as mesmas considerações feitas quanto à operação de igualdade se aplicam aqui. A próxima subseção mostra um exemplo de ordenamento de uma lista que contém valores de um tipo definido pelo programador.

Ordenamento de uma lista com valores de um tipo definido pelo programador

Quando um programador define um novo tipo ou classe, seus operadores relacionais ainda não existem. Quer dizer, não se conseguem comparar valores desse novo tipo com operadores tais como <, >, <=, >= e ==, entre outros. O ordenamento da lista depende do operador <, portanto uma lista que contenha valores do novo tipo não pode ser ordenada a menos que esse operador seja declarado e implementado.

O exemplo a seguir mostra um programa que cria uma lista com valores de um novo tipo de dados, e a ordena.

Exemplo com o operador< como um método do novo tipo de dados

// o novo tipo de dados: as coordenadas de um vetor bidimensional struct Vetor { double x, y; Vetor(double X, double Y) { x = X; y = Y; } // calcula o módulo do vetor double modulo() const { return sqrt(x*x + y*y); } // operador < para Vetor: compara os módulos deste vetor com o outro vetor // retorna true se módulo deste vetor for menor que módulo de v2 bool operador<(const Vetor & v2) { return modulo() < m2.modulo(); } }; int main() { lista<Vetor> lv; // acrescenta alguns vetores à lista lv.anexa(Vetor(2,2)); lv.anexa(Vetor(1,3)); lv.anexa(Vetor(3,2)); lv.anexa(Vetor(0,5)); lv.anexa(Vetor(3,3)); // ordena a lista lv.ordena(); // mostra os vetores ordenados lv.inicia(); while (! lv.fim()) { Vetor & v = lv.proximo(); cout << "x=" << v.x << ", " << y=" << v.y << endl; } }

Exemplo com o operador< como uma função

// o novo tipo de dados: as coordenadas de um vetor bidimensional struct Vetor { double x, y; Vetor(double X, double Y) { x = X; y = Y; } // calcula o módulo do vetor double modulo() const { return sqrt(x*x + y*y); } }; // operador < para Vetor: compara os módulos dos vetores v1 e v2 // retorna true se módulo do vetor v1 for menor que módulo de v2 bool operator<(const Vetor & v1, const Vetor & v2) { return v1.modulo() < v2.modulo(); } int main() { lista<Vetor> lv; // acrescenta alguns vetores à lista lv.anexa(Vetor(2,2)); lv.anexa(Vetor(1,3)); lv.anexa(Vetor(3,2)); lv.anexa(Vetor(0,5)); lv.anexa(Vetor(3,3)); // ordena a lista lv.ordena(); // mostra os vetores ordenados lv.inicia(); while (! lv.fim()) { Vetor & v = lv.proximo(); cout << "x=" << v.x << ", " << y=" << v.y << endl; } }

Outro exemplo visto em aula

#include <iostream> #include <string> #include <prglib.h> using namespace std; using prglib::lista; // Tipo Alguem: representa uma pessoa com seu nome e idade struct Alguem { string nome; int idade; Alguem() { idade = 0; } Alguem(const string & umNome, int age) { nome = umNome; idade = age; } // sobrecarga do operador< para o tipo Alguem bool operator<(const Alguem & o) { if (idade == o.idade) { return nome < o.nome; } return idade < o.idade; } }; // sobrecarga do operador << para stream de saída (ostream) // com ele se consegue escrever na stream um valor do // tipo Alguem ostream & operator<<(ostream & out, const Alguem & x) { out << x.nome << ": " << x.idade; return out; } int main() { lista<Alguem> l; Alguem joao("Joao", 20); Alguem ninguem; Alguem x1("Amanda", 15); l.anexa(x1); Alguem x2("Gabriel", 19); l.anexa(x2); l.anexa(Alguem("Isadora", 18)); l.anexa(Alguem("Gustavo", 18)); // ordena a lista l.ordena(); // isto só funciona porque agora existe o operador << // que sabe apresentar o tipo Alguem l.escrevaSe(cout); cout << endl; }

Embaralhamento

O embaralhamento envolve misturar eficientemente os dados da lista de forma aleatória. O algoritmo envolvido tem custo de tempo computacional O(n log n). Esse método está declarado assim na classe lista:

  // embaralha os dados de uma lista
  void embaralha();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // embaralha a lista
  numeros.embaralha();

  numeros.escrevaSe(cout);

  cout << endl;
}

Inversão

A inversão da lista envolve inverter a ordem dos dados nela armazenados: o primeiro se torna o último, o segundo o penúltimo, e assim por diante. O algoritmo envolvido tem custo de tempo computacional O(n). Esse método está declarado assim na classe lista:

  // inverte a ordem dos dados de uma lista
  void inverte();

Seu uso é direto, e não há dependência a qualquer operador do tipo dos dados armazenados. Um exemplo de uso é este:

#include <iostream>
#include <prglib.h>

using namespace std;
using prglib::lista;

int main() {
  lista<int> numeros;

  numeros.anexa(34);
  numeros.anexa(7);
  numeros.anexa(21);
  numeros.anexa(8);
  numeros.anexa(12);
  numeros.anexa(17);

  // ordena a lista
  numeros.ordena();

  // ... e agora a inverte, para obter um ordenamento decrescente
  numeros.inverte();

  numeros.escrevaSe(cout);

  cout << endl;
}

Atividade

Faça estes exercícios que envolvem ordenamento:

1. Lista ordenada de números inteiros
2. Ordenar linhas de um arquivo
3. Ordenar linhas de um arquivo de acordo com comprimentos das linhas

Uma solução para o exercício 3

#include <fstream> #include <iostream> #include <prglib.h> using prglib::lista; using namespace std; // Este novo tipo de dados foi criado para possibilitar comparar // strings pelos seus comprimentos. // Note que o tipo Linha apenas encapsula uma string (campo string s), // e define o operador < struct Linha { // a string encapsulada string s; Linha() {} Linha(const string & algo) { s = algo; } }; // o operador < compara as strings s1 e s2 (s1 < s2) // a comparação é feita pelos comprimentos das strings encapsuladas bool operator<(const Linha & s1, const Linha & s2) { return s1.s.size() < s2.s.size(); } int main(int argc, char * argv[]) { // implemente aqui seu programa ifstream arq(argv[1]); // Cria uma lista de Linha, para ser possível ordenar pelo comprimento de string lista<Linha> l; string x; // para cada linha lida e guardada na variável "x" while (getline(arq, x)) l.anexa(x); // ordena a lista: a comparação entre os valores armazenados será feita usando o // operador < do tipo Linha l.ordena(); // Usa iteração para apresentar o conteúdo da lista na tela l.inicia(); while (! l.fim()) { Linha & linha = l.proximo(); cout << linha.s << endl; } return 0; }

Outra solução para o exercício 3 ... ver o uso da operação escrevaSe da lista (depende do operador << para o tipo Linha)

#include <fstream> #include <iostream> #include <prglib.h> using prglib::lista; using namespace std; // Este novo tipo de dados foi criado para possibilitar comparar // strings pelos seus comprimentos. // Note que o tipo Linha apenas encapsula uma string (campo string s), // e define o operador < struct Linha { // a string encapsulada string s; Linha() {} Linha(const string & algo) { s = algo; } }; // o operador < compara as strings s1 e s2 (s1 < s2) // a comparação é feita pelos comprimentos das strings encapsuladas bool operator<(const Linha & s1, const Linha & s2) { return s1.s.size() < s2.s.size(); } // define como funciona o operador << (escrita formatada) para o tipo Linha ostream& operator<<(ostream & out, const Linha & linha) { out << linha.s; return out; } int main(int argc, char * argv[]) { // implemente aqui seu programa ifstream arq(argv[1]); // Cria uma lista de Linha, para ser possível ordenar pelo comprimento de string lista<Linha> l; string x; // para cada linha lida e guardada na variável "x" while (getline(arq, x)) l.anexa(x); // ordena a lista: a comparação entre os valores armazenados será feita usando o // operador < do tipo Linha l.ordena(); l.escrevaSe(cout); cout << endl; return 0; }

Curiosidade: contando quantas vezes cada valor existe em uma lista

No projeto 2, o requisito "listar os atores que mais atuaram, por ordem decrescente de atuações em filmes" poderia ser resolvido de mais de uma maneira. Uma abordagem é criar uma lista contendo todos os nomes de atores que atuaram nos filmes, de forma que, se um ator trabalhou em três filmes, seu nome apareceria três vezes nessa lista. Basicamente isso implica listar os atores de cada filme, e acrescentá-los a essa nova lista. Ao final, bastaria contar quantas vezes cada ator aparece na lista.

Ao menos dois algoritmos podem ser pensados para esse problema:

1. Para cada ator da lista, usar a operação procuraMuitos da lista para contar quantas vezes seu nome aparece. O comprimento da lista resultante dessa procura é a quantidade de vezes em que seu nome aparece. Há que cuidar para realizar essa procura somente para a primeira vez em que cada ator é avaliado.
2. Ordenar a lista de atores, e então iterá-la. Os nomes de atores ficarão contíguos, o que facilita contá-los. Se o próximo ator da iteração for diferente do anterior, então registra-se a contagem do ator anterior e reinicia-se o contador.

Qual dos dois algoritmos é melhor, do ponto de vista de custo computacional (tempo para concluirem) ? O gráfico abaixo responde essa questão !

Custo computacional dos algoritmos para ocntar valores repetidos em uma lista, para listas de números inteiros

Uma alternativa à lista: vetor dinâmico

A STL apresenta uma outra estrutura de dados linear chamada vector. Essa estrutura se apŕesenta como um vetor dinâmico, em que dados são armazenados de forma parecida com um vetor, porém cuja área de armazenamento em memória pode ser expandida automaticamente. Em vector, os dados estão sempre contíguos em memória. Um vector usa uma área de memória capaz de guardar a quantidade de dados armazenados, estando os dados gravados sequencialmente ali dentro. A figura a seguir mostra como um vector usa memória para armazenar dados.

Um vector com alguns dados armazenados

Em geral, vector é adequado quando os dados são armazenados e removidos do final da área de armazenamento, e também quando se precisam acessá-los diretamente (por suas posições) e/ou aleatoriamente. Com list é o contrário, pois ela é adequada quando dados precisam ser inseridos e removidos de qualquer posição. Cabe ao programador escolher a estrutura mais adequada em cada situação. Os pontos listados a seguir buscam esclarecer melhor o que está em jogo.

• Com list, não é necessária uma área de memória contígua: como dados são armazenados dinamicamente, eles podem ocupar áreas de memória arbitrárias, e não há nenhuma relação entre a localização dos dados em memória e sua ordem na lista. No caso de vector, a localização dos dados em memória está diretamente ligada a suas posições na área de armazenamento.
• Com list não é possível indexar os dados, por isso para acessar um dado deve-se obrigatoriamente procurá-lo a partir do início ou fim da lista, seguindo cada sucessor ou antecessor até chegar àquele procurado.
• Com vector podem-se indexar os dados, acessando-os diretamente por suas posições, uma vez que suas localizações em memória podem ser calculadas em função de suas posições.
• Com list, acrescentar uma dado implica modificar a referência ao sucessor do dado que deve antecedê-lo na lista. Assim, não é necessário "empurrar" os dados seguintes para frente (como seria o caso quando se usa vector).
• Para remover um dado é a mesma coisa: basta modificar a referência de seu antecessor. Assim, não é necessário "deslocar pra trás" os dados seguintes (como seria o caso de vector).

As operações que podem ser feitas em vector são parecidas com as operações de list.

• push_back: Adicionar um dado ao final
• insert: Inserir um dado em uma determinada posição
• erase: Remover um ou mais dados a partir de uma determinada posição
• front: Acessar o dado que está no início
• [/ operador []]: Acessar um dado em uma posição qualquer
• back: Acessar o dado que está no final
• size: Obter a quantidade de dados armazenados
• clear: Remover todos os dados (esvaziar)

Abaixo segue um exemplo de uso de algumas operações de vector:

#include <cstdlib>
#include <vector>
#include <iostream>
#include <string>

using namespace std;

void mostra_vetor(vector<string> & v) {
    // itera o vetor
    for (auto & dado: v) {
      cout << dado << ",";
    }
    cout << endl;
}

int main(int argc, char** argv) {
    // cria um vector de string
    vector<string> nomes;
    
    // anexa três dados ao final do vector
    nomes.push_back("manuel");
    nomes.push_back("maria");
    nomes.push_back("bilica");
    
    // mostra comprimento e conteúdo do vector
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_vetor(nomes);

    // Acessa um dado por sua posição
    for (int i=0; i < v.size(); i++) {
      cout << "Dado na posição " << i << ": " << nomes[i] << endl;
    }

    // remove dado do final do vector
    nomes.pop_back();
    cout << "Comprimento: " << nomes.size() << ", dados: ";
    mostra_vetor(nomes);
    
    // ao final, vector é automaticamente destruído, e a memória utilizada
    // é liberada
    return 0;
}

Nem tudo que se pode fazer com list está disponível em vector:

• Ordenamento: não há uma operação de ordenamento para vector, porém é possível ordená-los por meio de um algoritmo existente na STL.
• Embaralhamento: não existe uma operação para embaralhar os dados em um vector, mas também há um algoritmo para essa finalidade na STL.
• Reversão: não há operação para inverter as ordens dos dados, o que também depende de um algoritmo da STL.
• ... e algumas outras operações de list !

Por fim, assim como emlist, iteradores são úteis para acessar dados e percorrer vector.