STL set::count() help needed

Quote:

Original post by BerwynIrish C:/msys/1.0/mingw/bin/../lib/gcc/mingw32/3.4.2/../../../../include/c++/3.4.2/bits/stl_tree.h:1129: error: passing const compSavedMsg' as this' argument of `bool compSavedMsg::operator()(const SavedMsg&, const SavedMsg&)' discards qualifiers

Your compSavedMsg::operator()(const SavedMsg&, const SavedMsg&) is not const-correct. It should be compSavedMsg::operator()(const SavedMsg&, const SavedMsg&) const.

Σnigma

By default the less than operator is used to sort the set. You can change the type of comparison done with the second template argument (by default it's std::less), but it does have some requirements (which == doesn't meet).

EDIT: Oh, you did try to define a comparison function. I didn't see that, just assumed you didn't because of the code snippet which doesn't show it.

Quote:

Original post by Enigma Quote: Original post by BerwynIrish C:/msys/1.0/mingw/bin/../lib/gcc/mingw32/3.4.2/../../../../include/c++/3.4.2/bits/stl_tree.h:1129: error: passing const compSavedMsg' as this' argument of `bool compSavedMsg::operator()(const SavedMsg&, const SavedMsg&)' discards qualifiers Your compSavedMsg::operator()(const SavedMsg&, const SavedMsg&) is not const-correct. It should be compSavedMsg::operator()(const SavedMsg&, const SavedMsg&) const. Σnigma

Thanks. That fixed it. Although I'm so rusty in c++ that I have no idea what that extra const means, but I mean to look into it. Going under the hood, why would count use that particular comparison function anyway? I thought it was only there for sorting purposes when an element is inserted. I can see how it can be used to test for equality (if !(a < b) && !(b < a)) then a == b, but it would seem more efficient if there was an actual straight test for equality when that's all you're doing (like in counting elements), which is why I figured I would have to end up doing something like defining operator== for my class.

Quote:

Original post by BerwynIrish Thanks. That fixed it. Although I'm so rusty in c++ that I have no idea what that extra const means, but I mean to look into it. Going under the hood, why would count use that particular comparison function anyway? I thought it was only there for sorting purposes when an element is inserted. I can see how it can be used to test for equality (if !(a < b) && !(b < a)) then a == b, but it would seem more efficient if there was an actual straight test for equality when that's all you're doing (like in counting elements), which is why I figured I would have to end up doing something like defining operator== for my class.

Sorting algorithms are often implemented easier and sometimes more efficiently with a less than operator. For example here is Wikipedia's pseudocode for merging two sorted sequences (a part of merge sort which is what pretty much all C++ implementations use for unsorted sequences):

function merge(left,right)    var list result    while length(left) > 0 and length(right) > 0        if first(left) ≤ first(right)            append first(left) to result            left = rest(left)        else            append first(right) to result            right = rest(right)    if length(left) > 0         append left to result    if length(right) > 0         append right to result    return result

Note that they use less than or equal, not equal. The code could easily use less than instead, but it would get quite a lot more complicated and less efficient if you choose to use equal instead.

EDIT: Actually, using an equal operator wouldn't even work under practical constraints (merge sort could still be done in O(n*log₂(n)) for finite sets, but the coefficient would get considerably larger (it would get as many times larger as the average number of objects between two adjacent objects)). How would you choose where to insert 5 in the following sequence without using less than or greater than?
2 3 4 8 9
If we had a less than operator we could just go through the sequence from the back and insert 5 when the current element is less than 5. So in this example we would start by allocating an extra space at the end:
2 3 4 8 9 NIL
We would start at 9 and see that 5 < 9 so we move 9 one place forward (we shift them all one place to make room for the inserted number)
2 3 4 8 NIL 9
We then see that 5 < 8 so we move 8 one place forward.
2 3 4 NIL 8 9
We then see that 5 < 4 is false and therefore insert 5.
2 3 4 5 8 9.
How would you do that with an equal operator?

[Edited by - CTar on December 29, 2006 2:30:29 PM]

Quote:

Original post by BerwynIrish Thanks. That fixed it. Although I'm so rusty in c++ that I have no idea what that extra const means, but I mean to look into it.

A good place to start on that is at the C++ FAQ Lite (in this case section 18.10).

set's specification is that it only uses < (or a similiar ordering function) for comparisons between elements. Because of this, along with the performance specs, its implementation is virtually guaranteed to be some sort of tree. Navigating a tree structure efficiently can require comparisons to choose which branch to explore, so even an operation like count() will use comparisons. The error only occured for count because count is a const function, meaning it won't alter the set's data. The comparison it uses must therefore also be const.

Quote:

Original post by CTar EDIT: Actually, using an equal operator wouldn't even work under practical constraints (merge sort could still be done in O(n*log2(n)) for finite sets, but the coefficient would get considerably larger (it would get as many times larger as the average number of objects between two adjacent objects)). How would you choose where to insert 5 in the following sequence without using less than or greater than? 2 3 4 8 9 If we had a less than operator we could just go through the sequence from the back and insert 5 when the current element is less than 5. So in this example we would start by allocating an extra space at the end: 2 3 4 8 9 NIL We would start at 9 and see that 5 < 9 so we move 9 one place forward (we shift them all one place to make room for the inserted number) 2 3 4 8 NIL 9 We then see that 5 < 8 so we move 8 one place forward. 2 3 4 NIL 8 9 We then see that 5 < 4 is false and therefore insert 5. 2 3 4 5 8 9. How would you do that with an equal operator?

You misunderstood me. I wasn't expecting an equal-comparison function to completely replace the less-than function which sets require; I was expecting to have to define an additional function that defines equality for functions that ultimately only care whether or not there is an equality. I wasn't expecting my hypothetical function to play any part in sorting or insertion. I was thinking that functions like find() and count() would find a simple equality definition useful, rather than indirectly determining equality by using the less-than definition.

An equality function wouldn't necessarily be useful to a binary tree data structure.

When traversing the tree, the value in each node must be compared to the value we're searching for. If this comparison returns true, then we know which child to visit. If it returns false, we must check for equality to know if we have found the node we want or if we must visit the other child. But since we've already done the comparison one way, we can just do the comparison the other way to determine equality. There's never a situation where we must check for equality before having done the comparison in one of the directions (and if you try to check for equality first then you'll end up with a higher number of expected operations).

If equality is a much cheaper operation than comparison, then there is possibly some room for optimization...