Overloading operators with multi index container?
We are using a multi index container to store some data indexed both by a text key and by a timestamp. For the text key index, we are using a non-unique ordering like below: boost::multi_index::ordered_non_unique< boost::multi_index::tag<tags::key>, boost::multi_index::identity<Transaction> > Sometimes we have an issue where we get duplicate keys for transactions that aren't actually duplicates (don't ask). In this case, we can tell them apart by looking at their timestamp and checking if both transactions occurred within a certain window. To do this, we tried to overload operator< in the following way: bool MyTransaction::operator<(const Transaction & rhs) const { const std::time_t WINDOW = 2; if (getHashKey() == rhs.getHashKey()) { if ((epochTime() - WINDOW) <= rhs.epochTime() && (epochTime() + WINDOW) >= rhs.epochTime()) { return false; } else { return (epochTime() < rhs.epochTime()); } } else { return (getHashKey() < rhs.getHashKey()); } } This ought to work, under the assumption that equality is determined by checking that (lhs < rhs) is false and (rhs < lhs) is false. This doesn't seem to be working correctly though. If we add some logging inside the operator overload, we see that it only gets called once, not twice, when we call find() on that keyed index. What is the logic behind find()? I tried to take a look but it's so heavily templated that I couldn't see much more than that it was doing a tree traversal and using a comp() method that's provided as a template argument. Also, I am testing this with just one item in the container. That item has a matching key, but the timestamps are not within the time window I'm using in the operator< overload. I have not checked to see if the behavior is different for a container with many elements. I also tried overloading all the other comparison operators for kicks, and none of them get called ever either. Ideas? Thanks, Paul ________________________________ Note: This email is for the confidential use of the named addressee(s) only and may contain proprietary, confidential or privileged information. If you are not the intended recipient, you are hereby notified that any review, dissemination or copying of this email is strictly prohibited, and to please notify the sender immediately and destroy this email and any attachments. Email transmission cannot be guaranteed to be secure or error-free. Jump Trading, therefore, does not make any guarantees as to the completeness or accuracy of this email or any attachments. This email is for informational purposes only and does not constitute a recommendation, offer, request or solicitation of any kind to buy, sell, subscribe, redeem or perform any type of transaction of a financial product.
This ought to work, under the assumption that equality is determined by checking that (lhs < rhs) is false and (rhs < lhs) is false. This doesn’t seem to be working correctly though. If we add some logging inside the operator overload, we see that it only gets called once, not twice, when we call find() on that keyed index.
What is the logic behind find()?
I don't know the aswer to your question, but it might be worth trying to overload some other comparaison operators as well.
Paul Dovydaitis <pdovydaitis <at> jumptrading.com> writes:
We are using a multi index container to store some data indexed both by a text key and by a timestamp. [...] To do this, we tried to overload operator< in the following way: bool MyTransaction::operator<(const Transaction & rhs) const { const std::time_t WINDOW = 2; if (getHashKey() == rhs.getHashKey()) { if ((epochTime() - WINDOW) <= rhs.epochTime() && (epochTime() + WINDOW) >= rhs.epochTime()) { return false; } else { return (epochTime() < rhs.epochTime()); } } else { return (getHashKey() < rhs.getHashKey()); } }
This less-than operator is ill-defined according to the semantics expected by Boost.MultiIndex indexed indices (as well as STL associative containers and a number of stdlib algorithms). In particular the operator must implement a strict weak ordering: http://cpp-next.com/archive/2010/02/order-i-say/ Among other, a strict weak ordering has the property that "equivalence" defined as x~y := !(x<y) && !(y<x) is *transitive*, i.e. if x~y and y~z then x~z. Now consider three transactions x y and z with the same hash key and epoch times 0,2,4, respectively. According to your definition of operator<, x~y (their epoch times are within a distance of 2) and y~z (same argument), *but* x is *not* equivalent to z (the distance between their epoch times is 4). If your operator< does not implement a strict weark ordering, then ordered indices' behavior is undefined. Trying to analyze what happens under these conditions is basically pointless. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquin M Lopez Munoz wrote:
Paul Dovydaitis <pdovydaitis <at> jumptrading.com> writes:
We are using a multi index container to store some data indexed both by a text key and by a timestamp. [...] To do this, we tried to overload operator< in the following way: bool MyTransaction::operator<(const Transaction & rhs) const { const std::time_t WINDOW = 2; if (getHashKey() == rhs.getHashKey()) { if ((epochTime() - WINDOW) <= rhs.epochTime() && (epochTime() + WINDOW) >= rhs.epochTime()) { return false; } else { return (epochTime() < rhs.epochTime()); } } else { return (getHashKey() < rhs.getHashKey()); } }
This less-than operator is ill-defined according to the semantics expected by Boost.MultiIndex indexed indices (as well as STL associative containers and a number of stdlib algorithms). In particular the operator must implement a strict weak ordering:
http://cpp-next.com/archive/2010/02/order-i-say/
Among other, a strict weak ordering has the property that "equivalence" defined as x~y := !(x<y) && !(y<x) is *transitive*, i.e. if x~y and y~z then x~z. Now consider three transactions x y and z with the same hash key and epoch times
0,2,4,
respectively. According to your definition of operator<, x~y (their epoch times are within a distance of 2) and y~z (same argument), *but* x is *not* equivalent to z (the distance between their epoch times is 4).
If your operator< does not implement a strict weark ordering, then ordered indices' behavior is undefined. Trying to analyze what happens under these conditions is basically pointless.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Awesome answer, thanks Joaquín. We had overlooked the fact that operator< needs to implement a strict weak ordering - given that, I can see why what we are doing would have undefined behavior. We'll have to revisit what we're trying to do and find a different way to achieve our goal. -- View this message in context: http://old.nabble.com/Overloading-operators-with-multi-index-container--tp28... Sent from the Boost - Users mailing list archive at Nabble.com.
participants (4)
-
Igor R -
Joaquin M Lopez Munoz -
Paul Dovydaitis -
pdovydaitis