How to Check That an Element Is in a Std::Set

How to look for an element inside a set of sets in C++?

Use a simple for loop:

size_t ii = 0;
for (const auto& inner : output) {
    if (inner.count(5))
        std::cout << "found in set " << ii << std::endl;
    ++ii;
}

C++ set how to check if a list of sets contains a subset

Consider using a list of set<int> instead. This allows you to use std::include. Run your loop on the vector after having sorted it by number of elements in the set (i.e. from the sets with the smallest number of elements, to the sets with the largest number of items). The inner loop will start at the current index. This avoids that you check inclusion of the larger sets in the smaller ones.

If the range of the integers is not too large, you could consider implementing the set with a std::bitset (bit n is true if n is included). The inclusion test is then done with very fast logical operation (e.g. subset & large_set == subset). You could still sort the vector by count, but not sure that this would be needed considering the speed of the logical operation.

How does std:set check if there is an equivalent element in set during the insertion?

It calls the comparator twice, with different order of arguments.

If cmp(x, y) and cmp(y, x) are both false, then x and y are considered to be equivalent.

How does std::find works with std::set

The reason for the time complexity difference is that std::find operates with iterators, and it, indeed, does treat std::set as a sequence container, while std::set::find uses container properties.

As for why st.begin() is faster than std::begin(st), they are actually identical. The reason why second is faster is that both of your functions are doing the same thing, and as benchmarks are run consecutively, the execution of the second function is faster because probably cache misses are lower and similar things. I changed the order of these two functions and got exactly opposite result with std::begin(st) being faster. See this modified benchmark here: https://quick-bench.com/q/iM6e3iT1XbqnW_s-v_kyrs6kqrQ

Check that element belongs to std::stack

As others have noted, a std::stack is probably not the best thing to be using, but assuming you have no other option then you'll have to go through the stack one by one and check each element:

bool found_in_stack(int to_find, std::stack<int> stack) {
    while (!stack.empty()) {
        if (stack.top() == to_find) return true;
        stack.pop();
    }
    return false;
}

Notice that I take the stack by value so that a copy is made, this way the original stack isn't changed at all.

Another option would be to mutate the original if you don't want to make a copy, this would require temporarily storing popped elements:

bool found_in_stack(int to_find, std::stack<int>& stack) {
    // keep track of elements we've popped here, we'll add them back at the end
    std::stack<int> tmp;

    bool done = false;
    while (!stack.empty()) {
        if (stack.top() == to_find) {
            done = true;
            break;
        }
        
        tmp.push(stack.top());
        stack.pop();
    }

    // add popped elements back
    while (!tmp.empty()) {
        stack.push(tmp.top());
        tmp.pop();
    }
    return done;
}

Most performant way to verify an element exists in a given set in C++

As @JaMiT recognized, it's not the set that's the problem; it's the potentially unterminated C string. If you invert into another std::string, which knows its length, you won't run into that problem:

string invertSequence(string sequence) 
{
  string inverted(' ', sequence.size());
  for (int i = 0; i < sequence.length(); i++) 
    {
      inverted[sequence.length() - i - 1] = sequence[i];
    }
  return inverted;
}

and at least on my computer, it runs in about 0.6 seconds.

Finally, of course, std::reverse is shorter, safer, and even a little faster:

string invertSequence(string sequence) 
{
  reverse(sequence.begin(), sequence.end());
  return sequence;
}

Determining whether an object is in a std::set

Your code as posted will always execute the code within the if, and 0xbaadf00d is the implementation's "one-past-the-end" marker.

Element at index in a std::set?

It doesn't cause a crash, it just doesn't compile. set doesn't have access by index.

You can get the nth element like this:

std::set<int>::iterator it = my_set.begin();
std::advance(it, n);
int x = *it;

Assuming my_set.size() > n, of course. You should be aware that this operation takes time approximately proportional to n. In C++11 there's a nicer way of writing it:

int x = *std::next(my_set.begin(), n);

Again, you have to know that n is in bounds first.

---

Related Topics