Contêineres STL classificados dinamicamente

Question

Sou bastante novo no STL, então gostaria de saber se existe algum contêiner classificável dinamicamente?No momento, meu pensamento atual é usar um vetor em conjunto com vários algoritmos de classificação, mas não tenho certeza se existe uma seleção mais apropriada, dada a complexidade (presumivelmente) linear da inserção de entradas em um vetor classificado.

Para esclarecer "dinamicamente", estou procurando um contêiner que possa modificar a ordem de classificação em tempo de execução - por exemplo.classifique-o em ordem crescente e, posteriormente, reclassifique-o em ordem decrescente.

Answer 1

Se você sabe que classificará um único valor crescente e decrescente, então set é seu amigo.Use um iterador reverso quando quiser "classificar" na direção oposta.

Se seus objetos são complexos e você vai classificar de muitas maneiras diferentes com base nos campos de membros dentro dos objetos, então provavelmente será melhor usar um vetor e uma classificação.Tente fazer suas inserções de uma só vez e depois chame sort uma vez.Se isso não for viável, o deque pode ser uma opção melhor que o vetor para grandes coleções de objetos.

Eu acho que se você estiver interessado em que nível de otimização, é melhor traçar o perfil do seu código usando dados reais.(Qual é provavelmente o melhor conselho que alguém aqui pode dar:pode não importar que você chame sort após cada inserção se estiver fazendo isso apenas uma vez na lua azul.)

Answer 2

Você vai querer dar uma olhada em std::map

std::map<keyType, valueType>

O mapa é classificado com base no operador < fornecido para keyType.

Ou

std::set<valueType>

Também classificado no operador < do argumento do modelo, mas não permite elementos duplicados.

Há

std::multiset<valueType>

que faz a mesma coisa que std::set mas permite elementos idênticos.

Eu recomendo fortemente "The C++ Standard Library" de Josuttis para obter mais informações.É a visão geral mais abrangente da biblioteca std, muito legível e repleta de informações obscuras e não tão obscuras.

Além disso, conforme mencionado em 17 de 26, vale a pena ler Effective Stl de Meyers.

Answer 3

Parece que você quer um contêiner de vários índices.Isso permite que você crie um contêiner e informe a ele as diversas maneiras pelas quais você deseja percorrer os itens nele.O contêiner mantém várias listas de itens, e essas listas são atualizadas em cada inserção/exclusão.

Se você realmente deseja reordenar o contêiner, você pode ligar para o std::sort funcionar em qualquer std::deque, std::vector, ou até mesmo um array simples no estilo C.Essa função recebe um terceiro argumento opcional para determinar como classificar o conteúdo.

Answer 4

O stl não fornece tal contêiner.Você pode definir o seu próprio, apoiado por um set/multiset ou um vector, mas você terá que reordenar toda vez que a função de classificação for alterada, chamando sort (para vector) ou criando uma nova coleção (por set/multiset).

Se você deseja apenas mudar da ordem de classificação crescente para a ordem decrescente, você pode usar o iterador reverso em seu contêiner chamando rbegin() e rend() em vez de begin() e end().Ambos vector e set/multiset são contêineres reversíveis, então isso funcionaria para ambos.

Answer 5

std::set é basicamente um contêiner classificado.

Answer 6

Definitivamente, você deve usar um conjunto/mapa.Como diz Hazzen, você obtém O (log n) inserção/localização.Você não conseguirá isso com um vetor classificado;você pode obter O(log n) find usando pesquisa binária, mas a inserção é O(n) porque inserir (ou excluir) um item pode fazer com que todos os itens existentes no vetor sejam deslocados.

Answer 7

Não é tão simples assim.Na minha experiência, inserir/excluir é usado com menos frequência que localizar.A vantagem do vetor classificado é que ele ocupa menos memória e é mais amigável ao cache.Se acontecer de você ter uma versão compatível com mapas STL (como o que vinculei antes), é fácil alternar e usar o contêiner ideal para cada situação.

Answer 8

em teoria, um contêiner associativo (set, multiset, map, multimap) deve ser sua melhor solução.

Na prática depende do número médio de elementos que você está colocando.para menos de 100 elementos, um vetor é provavelmente a melhor solução devido a:- Evitando a alocação contínua -desalocação - amigável de cache devido à localidade de dados que essas vantagens provavelmente superarão a classificação contínua.Obviamente, também depende de quantas inserções-exclusões você precisa fazer.Você vai fazer inserção/exclusão por quadro?

De forma geral:você está falando de um aplicativo de desempenho crítico?

lembre-se de não otimizar prematuramente ...

Answer 9

A resposta é como sempre depende.

set e multiset são apropriados para manter os itens classificados, mas geralmente são otimizados para um conjunto equilibrado de adição, remoção e busca.Se você tiver operações de pesquisa viris, então uma classificação vector pode ser mais apropriado e então usar lower_bound para pesquisar o elemento.

Além disso, seu segundo requisito de recorrer em uma ordem diferente em tempo de execução significará que set e multiset não são apropriados porque o predicado não pode ser modificado em tempo de execução.

Eu recomendaria, portanto, um vetor classificado.Mas lembre-se de passar o mesmo predicado para lower_bound que você passou para a classificação anterior, pois os resultados serão indefinidos e provavelmente errados se você passar o predicado errado.

Answer 10

Conjunto e multiconjunto usam uma árvore binária subjacente;você pode definir o operador <= para seu próprio uso.Esses contêineres se mantêm classificados, portanto, podem não ser a melhor escolha se você estiver alternando os parâmetros de classificação.Vetores e listas são provavelmente melhores se você for recorrer bastante;em geral, a lista possui sua própria classificação (geralmente um mergesort) e você pode usar o algoritmo de pesquisa binária stl em vetores.Se as inserções dominarem, a lista supera o vetor.

Answer 11

Mapas e conjuntos STL são contêineres classificados.

Concordo com a recomendação do livro de Doug T - o livro Josuttis STL é o melhor que já vi como livro de aprendizagem e de referência.

STL eficaz também é um excelente livro para aprender os detalhes internos do STL e o que você deve ou não fazer.

Answer 12

Para vetor classificado "compatível com STL", consulte A.AssocVector de Alexandrescu de Loki.