# [STL\set] unsorted?

## Recommended Posts

Thirthe    128
hello, i have a problem that is solvable using trees. but these trees mustn't be sorted. can i use the STL trees as an ordinary BST?

##### Share on other sites
ZQJ    496
Well, you could use std::multiset and give it a comparison function which always returns false (i.e. make all elements equal). I don't think this will get you what you want however - while the STL set class is usually (or rather always, as far as I know) implemented by a tree, it isn't required to be by the standard and so none of the tree-like nature is exposed and you can't manipulate the tree yourself. In fact, there's no point in using std::multiset without a valid comparison function because you could just use std::list for the same effect (and better performance).

##### Share on other sites
Thirthe    128
well i'm trying to solve a problem that was on some programming contest.
i wish i'd had the instructions in english right about now :s

basically i have to get this tree:
       -1       20   60      77  0  1       666      123       18

and then i have to check whether A is a parent of B or B of A or neither.
but that should be easy, once i get the data structure right.

i solved this problem by implementing the tree by myself, but the teachers at my university recommended the use of STL, since the implemention time is of essence on these contests and i shouldn't "waste" it on re-inventing the wheel.

EDIT: formatting

##### Share on other sites
ZQJ    496
The real question for a problem like that is what the input format of the data is. Actually finding out if one node is an ancestor of another is a very simple problem, inputting the data may be a little more complex.

##### Share on other sites
Thirthe    128
1st line is the number of pairs,
the following lines are the actual pairs in form of (A,B), where B is ancestor of A.
8
1 60
18 666
77 20
20 -1
0 60
666 77
123 1
60 20

based on this data i then made this function:
void input(int ancestor_, int pair[][2], int n_, tree &tree_){	int i=0;	while(i<n_){		if(pair[i][1]== ancestor_){			tree.add(pair[i][0], pair[i][1]);			input(pair[i][0], pair, n_, tree_);		}		i++;	}	return;}

##### Share on other sites
ZQJ    496
In that case I think I see what your teachers are getting at: you don't need to construct the tree at all. From those pairs, you can straightforwardly construct a map from children to parents (i.e. via std::map), then use that to walk up the tree (which you'll need to do twice, as you're checking if either one is an ancestor of the other).

##### Share on other sites
Thirthe    128
very well, time for me to learn some std::map, then!
tnx