0

I am trying to find the next / previous neighbor of an element in std::set.

I tried doing something like:

std::set<int> s;
  for (int i = 0; i < 10; ++i) {
    s.insert(i);
  }
  std::set<int>::iterator iter = s.find(5);
  EXPECT_EQ(5, *(iter++));

But it not work.

At a high level, it seems like from a red-black tree it is possible to find the next / previous element in O(logN), so the question is does std::set support it?

shreyasva
  • 13,126
  • 25
  • 78
  • 101
  • 2
    Whether or not it uses red-black trees under the hood is implementation-dependent. The requirements of `std::set` are that it is ordered and supports bidirectional iterators. Please elaborate on _"it not work"_ by clarifying exactly what is not working. – paddy Jul 25 '19 at 05:22
  • The `iter = find` call should take roughly O(lg N) time. I would assume `previous = (*iter-1)` and `next = (*iter + 1)` are O(1). But that's just a guess of how the implementation work based on historical knowledge, not based on the language standard. – selbie Jul 25 '19 at 05:24
  • 1
    Code above works for me. – Martin York Jul 25 '19 at 05:27
  • 2
    Yes it does support it, and in exactly the way you've tried. So what's gone wrong for you is not clear. – john Jul 25 '19 at 06:02
  • 3
    And please don't say 'it doesn't work'. **What actually happens?**. Do you get a different value (if so what is it), do you get a crash, a compile error. 'It doesn't work' is said so many times but it's a completely inadequate description of the circumstances. – john Jul 25 '19 at 06:04
  • 2
    Your question would be so much closer to the title if you had `EXPECT_EQ(6, *(++iter));`. Asit stands it's confusing. And better if you also included what the macro does. – acraig5075 Jul 25 '19 at 06:21

2 Answers2

1

You need to decrement the iterator using preincrement i.e. ++iter rather than postincrement i.e. iter++ if you want to do it in a single line like that:

#include <iostream> 
#include <set>

int main() {
    std::set<int> s;

    for (int i = 0; i < 10; ++i) {
        s.insert(i);
    }

    std::set<int>::iterator iter; 
    iter = s.find(5);

    std::cout << "The number after 5 is: " << *(++iter) << "\n";
    iter--; // Go back to 5 (Here it doesn't matter if you use postdecrement or predecrement)
    std::cout << "The number before 5 is: " << *(--iter) << "\n";

    return 0;
}

Output:

The number after 5 is: 6
The number before 5 is: 4

Note you should check that your iterator is not at the end or beginning as well probably before getting the next/previous element.

Sash Sinha
  • 18,743
  • 3
  • 23
  • 40
0

It seems like you have a typo in your code. You are searching for a 5 and go to the next element. This should be 6, not 5. Besides this you messed up pre and post increment. So after fixing this it should look like: 

std::set<int> s;
for (int i = 0; i < 10; ++i) {
  s.insert(i);
}
std::set<int>::iterator iter = s.find(5);
EXPECT_EQ(6, *(++iter));
zeroset
  • 55
  • 5