The Nightstar Zoo

Nightstar IRC Network - irc.nightstar.net
It is currently Sat Dec 16, 2017 4:18 am

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 7 posts ] 
Author Message
PostPosted: Thu Jul 01, 2004 2:09 am 
Offline
Energizer Bunny
User avatar

Joined: Wed May 22, 2002 12:24 am
Posts: 1634
the STL map, for those of you who don't usually use such a monster, works using a red-black binary tree, and a comparator function object that returns bool (usually the templated less<T>, which puts the objects in ascending order and uses the overloaded operator< to do its dirty work). Now, this is all well and good, so far. I can make such an operator. The problem is that I can't figure out how the map determines whether an object is unique (and thus whether to insert or replace it), and until I do I can't get it to accept that I want slightly fuzzier equality checking.

Does anyone have any resources that talk about this, or know exactly how it works?

Vorn


Top
 Profile  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 8:21 am 
You can pass it your very own compare function (it's actually a compare function object, but you'll have no trouble with the concept). In that compare function you can specially tailor your checking to be fuzzy if you like. :) From what I've been able to determine in my own experiments with that thing, you can actually use a function that does FULL comparison (not just "less", but "comp").

That's what the template is for (to pass in your own function if you like). Does this answer your question or just restate the problem?


Top
  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 8:44 am 
Offline
Nightstar Graveyard Daemon
User avatar

Joined: Mon Jun 03, 2002 8:30 pm
Posts: 1071
Location: Wouldn't you rather observe my Velocity?
Good Lord.

I dug into this, looking at stl_map.h and then into stl_tree.h; ultimately the redblack tree is performing a comparison on the objects. Unfortunately, it's seventeen layers of templates deep and I can't make heads nor tails of it.

This might be a good question for #stl on freenode (assuming there *is* such a channel).

What I personally would expect, and I reserve the right to be completely wrong, is that the STL would check the objects operator== function. I base this assumption on the fact that the sorting and searching algorithms in the STL require you to implement == and <, and they use those. BTW, my reading of the code leads me to believe that if the item is already in the map, the insert will fail, not replace. You might be using a different insert, though. Anyway, what I saw in there looks like it *should* fail if operator== returns true, and return pair<iterator to existing node, false>. If == returns false, then the insert goes ahead and we return pair<iterator to newly inserted node, true>.

Another tack to look at, the functionality you are looking for is idiomatic in the concept of a cmp() function. cmp is a three-value compare: -1 if a < b, 0 if a==b, and 1 if a>b.

There is a clever STL include/template thingy you can include, can't remember what it's called, you'll have to ask around. But essentially, if you write operator< and operator==, it will write !=, >, >=, <= and cmp for you (since these can all be derived from < and ==).

Good luck!

Oh, P.S. this is a very trivial operator== that should probably work for your needs. All it does is test to see if the objects are the same object, not if they have the same value:
Code:
MyClass::operator==(const MyClass &that) {
    return ( *this == that );
}


Top
 Profile  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 10:01 am 
Offline
Energizer Bunny
User avatar

Joined: Wed May 22, 2002 12:24 am
Posts: 1634
hmn, hmn, hmn. As much as I'd like to believe Raif, the stuff I've seen doesn't match up with that...

Chalain's sounds right, though.

...except that his operator== is actually the exact opposite of fuzziness. :)

Vorn


Top
 Profile  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 1:34 pm 
Chalain wrote:
What I personally would expect, and I reserve the right to be completely wrong, is that the STL would check the objects operator== function. I base this assumption on the fact that the sorting and searching algorithms in the STL require you to implement == and <, and they use those.


According to this book on the STL, it actually uses less<T> and greater<T>, which are just function class templates that call operator< and operator>. If less and greater both return false, it assumes equality. I might be misunderstanding, or it might be out of date (it's a few years old).


Top
  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 1:38 pm 
Offline
Energizer Bunny
User avatar

Joined: Wed May 22, 2002 12:24 am
Posts: 1634

Hmm...reading my STL reference, it looks like the map template takes a comparison parameter:

Code:
template <class Key, class T, class Compare = less, class Allocator = allocator>


The Compare class has to define a strict weak ordering (x E y if and only if both x R y and y R x are false). It's a class that overloads the () operator so that it takes two arguments of the type to be compared and returns a bool. (emphasis mine)


That is what I needed to know. Thank you very much, folks!

Vorn


Top
 Profile  
 
 Post subject:
PostPosted: Thu Jul 01, 2004 9:30 pm 
Vorn the Unspeakable wrote:
hmn, hmn, hmn. As much as I'd like to believe Raif, the stuff I've seen doesn't match up with that...

You're right. It's been 3 months since I touched it. :) At the time I tried to use it but realized after a while of trying to get it to behave elegantly that it most definitely was not what I needed.

All in all I'd peg it as a very kludgy solution to a keyed data set, but that's just me.


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 7 posts ] 

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group