OJ Board

Posted: **Thu Jan 19, 2006 12:23 pm**

Is STL set in fact a binary search tree?
Or is the running time of set::find() and set::insert() O(log n)?

Posted: **Thu Jan 19, 2006 12:58 pm**

A balanced binary tree is more likely. A binary search tree has a worst case performance no
better than a linked list. Look up red-black trees, AVL etc.

Posted: **Thu Jan 19, 2006 1:22 pm**

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:

Code: Select all

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

Is there any faster way?
I'm sorry I'm not very familiar with STL.

Posted: **Thu Jan 19, 2006 1:33 pm**

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

Why would you want that? How do you want the index to be calculated ?
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.

Posted: **Thu Jan 19, 2006 2:01 pm**

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.

Posted: **Thu Jan 19, 2006 3:56 pm**

I would suggest using the STL map using (index,value) pair.

Code: Select all

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

Then use the find function in STL map (it runs in O(log n) time) or do this:

Code: Select all

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

Of course for the example given, the map needs to have at least 10 elements inside.

Posted: **Thu Jan 19, 2006 4:21 pm**

chunyi81 wrote:I would suggest using the STL map using (index,value) pair.

Neither set nor map can't be used to find the k-th smallest stored element effectively. For problem 10909 I implemented my own splay tree.

Posted: **Fri Jan 20, 2006 6:11 am**

Neither set nor map can't be used to find the k-th smallest stored element effectively.

Not true - it's possible to use the underlying tree structure. However, such code is not portable.

Posted: **Fri Jan 20, 2006 12:37 pm**

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

What I meant is that you can't use them directly, they don't have such methods.

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?

Posted: **Fri Jan 20, 2006 5:59 pm**

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.

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();
}

OJ Board

Is STL set a binary search tree?

Is STL set a binary search tree?