I need to use a Tree Set data structure(available in java) in C++, and make use of functions like TreeSet.lower(i) and TreeSet.higher(i) - > which returns the element just lower, and just higher than i in the given tree set. Is there an STL?
Edit: Following is the functionality I need, I was wondering how to use the upper_bound and lower_bound functions to do it:
for (int i = 1; i<10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
int k = 50; // I need 40 and 60
set<int>::iterator itr = myset.find(k);
if (itr != myset.end()) {
// Found the element
itr--; // Previous element;
cout << *(itr); //prints 40
itr++; // the element found
itr++; // The next element
cout << *(itr); // prints 60
}
Use std::set
, which is typically implemented as a binary search tree.
Its insert()
, erase()
and find()
methods are logarithmic in size, but can do better if a hint is given. The logarithmic complexity is reffered to the the Java TreeSet.
I think you should be interested in std::lower_bound
, which returns an iterator to the lower bound, and in std::upper_bound
, which returns an iterator to the upper bound.
You can use std::set
Look at std::set::lower_bound
and std::set::upper_bound
You can use std::set here. And for your functionality you can use functions upper_bound(i) and lower_bound(i) but catch here is they don't work similar to TreeSet.lower(i) and TreeSet.higher(i).
lower_bound(const i) – Returns An iterator to the the first element in the container which is not considered to go before i (i.e., either it is equivalent or goes after), or set::end if all elements are considered to go before i.
upper_bound(const i) – Returns an iterator to the first element in the container which is considered to go after i, or set::end if no elements are considered to go after i.
for (int i = 1; i<10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
int k = 50;
set<int>::iterator itlow,itup;
itlow=myset.lower_bound (k);
itup=myset.upper_bound (k);
if(itlow!=myset.begin()){
itlow--;
cout << *itlow; // 40 will print
}
cout << *itup; // 60 will print
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With