Is there a concept name for a regular type for which comparisons doesn't compare the full object state?

Question

I have a set of types which looks like this:

struct MyFlag
{
     SomeId source_id; // INVALID_ID by default
     SomeData data; // regular type

     friend bool operator==( const MyFlag& a, const MyFlag& b ) { return a.source_id == b.source_id; }
     friend bool operator<( const MyFlag& a, const MyFlag& b ) { return a.source_id < b.source_id; }
     friend bool operator!=( const MyFlag& a, const MyFlag& b ) { return !(a == b); }

     friend bool operator==( const SomeId& a, const MyFlag& b ) { return a == b.source_id; }
     friend bool operator<( const SomeId& a, const MyFlag& b ) { return a < b.source_id; }
};



MyFlag flag_a { id, data_A };
MyFlag flag_b { id, data_B };

assert( flag_a == flag_b );
assert( flag_a.data != flag_b.data );
assert( flag_a == id );
assert( flag_b == id ); 

MyFlag flag = flag_b;
assert( flag == flag_a );
assert( flag == id );
assert( flag.data != flag_a.data );

const MyFlag flag_x ={ id_x, data_A };
flag = flag_X;
assert( flag != flag_a );
assert( flag.data == flag_a.data );

That is, only a specific part of the state of the object is considered in comparison: in this example, any MyFlag object would be compared to others using their ids, but not the rest of the data they contain.

I think it match the definition Sean Parent gave of a "value type", but I also think this is a strange or unfamiliar (but useful in my case) pattern.

So my question is: is there a concept name for this ... concept?

---

How is that kind of type useful? I use this kind of type in a "black board" event system which is basically a kind of set of any value that have a type that is at least regular. However, this black board systematically overwrite the value pushed (inserted) in it even if it's already found (through comparison). That way, I overwrite the full state of a value in the black board using the comparison operators as identifiers.

I have no idea if it's a well known pattern or idea or if it's problematic on the long run. So far it have been very useful. It also feels like something that might be "too smart", but I lack experience with this pattern to confirm that. It might be that I am abusing the use of comparison operators, but it feels that the semantic of these types is correct in my use.

I can provide a detailed example of my usage if necessary.

Answer 1

The type has correct comparison operators defining a total ordering and is therefore TotallyOrdered (using the N3351 definition).

That does not distinguish whether the total ordering compares all of the object state or not, but there does not seem to be any concept for differentiating that. Because it would neither be possible to define (the == says the objects are equal based on the compared part of the state, how can you tell whether there is also any uncompared part?) nor does any algorithm reason to care.

Answer 2

MyFlag is not EqualityComparable, since == returns true for objects with distinct values. The definition of EqualityComparable in §3.3 includes axiom { a == b <=> eq(a, b); }.

Informally, eq is meant to represent equality of what we would consider to be the value of an object regardless of the existence of an == for that object's type. This isn't strictly the same thing as representational equality, since (a) different representations can be considered equal (e.g., -0.0 == 0.0), and (b) there can be insignificant state in representations (colloquially "padding").

In the case of MyFlag, I find it almost certain that data would be considered significant in the value of a MyFlag in some context (several occurrences appear in the OP itself). Formally, I could define an operator cmp over MyFlag as:

bool cmp(const MyFlag& a, const MyFlag& b) {
  return a == b && a.data == b.data;
}

which clearly provides a stronger interpretation of equality than the corresponding operator ==.

Consider an implementation of std::copy:

template <typename In, typename Out>
Out copy_(In first, In last, Out out, std::false_type) {
  while(first != last) {
    *out++ = *first++;
  }
}

template <typename In, typename Out>
Out copy_(In first, In last, Out out, std::true_type) {
  while(first != last) {
    *out = *first;
    *out.data = SomeData();
    ++first;
    ++out;
  }
}

template <typename In, typename Out>
Out copy(In first, In last, Out out) {
  copy_(first, last, out, std::is_same<
          Myflag,
          typename std::iterator_traits<In>::value_type>());
}

Would you consider this to be a valid implementation of copy, or would you say it is corrupting data? It is equality-preserving according to Myflag's operator ==.

