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?
1 Resposta
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 ovector
, 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 ounordered_set
complexidade média de O(1) (constante, independente do número de elementos já presentes).
std::map
não serve ? Que tipo de dados são ?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).std::unordered_map
que é implementado como uma hashtable