Sign in to follow this  
Thirthe

[STL\set] unsorted?

Recommended Posts

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).

What is your actual problem?

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.
also the tree must start with -1:
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this