Is it possible to use elements of a different type than contained in a std::set to perform search and deletion?

Question

Let's say I have the following:

struct MetadataThingy {

    void *actual_thingy;
    int some_metadata;
    int more_metadata;

    bool operator<(MetadataThingy const& other) const {
        return actual_thingy < other.actual_thingy;
    }

};

where actual_thingy points to some data of importance and I want the container ordered by the value of actual_thingy rather than the value of the element pointed at, but I need to store some other data about it, so I created the wrapper class MetadataThingy with a comparator that only considers the value of the actual_thingy pointer (rather than using a container of void *)

Now, given the following code:

std::set<MetadataThingy> thingy_set;

void test() {

    MetadataThingy m1 { nullptr, 5, 20 };
    MetadataThingy m2 { &m1, 1, 2 };
    MetadataThingy m3 { &m2, 6, 0 };

    thingy_set.insert(m1);
    thingy_set.insert(m2);
    thingy_set.insert(m3);

    MetadataThingy m;
    m = *thingy_set.find(m2); // OK.
    m = *thingy_set.find(static_cast<void *>(&m2)); // Nope. Can't use a pointer.

}

Since each MetadataThingy can be uniquely identified by the pointer value it stores and is ordered by the pointer value, it would make sense to find/delete objects simply by using a void * as the key. As it currently stands, though, I would have to create a dummy MetadataThingy each time I search for an element, which feels really kludgy. I've already considered using just a map with pointers as key and MetadataThingy as value but since each MetadataThingy must also contain the pointer anyway, this feels a bit redundant. So, is there a way to use an element of a type other than that stored in a set to find or delete values in the set, given that elements of the two types are mutually comparable and that elements of one type can be uniquely mapped into the other ( void * and MetadataThingy are isomorphic)? (I didn't include any in the above code, but suppose there are operator overloads for comparing void * and MetadataThingy in any order.)

A little background on the problem I'm trying to solve, just in case anyone can recommend a better approach: I need to order a collection by multiple criteria, so I have several MetadataThingy containers, all sorted by different criteria. "Metadata" in this case would be stuff I need to track the positions of the elements in all containers so that I can do fast removal. This would sound like a perfect job for boost multi-index containers, but the ordering of these elements is constantly changing, which AFAIK would mean it won't work.

Answer 1

As of C++14, std::set has templated versions of its lookup functions find, lower_bound, etc. They allow you to pass any object for comparison, as long as the comparer supports it.

This means you can directly pass your void* to find, as long as the comparer supports comparing MetadataThingy and void*.

For more information, see http://en.cppreference.com/w/cpp/container/set/find.

To understand the limitation regarding Compare::is_transparent, I found this StackOverflow question very helpful.

Answer 2

You can do this by using std::find_if and providing a predicate functor.

#include <algorithm>

struct Predicate
{
    void const * const ptr_;
    explicit Predicate(const void* ptr) : ptr_(ptr) {}
    bool operator()(const MetadataThingy& other)
    {
        return ptr_ == other.actual_thingy;
    }
};

m = *std::find_if(thingy_set.begin(), thingy_set.end(), Predicate(&m2));

You can use the iterator returned by std::find_if to remove the element from the set by passing it to set::erase.

Answer 3

No, the signature of map<>::find requires you pass in the key type.

There is, however, a relatively simple workaround. Use boost::optional or std::tr2::optional (from C++1y) to store your non-key data.

struct MetadataThingy {
  void* pBlah;
  optional<rest_of_stuff> rest;
  static MetadataThingy searcher( void* );
  MetadataThingy(...);
};

then call MeatadataThingy::searcher to generate your key value.

Another approach would be to store smart (unique probably) pointers to sub-interfaces, each of which has a "get full data" method. Then, when you want to do a search, create a stub sub-interface that returns nullptr on "get full data".

struct MetadataFull;
struct MetadataRoot {
  virtual MetadataFull* get() = 0;
  virtual MetadataFull const* get() const = 0;
  virtual ~MetadataRoot() {}
};
template<typename T>
struct MetadataFinal: virtual MetadataRoot {
  static_assert( std::is_base_of< T, MetadataFinal<T> >::value, "CRTP failure" );
  virtual MetadataFull* get() { return static_cast<T*>(this); }
  virtual MetadataFull const* get() const { return static_cast<T const*>(this); }
};
struct MetadataStub: virtual MetadataRoot {
  virtual MetadataFull* get() { return nullptr; }
  virtual MetadataFull const* get() const { return nullptr; }
};
struct MetaDataA: virtual MetaDataRoot {
  void* pBlah;
};

struct MetaDataFull: MetaDataA, MetadataFinal<MetaDataFull> {
  // unsorted data
};
struct MetaDataAStub: MetaDataA, MetaDataStub {};

now, this can be done with virtual functions but not virtual inheritance with a bit of finagling if you really need it.

Answer 4

The library does not support the behavior that you ask for, although I have seen other people request the same thing (i.e. providing a templated member function find in ordered associative containers that would use a cross comparator), although this is infrequent.

Your type is unusual in that only one of the member attributes takes part on the value of the object (i.e. is used in the comparison). The compiler cannot know that only some of the members (or which of the members) are part of the value and which are not. although it might be that the objects are not really comparable and you just hammered operator< as a simple way of enabling the use in associative containers.

If that is the case, consider dropping the operator< that does not really compare the MetaThingy objects and also change the data structure to be a std::map<void*,MetaThingy>, which would make the design cleaner at the cost of an extra void* per stored object --it might also be the case that the void* is inside the MetaThingy for the lookup in the set... in which case it might even make more sense and you could provide std::map<void*,MetaInfo>.