5
\$\begingroup\$

This ObjectSet container adds new Objects with lowest possible unique ID. My implementation uses std::set for its sorting, but this convenience may not be required.

My two main questions are:

  1. Is std::set generally a good and preferred solution for this problem?

  2. In case of using std::set, can ObjectSet::minId be implemented with use of standard algorithms?

Code:

#include <iostream>
#include <set>
#include <string>

class Object
{
    std::uint32_t id_;

public:
    explicit Object(std::uint32_t id) : id_(id) {}

    std::uint32_t const& id() const
    {
        return id_;
    }

    std::string name() const
    {
        return "Object" + std::to_string(id_);
    }

    bool operator<(Object const& other) const
    {
        return id_ < other.id_;
    }
};

class ObjectSet : std::set<Object>
{
public:
    void addObject()
    {
        insert(Object(minId()));
    }

    void removeObject(std::uint32_t id)
    {
        erase(Object(id));
    }

    std::uint32_t minId() const
    {
        if(empty())
            return 1;

        for(auto it1 = begin(), it2 = it1++; it1 != end(); ++it1, ++it2)
            if(it1->id() != it2->id() + 1)
                return it2->id() + 1;

        return rbegin()->id() + 1;
    }

    using Base = std::set<Object>;

    using Base::begin;
    using Base::cbegin;
    using Base::rbegin;
    using Base::crbegin;

    using Base::end;
    using Base::cend;
    using Base::rend;
    using Base::crend;
};

int main()
{
    ObjectSet objects;
    objects.addObject();
    objects.addObject();
    objects.addObject();
    objects.removeObject(2);
    objects.addObject();

    for(auto const& object : objects)
        std::cout << object.name() << std::endl;
}
\$\endgroup\$
5
\$\begingroup\$

Looks pretty good to me. The only glaring stylistic issue I see is that you inherit from std::set instead of having a member of that type. Inheriting from classes whose innards you don't personally control usually leads to issues with slicing and/or expecting-polymorphism-and-not-getting-it. However, since you're doing private inheritance, this is probably okay.

There are a couple of functional improvements you might want to make (but then again might not, because they're subtle).

(1) Your Object type has an operator< that does nothing but compare ids. That's unlikely to be useful in practice. But you need to have that "compare ids" operation so that you can make your sorted set. The solution is to pass a comparator to your set, like so:

class ObjectSet {
    static bool id_less(const Object& a, const Object& b) {
        return a.id() < b.id();
    }
    std::set<Object, decltype(&id_less)> items_;

  public:
    ObjectSet() : items_(id_less) {}

    // ...
};

This allows you to reclaim Object::operator< for some more appropriate semantics.

(2) Continuing with comparators... Every time I call removeObject, you construct a whole Object to pass to erase. This seems wasteful (assuming Object is a heavyweight type), and also counter-intuitive: what do you mean, removeObject calls the constructor of Object?! :)

The solution requires C++14 or better, because it depends on a particular overload of std::set<T>::find() that first showed up in C++14.

class ObjectSet
{
    static bool id_less(const Object& a, const Object& b) { return a.id() < b.id(); }
    static bool id_less(const Object& a, std::uint32_t b) { return a.id() < b; }
    static bool id_less(std::uint32_t a, const Object& b) { return a < b.id(); }

    struct Comparator {
        template<class T, class U>
        bool operator()(const T& a, const U& b) { return id_less(a, b); }
        using is_transparent = void;
    };

    std::set<Object, Comparator> items_;

    // ...

    void removeObject(std::uint32_t id)
    {
        items_.erase(items_.find(id));
    }
};

(Wandbox link.)

\$\endgroup\$
  • 1
    \$\begingroup\$ One SO question interested me and I coded it kind of in haste. I'm not going to be using it anytime soon, but you gave me a few valuable advices. Thanks. I guess that that private inheritance is OK too - I don't want any polymorphism and sliscing is forbidden by that. If std::set was a member, I certainly wouldn't like the process of defining all the member functions and overloads. \$\endgroup\$ – LogicStuff Oct 24 '15 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.