0

Tenho um programa que ele adiciona vários elementos em um vetor. A quantidade está ficando maior que 1000000, preciso adicionar e quando já houver o elemento que estou adicionando, ele retorna a posição de memória. Está funcionando, mas está ficando muito lento. Em c++ existe alguma outra estrutura pronta em alguma biblioteca como uma árvore avl?? ou vcs tem alguma outra sugestão para eu resolver esse problema?

5
  • um std::map não serve ? Que tipo de dados são ?
    – Isac
    Commented 15/05/2018 às 17:44
  • é um tipo de classe, que guarda um vértice de um grafo Commented 15/05/2018 às 18:02
  • 1
    @Isac, as implementações convencionais implementam std::map como uma red-black tree, e não como uma AVL, como descrito pelo OP (mas entendi que foi só uma sugestão). Commented 15/05/2018 às 18:48
  • 1
    @MárioFeroldi Que para o efeito é mais rápido na inserção, pois não tem de fazer tantas rotações. Não obstante, e virando para a questão da velocidade, outra solução seria utilizar um std::unordered_map que é implementado como uma hashtable
    – Isac
    Commented 15/05/2018 às 18:57
  • 2
    @LucasVieira Aconselho que você elabore melhor a pergunta, indique o tipo de dados que está armazenando e qual é a solução atual que "Está funcionando, mas está ficando muito lento". Elaborei uma resposta de acordo com uma situação semelhante que encontrei recentemente, espero que já ajude.
    – Kahler
    Commented 15/05/2018 às 23:58

1 Resposta 1

1

Você diz que:

preciso adicionar e quando já houver o elemento que estou adicionando, ele retorna a posição de memória.

Existe uma classe com método específico pra isso, que é o std::set. O set só guarda elementos de valor único (ou seja, sem itens repetidos), e fornece um método para tentar adicionar um novo valor, e indicar se foi possível, o set::insert(...)

O seguinte programa ilustra esse caso de uso do set:

#include <iostream>
#include <set>

std::set<int> Conjunto; //set de inteiros

void tenta_e_avisa(int v)
{
    auto tenta = Conjunto.insert(v); //insere valor fornecido no conjunto
    if(tenta.second) //o segundo item do retorno indica se número foi criado ou já estava presente
    {
        //o primeiro elemento do retorno de 'insert' contém iterador para o item
        std::cout << "numero " << *tenta.first << " inserido\n";
    }
    else
    {
        std::cout << "numero " << *tenta.first << " ja existia\n";
    }
}

int main()
{
    tenta_e_avisa(1);
    tenta_e_avisa(5);
    tenta_e_avisa(5);
}

E produz a saída:

numero 1 inserido
numero 5 inserido
numero 5 ja existia

Já que você fala de performance, algumas considerações:

  • Quando a construção dos objetos é demasiada cara para o programa, você pode usar a função set::emplace(...), que constrói condicionalmente o objeto baseado na pré-existência deste ou não.
  • O set efetivamente armazena os valores em si, assim como o vector, e os mantém ordenados, então você precisa fornecer uma maneira de comparar (ordenar, pra ser mais exato), objetos da classe que você está fornecendo, se esta não for um dos tipos básicos.
  • Quando a ordem dos itens não for importante, existem classes mais especializadas, como o unordered_set. Este, por exemplo, não guarda os itens em si, mas fornece métodos eficientes para verificar se um item de determinado valor já foi adicionado previamente.
  • Tecnicamente, o set tem complexidade de inserção O(log(N)), sendo N o número de elementos já presentes, e o unordered_set complexidade média de O(1) (constante, independente do número de elementos já presentes).

referência para o set

referência para o set não ordenado

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .