How to optimize this simple algorithm further?

Question

Note: this is a programming challenge

---

This challenge requires usage of std::set.

Input

• A number n
• n lines with each j and k

Sample input:

5
1 4
2 1
1 6
3 4
1 2

j is for the operation: 1 to insert k, 2 to delete k (if there is a k), 3 find k

For j == 3, output Yes or No if k is in the std::set.

---

I made different versions of the algorithm, but all are way too slow. I tried different std functions, but std::find seems the fastest one, but is still too slow. Implementing my own would be even worse, so maybe I missed a function from the library. I really have no idea how to optimize it further. Currently I have this:

int main()
{
    std::set<int> set{};
    int Q = 0;
    std::cin >> Q;

    int type = 0;
    int x = 0;
    for (int i = 0; i < Q; ++i)
    {
        std::cin >> type;
        std::cin >> x;

        if (type == 1)
            set.insert(x);
        else if (type == 2)
            set.erase(x);
        else if (type == 3)
            std::cout << (std::find(std::begin(set), std::end(set), x) != std::end(set) ? "Yes" : "No") << '\n';
            //Condition may be std::find, std::count or std::binary_search
    }

    return 0;
}

---

The challenge requires it to run under 2 seconds. Here are the results of mine:

Function              Time           % over
std::find          -> 7.410s         370.50%
std::count         -> 7.881s         394.05%
std::binary_search -> 14.050s        702.50%

As you can see my algorithm is 3x slower than the required algorithm. The bottlenecks are clearly those functions:

Function               % of total time 
std::find          ->  77.61%
std::count         ->  80.80%
std::binary_search ->  87.59%

But currently I have no better idea than to use std::find or similar functions. Does someone have a way/idea to optimize my code further? Or are there some obvious bottlenecks that I'm missing?

Answer 1

You want to use set.find() and not std::find(set.begin(),set.end()).

set.find() will use the set's internal structure to locate the key in O(log(n)) time. Whereas std::find is a linear search, requiring O(n) time, no matter what container type is used.