Asked  6 Months ago    Answers:  5   Viewed   70 times

How to define operator< on n-tuple (for example on 3-tuple) so that it satisfy strict weak ordering concept ? I know that boost library has tuple class with correctly defined operator< but for some reasons I can't use it.

 Answers

39
if (a1 < b1)
  return true;
if (b1 < a1)
  return false;

// a1==b1: continue with element 2
if (a2 < b2)
  return true;
if (b2 < a2)
  return false;

// a2 == b2: continue with element 3
if (a3 < b3)
  return true;
return false; // early out

This orders the elements by a1 being most siginificant and a3 least significant.

This can be continued ad infinitum, you could also e.g. apply it to a vector of T, iterating over comparisons of a[i] < a[i+1] / a[i+1] < a[i]. An alternate expression of the algorithm would be "skip while equal, then compare":

while (i<count-1 && !(a[i] < a[i+1]) && !(a[i+1] < a[i])
  ++i;
return i < count-1 && a[i] < a[i+1];

Of course, if the comparison is expensive, you might want to cache the comparison result.


[edit] removed wrong code


[edit] if more than just operator< is available, I tend to use the pattern

if (a1 != b1)
  return a1 < b1;

if (a2 != b2)
  return a2 < b2;

...
Tuesday, June 1, 2021
 
aslum
answered 6 Months ago
22

This is certainly going to make it easier to write a correct operator than rolling it yourself. I'd say only consider a different approach if profiling shows the comparison operation to be a time-consuming part of your application. Otherwise the ease of maintaining this should outweigh any possible performance concerns.

Saturday, June 5, 2021
 
employeegts
answered 6 Months ago
43

Yeah, it's invalid, but not because you're converting a char* to an A*: it's because you are not obtaining a A* that actually points to an A* and, as you've identified, none of the type aliasing options fit.

You'd need something like this:

#include <new>
#include <iostream>

struct A
{
  int t;
};

char *buf = new char[sizeof(A)];

A* ptr = new (buf) A;
ptr->t = 1;

// Also valid, because points to an actual constructed A!
A *ptr2 = reinterpret_cast<A*>(buf);
std::cout << ptr2->t;

Now type aliasing doesn't come into it at all (though keep reading because there's more to do!).

  • (live demo with -Wstrict-aliasing=2)

In reality, this is not enough. We must also consider alignment. Though the above code may appear to work, to be fully safe and whatnot you will need to placement-new into a properly-aligned region of storage, rather than just a casual block of chars.

The standard library (since C++11) gives us std::aligned_storage to do this:

using Storage = std::aligned_storage<sizeof(A), alignof(A)>::type;
auto* buf = new Storage;

Or, if you don't need to dynamically allocate it, just:

Storage data;

Then, do your placement-new:

new (buf) A();
// or: new(&data) A();

And to use it:

auto ptr = reinterpret_cast<A*>(buf);
// or: auto ptr = reinterpret_cast<A*>(&data);

All in it looks like this:

#include <iostream>
#include <new>
#include <type_traits>

struct A
{
  int t;
};

int main()
{
    using Storage = std::aligned_storage<sizeof(A), alignof(A)>::type;

    auto* buf = new Storage;
    A* ptr = new(buf) A();

    ptr->t = 1;

    // Also valid, because points to an actual constructed A!
    A* ptr2 = reinterpret_cast<A*>(buf);
    std::cout << ptr2->t;
}

(live demo)

Even then, since C++17 this is somewhat more complicated; see the relevant cppreference pages for more information and pay attention to std::launder.

Of course, this whole thing appears contrived because you only want one A and therefore don't need array form; in fact, you'd just create a bog-standard A in the first place. But, assuming buf is actually larger in reality and you're creating an allocator or something similar, this makes some sense.

Friday, August 6, 2021
 
Kai
answered 4 Months ago
Kai
57

Partial ordering is, essentially, <=. If both a <= b and b <= a then you may say that a is equivalent to b. But it's also possible that neither a <= b nor b <= a - the two elements are incomparable. As a result, you cannot impose a total order (like std::sort would need to) on a set with partial ordering relation - at best you can do a topological sort. Nor can you derive an equivalence relation - again, there may be elements that are incomparable.

Strict weak ordering is like <. It doesn't allow having both a < b and b < a, and if neither a < b nor b < a, you can just pronounce a and b equivalent.

Total ordering is simply strict weak ordering where two elements are equivalent if and only if they are equal (which is only meaningful if you have an equality comparison predicate in addition to less-than predicate, and there is no C++ standard library algorithm that uses both at the same time, so the issue is largely moot in this context).

Tuesday, August 10, 2021
 
simPod
answered 4 Months ago
94

The only consequence of not using a WeakReference is that the reference in your dictionary will prevent the View Model instances from being garbage collected. A WeakReference allows garbage collection (assuming there are no other solid references elsewhere).

An item becomes eligible for garbage collection when it has no references to it. WeakReference does not create a "countable" reference, thus you can keep a sort-of-reference to it, but still let it be eligible if your WeakReference is the only thing left looking at it.

Whether you need it or not really depends on what sort of life-cycle your View Models have. If they need disposing or otherwise "letting go of", then you may need to use WeakReference or expose a way to remove the reference from the dictionary instead.

As I mention in the comments. I tend to err away from using WeakReference as opposed to handling the life-cycle of the relevant objects explicitly. That said, they are useful when you simply don't have visibility of the life-cycle at the relevant points. I think in your situation, you should have the necessary visibility, as these are all likely in the UI layer, and thus should try to not use them.

Here is a resource on the topic:

  • Weak References MSDN article

Guidelines extract from the above MSDN link:

Use long weak references only when necessary as the state of the object is unpredictable after finalization.

Avoid using weak references to small objects because the pointer itself may be as large or larger.

Avoid using weak references as an automatic solution to memory management problems. Instead, develop an effective caching policy for handling your application's objects.

I believe the last guideline point applies to your situation.

Thursday, October 28, 2021
 
Seán McCabe
answered 1 Month ago
Only authorized users can answer the question. Please sign in first, or register a free account.
Not the answer you're looking for? Browse other questions tagged :
 
Share