3
\$\begingroup\$

In C++11 we have the option of using std::unordered_set if we require a list of elements that have no duplicates but order is not important.

In C++03 we don't have this options, although we can use the std::set to achieve something similar. Let's consider the following code:

std::set<ElementType, std::NotEqualTo<ElementType>> unorderedSet;
unorderedSet.insert(some_element);
unorderedSet.insert(other_element);
unorderedSet.insert(some_element);

//... more stuff with the set

This will, basically produce a set that will store the elements in the order they were inserted while preventing duplicates. Note that ElementType simply can't have less than or greater than operator. It doesn't make sense, semantically speaking.

Anyway, since I am using std::NotEqualTo instead of a LessThan functor, as it is requested by the set, I am not feeling very comfortable with this code. I do know that set is using something such as

if first element < second element
    //insert accordingly 
else if second element < first element
    //insert accordingly
else
   //they are equal

but in the same time, theoretically, my code will be failing if the checks were more strict such as

if first element < second element AND !(second element < first element)
//...

My questions are:

  1. There are any potentially problems that could arise from using this construct?
  2. What other alternatives I have to achieve the same thing in a more readable form? I do not plan to write my own unordered set just for this scenario and can't really use any external libraries. Only standard library available in C++03.

Edit: I am unable to make use of "less than" operator between my elements. I can decide if they are equal or not but I can't say which one is smaller than other. With the default set functor the code won't even compile as "operator<" is not found. This is why I wanted to model the functor with equal operator in the first case.

I am also aware that it is not valid, however, the code will produce the desired results. From my understanding it will expand to something such as:

if first element != second element
    // place first element
else if second element != first element
    // this is buggy, but should never be executed; first condition will always be true, unless the elements are equal.
else
    //here the elements are equal .
\$\endgroup\$
  • 3
    \$\begingroup\$ Using std::NotEqualTo is not valid. The comparator must generate a strict weak ordering for the code to work. \$\endgroup\$ – Martin York Oct 9 '13 at 20:43
  • \$\begingroup\$ see: sgi.com/tech/stl/set.html About half way down the page you will see the requirements on comparator Compare The key comparison function, a Strict Weak Ordering whose argument type is key_type; it returns true if its first argument is less than its second argument, and false otherwise. This is also defined as set::key_compare and set::value_compare. less<Key>. Then sgi.com/tech/stl/StrictWeakOrdering.html is defined here. \$\endgroup\$ – Martin York Oct 9 '13 at 20:45
6
\$\begingroup\$

My questions are:

There are any potentially problems that could arise from using this construct?

Its not valid.
The code will not work as expected as the std::set requires the comparator type to generate a strict weak ordering between elements.

What other alternatives I have to achieve the same thing in a more readable form? I do not plan to write my own unordered set just for this scenario and can't really use any external libraries. Only standard library available in C++03.

You can use std::set as an unordered container as is. If you have an unordered container it does not matter to you what order the elements are in. If they just happen to be ordered does that matter?

The reason for using std::unordred_set is that it provides faster access to the elements. You give up an ordered property to get better performance.

Container:           Insert     find
std::set             O(ln(n))  O(ln(n))
std::unordered_Set   O(1)      O(1)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.