## Is STL set a binary search tree?

**Moderator:** Board moderators

### Is STL set a binary search tree?

Is STL set in fact a binary search tree?

Or is the running time of set::find() and set::insert() O(log n)?

Or is the running time of set::find() and set::insert() O(log n)?

I stay home. Don't call me out.

Thanks.

Another question, how can I get an element of index i in an STL set quickly (O(log n) time).

I think the following code is very slow:
Is there any faster way?

I'm sorry I'm not very familiar with STL.

Another question, how can I get an element of index i in an STL set quickly (O(log n) time).

I think the following code is very slow:

Code: Select all

```
set<int> s;
set<int>::iterator p = s.begin();
for(n = 0; n < i; n++){
p++;
}
```

I'm sorry I'm not very familiar with STL.

I stay home. Don't call me out.

Why would you want that? How do you want the index to be calculated ?ImLazy wrote:Thanks.

Another question, how can I get an element of index i in an STL set quickly (O(log n) time).

....

I don't know where & why you are using that, but I'd suggest

some other container, if its speed that you are getting tied up with. E.g. std::vector.

BTW: in a very simple case, you can use the (value, index) pair to create your set. The index

can actually reflect the order in which they were inserted to the set.

Sometimes I need data structure that can

1. insert and remove in O(log n)

2. search an element in O(log n)

3. search the ith smallest element in O(log n).

e.g. problem 10909.

Binary search tree fits this requirement.

But it seem's that STL set can not fit the 3rd requirement.

1. insert and remove in O(log n)

2. search an element in O(log n)

3. search the ith smallest element in O(log n).

e.g. problem 10909.

Binary search tree fits this requirement.

But it seem's that STL set can not fit the 3rd requirement.

I stay home. Don't call me out.

Code: Select all

```
map <int,int> int2val;//Say we want the ith integer in this map
```

Code: Select all

```
int i = 10;
int val = int2val[i];
```

- Krzysztof Duleba
- Guru
**Posts:**584**Joined:**Thu Jun 19, 2003 3:48 am**Location:**Sanok, Poland-
**Contact:**

Not true - it's possible to use the underlying tree structure. However, such code is not portable.Neither set nor map can't be used to find the k-th smallest stored element effectively.

For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

What I meant is that you can't use them directly, they don't have such methods.Krzysztof Duleba wrote:Not true - it's possible to use the underlying tree structure. However, such code is not portable.Neither set nor map can't be used to find the k-th smallest stored element effectively.

Still, I'm interested in your suggestion. I can imagine that I copy and paste the implementation of the red-black tree and modify it to suit my needs. But what you wrote suggests a more friendly possibility. Could you be more specific on this?

- Krzysztof Duleba
- Guru
**Posts:**584**Joined:**Thu Jun 19, 2003 3:48 am**Location:**Sanok, Poland-
**Contact:**

There are no obstacles to enhance trees on your own. I attach sample code that shows how to add subtree size information to nodes and how to maintain it after insertions. You can handle erase operation in a similar fashion.

Mind that this code is not portable. For some reason it works with all versions of g++ that I've tried, but it relies heavily on STL implementation aspects that are not standarized.

Mind that this code is not portable. For some reason it works with all versions of g++ that I've tried, but it relies heavily on STL implementation aspects that are not standarized.

Code: Select all

```
#include <set>
#include <map>
#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;
template<typename T>
struct Myset{
private:
map<T, int> mp;
typedef _Rb_tree_node<pair<const T, int> > _Node;
void fix_size(_Rb_tree_node_base * it, bool step_in = true){
int & it_size = static_cast<_Node *>(it) -> _M_value_field.second;
it_size = 1;
if(it -> _M_left != 0){
if(step_in)fix_size(it -> _M_left, false);
it_size += static_cast<_Node *>(it -> _M_left) -> _M_value_field.second;
}
if(it -> _M_right != 0){
if(step_in)fix_size(it -> _M_right, false);
it_size += static_cast<_Node *>(it -> _M_right) -> _M_value_field.second;
}
}
void fix_all_sizes(_Rb_tree_node_base * it, _Rb_tree_node_base * end){
if(it -> _M_left != 0)fix_size(it -> _M_left);
if(it -> _M_right != 0)fix_size(it -> _M_right);
do{
fix_size(it);
it = it -> _M_parent;
}while(it != end);
}
public:
void print()const{
const _Rb_tree_node_base * it = mp.begin()._M_node;
while(it -> _M_parent != mp.end()._M_node){
it = it -> _M_parent;
}
print_impl(it, "");
}
void print_impl(const _Rb_tree_node_base * it, string indent)const{
if(it == 0){
cout << indent << "nil (0)" << endl;
return;
}
cout << indent << static_cast<const _Node *>(it) -> _M_value_field.first;
cout << " (" << static_cast<const _Node *>(it) -> _M_value_field.second << ")" << endl;
if(it -> _M_left != 0 || it -> _M_right != 0){
print_impl(it -> _M_left, indent + " ");
print_impl(it -> _M_right, indent + " ");
}
}
void insert(const T & t){
pair<typename map<T, int>::iterator, bool> fit = mp.insert(pair<T, int>(t, -1));
if(fit.second == false)return;
fix_all_sizes(fit.first._M_node, mp.end()._M_node);
}
};
int main(){
Myset<int> st;
for(int i = 0; i < 30; ++i)st.insert(rand() % 100);
st.print();
}
```

For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...