Structure for search and quick insertion c++

Asked

Viewed 253 times

0

I have a program that adds several elements to a vector. The amount is getting larger than 1000000, I need to add and when there is already the element I am adding, it returns the memory position. It’s working, but it’s getting too slow. In c++ there is some other ready-made structure in some library like an avl?? tree or you have any other suggestions for me to solve this problem?

c++

  • one std::map does not serve ? What kind of data are ?

  • is a type of class, which holds a vertex of a graph

  • 1

    @Isac, conventional implementations implement std::map as a red-black Tree, and not as an AVL, as described by the OP (but I understood that it was only a suggestion).

  • 1

    @Márioferoldi That for the effect is faster in the insertion, because it does not have to do so many rotations. Nevertheless, turning to the issue of speed, another solution would be to use a std::unordered_map which is implemented as a hashtable

  • 2

    @Lucasvieira I advise you to elaborate the question better, indicate the type of data you are storing and what is the current solution that "It’s working, but it’s getting too slow". I have drawn up a reply according to a similar situation that I found recently, I hope it will help now.

1 answer

1


You say that:

I need to add and when there is already the element I am adding, it returns the memory position.

There is a class with specific method for this, which is the std::set. The set keeps only unique value elements (i.e., no repeat items), and provides a method for try to add a new value, and indicate if possible, the set::insert(...)

The following program illustrates this case of use of 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);
}

And produces the output:

numero 1 inserido
numero 5 inserido
numero 5 ja existia

Since you speak of performance, some considerations:

  • When the construction of objects is too dude for the program, you can use the function set::emplace(...), that conditionally builds the object based on its pre-existence or not.
  • The set effectively stores the values themselves, as well as the vector, and keeps them neat, so you need to provide a way to compare (sort, to be more exact), objects of the class you are providing, if this is not one of the basic types.
  • When the order of the items is not important, there are more specialized classes, such as the unordered_set. This, for example, does not store the items themselves, but provides efficient methods to verify that an item of a certain value has already been previously added.
  • Technically, the set has insertion complexity O(log(N)), where N is the number of elements already present, and the unordered_set average complexity of O(1) (constant, regardless of the number of elements already present).

reference to the set

reference to the ordered set

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.