CODEWITHSUNDEEP
c++
Sergey Barannikov
Sergey Barannikov

Reputation: 328

Create an object if it is not already in the set

Having a set of pointers to unique objects of type A, I want to create and insert a new element in the set, but only if there is no such element already. The problem is, the standard comparators operate existing objects, and one is not yet exist. That means that I can not determine if an object is in the set without creating the object (or without iterating the whole set manually).

One obvious solution would be to replace the set by a map with keys containing a part of A that makes objects of type A unique, but it almost doubles memory usage. It is unacceptable to me.

Any ideas?

UPDATE To be more concrete, here is a simplified example:

class Base { /* members */ };

class Derived : public Base {
  static std::set<Derived *> cache;
  std::vector<Object *> v;
 public:
  static Derived *Create(const std::vector<Object *> &v);
  /* other members */
};

Derived *Derived::Create(const std::vector<Object *> &v) {
  /* Here I need to create and insert a new object of type Derived
     into the `Derived::cache`, but only if there is no such object
     in the set yet. Objects are uniqued by contents of `v`. */
}

Upvotes: 0

Views: 144

Answers (2)

Malcolm McLean
Malcolm McLean

Reputation: 6404

You need to call set::count.

count will then call the '<' operator on the object you pass it, plus the objects in the set. So you must construct an object.

But the '<' operator does not need to access every field. Probably. If you absolutely must compare on every field then there is no solution other than to create the query object. But most likely the object has an Id or similar field you use for fast comparison. So you need a special constructor.

class MyClass
{
  int id;
  std::vector<int> expensive_member;
  friend bool operator < (MyClass const &, MyClass const &);

  public:
  MyClass(std::vector<int> const &expensivetosetup, int id);
  MyClass(int id);
  void member() { assert(expensive_member.empty() == false);} 
}

bool operator < (MyClass const &a, MyClass const &b)
{
   return a.id < b.id;
}

Set it up like that. Then the special constructor is only used to create a cheap query object. For a bit of extra safety, we wrap assert fails round the other members so the partially constructed objects can't be used for anything else.

It should be stressed that this is poor design. The real answer is to use a key / value pair and take the key out of the object if memory requires that. But sometimes other pressures create bad designs, and this is your answer.

Upvotes: 0

Richard Hodges
Richard Hodges

Reputation: 69864

std::find_if taking an arbitrary type is supported in c++14:

#include <set>
#include <tuple>
#include <memory>

//
// the concept of an Identity - some signature that identifies an object
// uniquely
struct Identity
{
  Identity(int v) : v_(v) {}

  auto as_tuple() const { return std::tie(v_); }

  private:
  int v_;
};
bool operator<(Identity const& l, Identity const& r)
{
  return l.as_tuple() < r.as_tuple();
}

//
// some object that has an identity
//
struct Thing
{
  Thing(Identity i) : ident_(std::move(i)) {}

  const Identity& identity() const { return ident_; }

private:
  Identity ident_;
};

struct LessThing
{
  struct is_transparent {};

  bool operator()(const std::unique_ptr<const Thing>& l, const Identity& r) const
  {
    return l->identity() < r;
  }

  bool operator()(const Identity& l, const std::unique_ptr<const Thing>& r) const
  {
    return l < r->identity();
  }

  bool operator()(const std::unique_ptr<const Thing>& l, const std::unique_ptr<const Thing>& r) const
  {
    return l->identity() < r->identity();
  }

};


int main()
{
  std::set<std::unique_ptr<const Thing>, LessThing> myset;
  myset.insert(std::make_unique<Thing>(Identity(5)));
  myset.insert(std::make_unique<Thing>(Identity(6)));

  if (myset.find(Identity(7)) == myset.end())
  {
      myset.emplace(std::make_unique<Thing>(Identity(7)));
  }  
}

Note1: the definition of the type is_transparent in the comparison functor to enable this behaviour.

Note2: Remember that the elements of a set are constants. If the key comparison depends on an object that is being pointed to by the pointer in the set, that data (or at least the identifying part of it) must be immutable.

Upvotes: 1

Related Questions