Structure for search and quick insert c ++

You say that:

  

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

There is a class with a specific method for this, which is std::set . The set only stores single-valued elements (that is, without repeated items), and provides a method to try to add a new value, and indicate if possible, set::insert(...)

The following program illustrates this use case 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 output:

numero 1 inserido
numero 5 inserido
numero 5 ja existia

Since you talk about performance, some considerations:

• When constructing objects is too much face for the program, you can use the set::emplace(...) function, which conditionally constructs the object based on its pre-existence or not.
• set effectively stores the values themselves, as well as vector , and keeps them sorted, so you need to provide a way to compare (sort, to be more exact) objects of the class you're supplying , 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 unordered_set . This, for example, does not save the items themselves, but provides efficient methods to check if an item of a certain value has already been added previously.
• (%) has the complexity of insertion O (log (N)), where N is the number of elements already present, and the set average complexity of O (1) (constant, independent of the number of elements already present).

reference to the set

reference to the unordered set