1

This is an interview question.

Referring to the sample code, which one of the operators needs to be overridden in order to use std::set<Value>

 #include<iostream>

 class Value
 {
      std::string   s_val;
      int           i_val;
  public:
      Value(std::string s, int i): s_val(s) , i_val(i){}
 };

 // EOF

 /*
 a       operator !=
 b       operator >
 c       operator <=
 d       operator >=
 e       operator <
 */

Actually, I do not understand why an operator needs to be overridden here. "set" does not allow duplicated elements, maybe operator != needs to be overridden ?

Improve this question
3
  • 1
    Overriding operator!= (or operator==) it would be difficult to maintain the complexity guarantees, don't you think? Still I find this question sort of sad... Commented Jun 3, 2012 at 17:10
  • -1 as you didn't appear to have tried to find out about what a std::set is and does. Commented Jun 3, 2012 at 17:53
  • possible duplicate of std::set with user defined type, how to ensure no duplicates Commented Jun 3, 2012 at 19:19

4 Answers 4

Reset to default
5

You don't have to override any operator, the std::set class template allows you to provide a comparison function as a template parameter. But if you were to provide an operator, the one needed is bool operator<(). This operator has to implement strict weak ordering. See this std::set documentation.

The reason strict weak ordering is used is because set is an ordered container, typically implemented as a self-balancing binary tree. So it is not enough to know whether two elements are the same or not. The set must be able to order them. And the less than operator or the comparator functor are also used to test for element equality.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I'm confused by your "you don't have to override any operator". If std::set<Value> is to be used, then std::less<Value> will be used by default. Doesn't this require operator<?
@Walter you can pass your own comparator as second template parameter to set, which then replaces the default, std::less<Value>. This is very handy because ofter you want to make sets containing objects of types that have no operator < and over which you have no control.
+1 okay, I misread your answer. Of course, if you provide the 2nd template argument, then you don't need to provide the operator<. And yes that can be very handy, in particular as you may not want to provide that operator as it may confuse other code, or (as you said) if there is already an operator< with another meaning than your intended ordering.
I would +1 this but the answer seems incomplete it contains no answer to the question, just a hint that the answer does exist somewhere! Syntax examples really help, especially with something that is described as just a second parameter.
@CoryTrese OP is asking which operators need to be overloaded, and I am answering that question. The references should be enough for anyone to figure out the rest.
|
3

You need to implement operator< for your type. The implementation must follow strick weak ordering to be able to use with associative containers from Standard library such as std::set and std::map.

Read about:

An example here:

Improve this answer

Comments

2

A set keeps out the duplicates without needing operator= or operator!= by using the notion of equivalence. Two items are equivalent if neither is less than the other:

if (!(a < b || b < a))
    // equivalent!
Improve this answer

Comments

0

To speed up the enforcement of no duplicate elements and generally checking if element is in its usually some sort of a tree and only needs operator <. (The only usage of less is enforced by the standard, the rest is just the avarage implementation)

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.