Contrastingly, had Myflag been defined as:

class MyFlag
{
     SomeData trash_bits;
public:
     SomeId source_id; // INVALID_ID by default

     friend bool operator==( const MyFlag& a, const MyFlag& b ) { return a.source_id == b.source_id; }
     friend bool operator<( const MyFlag& a, const MyFlag& b ) { return a.source_id < b.source_id; }
     friend bool operator!=( const MyFlag& a, const MyFlag& b ) { return !(a == b); }

     friend bool operator==( const SomeId& a, const MyFlag& b ) { return a == b.source_id; }
     friend bool operator<( const SomeId& a, const MyFlag& b ) { return a < b.source_id; }
};

you could make a compelling argument that trash_bits are not part of the value of a MyFlag since they are never observed. Then I would agree that MyFlag is Regular.

Answer 3

I think you should distinguish between the level at which you apply your relational operators and their semantics. Your operators seem to have the correct semantics, but are applied at a confusing level (ID member, rather than the whole object).

First, I would define operator== and operator< to compare the entire object state. This is the least surprising and most idiomatic way. To only compare ids, just make a named operator id_equal_to that does a projection onto the ID data member. If you like, you can even define mixed versions (taking one MyFlag and one SomeID parameter), but that is usually only necessary to avoid overhead of implicit conversions. It doesn't seem required in this case.

Second, to make sure that these operators have the correct semantics (reflexive, symmetric and transitive for operator==, and irreflexive, asymmetric, transitive and total for operator<), just define them in terms of std::tie and the corresponding operator for std::tuple. You should also make sure that operator== and operator< on SomeId also has the correct semantics. For builtins, this is guaranteed, but for user-defined ID types, you can apply the same std::tie trick again.

#include <cassert>
#include <tuple>

enum { invalid = -1 };
using SomeId = int;   // or any regular type with op== and op<
using SomeData = int; // or any regular type with op== and op<

struct MyFlag
{
    SomeId source_id; // INVALID_ID by default
    SomeData data;    // regular type

    friend bool operator==(MyFlag const& a, MyFlag const& b) 
    { return std::tie(a.source_id, a.data) == std::tie(b.source_id, b.data); }

    friend bool operator!=(MyFlag const& a, MyFlag const& b) 
    { return !(a == b); }

    friend bool operator<(MyFlag const& a, MyFlag const& b) 
    { return std::tie(a.source_id, a.data) < std::tie(b.source_id, b.data); }

    // similarly define >=, >, and <= in terms of !(a < b), (b < a) and !(b < a)

    friend bool id_equal_to(MyFlag const& a, MyFlag const& b)
    { return a.source_id == b.source_id; }    
};

int main()
{    
    auto const id = 0;
    auto const data_A = 1;
    auto const data_B = 2;

    MyFlag flag_a { id, data_A };
    MyFlag flag_b { id, data_B };

    assert( flag_a != flag_b );
    assert( id_equal_to(flag_a, flag_b) );
    assert( flag_a.data != flag_b.data );

    MyFlag flag = flag_b;
    assert( flag != flag_a );
    assert( id_equal_to(flag, flag_a) );
    assert( flag.data != flag_a.data );

    auto const id_x = invalid;
    const MyFlag flag_x = { id_x, data_A };
    flag = flag_x;
    assert( flag != flag_a );
    assert( id_equal_to(flag, flag_x) );
    assert( !id_equal_to(flag, flag_a) );
    assert( flag.data == flag_a.data );    
}

Live Example.

Answer 4

I think you might find the answer in this paper from John Lakos, specificly in the background section. In short Lakos distinguishes the salient attributes which make up the value of an object vs. the non-salient attributes (I remember them being called incidental attributes, too but might be wrong about that) that do not (like e.g. the capacity of a vector).

Answer 5

What you seem to be describing is a non-essential part. It is very similar to capacity() on an std::vector. The concept of Regular is defined in terms of the semantics of copy, assignment, and equality. So long as those semantics are obeyed, your type is Regular. You need to decide what the essential part of you type are by deciding what it is that the type represents. The essential parts, those that contribute to what the object represents, must be copies and included in equality comparison.