Detecting a bad item inserted into a std::set

Question

Say I have a custom type in my set, and the set/ordering only makes sense if all items have the same value on some property... if an item with a different value is inserted the model is screwed up and I want to protect this.

I thought maybe the comparison function might be a place we could test this (as an assert or exception) to either flag the problem and/or prevent the item getting inserted. e.g on TypeName, operator<() always returns false if the important attribute isn't equal.

Is this reasonable?

Jeff Foster · Accepted Answer · 2011-09-23T10:50:23.183

6

I guess putting it in the comparator could have issues as you've not got any guarantees when it's going to be called. Perhaps some mythical implementation stores items in a list when the number of items is small and doesn't call the comparator until later?

Probably the simplest approach would be to wrap the std::set in a protective outer class that performed these assertions.

class MySet {
  private:
     std::set<myFunkyType> myType;

  public:
     void insert(myFunkyType type) {
        assert(!type.isFunky(), "funk violation");
        // and so on
     }

     // all other members other than insertion or mutation just delegate to the
     // underlying set

}

edited Sep 23 '11 at 10:50

answered Sep 23 '11 at 08:33

Jeff Foster

43,770
11
86
103

how about public inheritance? MySet *is* really *a* set and you don't have to write all the wrapper functions... – Karoly Horvath Sep 23 '11 at 08:39
1

@yi_H: My understanding is STL containers aren't really designed to be subclassed, though I forget why. – Mr. Boy Sep 23 '11 at 08:40
@Jeff: if I simply want to stop it getting inserted, maybe not a problem - but yes if I want to alert about it this is a good point. – Mr. Boy Sep 23 '11 at 08:41
1

@John: http://stackoverflow.com/questions/1647298/why-dont-stl-containers-have-virtual-destructors – Karoly Horvath Sep 23 '11 at 08:44
That is a peculiar way to write assertions you have there ;) – visitor Sep 23 '11 at 08:44
@yi_H: a conversion operator can do the hob here. – Alexandre C. Sep 23 '11 at 08:51

score 0 · Answer 2 · answered Sep 23 '11 at 08:41

If your std::set is an implementation detail of a custom class then it should be up to your class's public member functions to ensure that invalid elements aren't inserted in your set. Otherwise, if you need a data structure to pass a collection of your objects around use a std::map instead, provide your class with a key generating function and put your error detection code there.

Remember that set elements, as map keys, should be immutable with respect to their ordering; basing ordering on mutable state smells bad.

I never said it was mutable. And of course the controlling class which owns the set should be checking this, but I want to be certain because this would be a hard kind of bug to track down. — Mr. Boy, Sep 23 '11 at 08:49

score 0 · Answer 3 · answered Sep 23 '11 at 08:42

0

The operator< idea sounds a bit fishy. It would merely mean that such elements are ordered last. x is the largest element iff x<y==false for all y, and x<x==false must always hold. But if that's acceptable to you, it's OK.

answered Sep 23 '11 at 08:42

MSalters

173,980
10
155
350

score 0 · Answer 4 · answered Sep 23 '11 at 08:47

0

When in your op< you detect that you can not establish a strict weak ordering, the only reasonable thing is to throw an exception. Any kind of insert, or possible other return from op< will likely break the internal constraints of the set.

Wrapping is IMHO not really necessary, since the behaviour of your wrapped insert() would probably be the same (that is, throw an exception).

The only thing that might make wrapping more attractive is any uncertainty about whether your standard library implementation is good enough to be able to cope with a throwing comparator. I doubt that many standard library implementations are strong on exception safety at that operation.

answered Sep 23 '11 at 08:47

PlasmaHH

15,673
5
44
57

I think the implementations should be strong enough: `if an exception is thrown by an insert() function while inserting a single element, that function has no effects.` - It also shouldn't be hard to achieve: you don't start modifying the container before you have determined the place for the new item (and successfully allocated the node for it). – visitor Sep 23 '11 at 08:53
@visitor: Therefore the fuzzy words of *might* and *uncertainty*. You also say they *should* but I really doubt that this area has been tested thoroughly, and since we don't know how much the OP cares about portability, we should at least make him think about it. Or even test it. – PlasmaHH Sep 23 '11 at 08:56
No, it is a general requirement in the language standard that single element insert functions are exception-proof. - Your answer makes sense, I just wanted to point out that the concerns might be unfounded. – visitor Sep 23 '11 at 09:24
@visitor: when there are widespread compilers that can bind non-const references to temporaries (msvc) then I think it is a pretty reasonable thing to wonder if an implementation are implementing certain other things equally well – PlasmaHH Sep 23 '11 at 10:09

Detecting a bad item inserted into a std::set

4 Answers4