10
\$\begingroup\$

After refactors and refactors and the discovery of very common patterns on many of the classes of the software I wrote, I decided that it would be fine to have something like an arbitrary-keyed map, that would require the key to be stored in the object (which allows to use the object's name as a key for instance).

I would like to know if it is a good design, and what are possible pitfalls I didn't encounter and might in the future (and how to prevent them).

It is far from perfect (no optimisations, not /that/ generic...) but allowed me to have cleaner code.

The container code:

#pragma once
#include <string>
#include <algorithm>
#include <vector>
#include <set>

template<typename T>
using SimpleVec = std::vector<T, std::allocator<T>>;

template <typename T,
          template <typename> class Container = SimpleVec,
          class String = std::string>
class Iterable
{
        template <typename friendT,
                  template <typename> class friendContainer,
                  class friendString>
        friend typename friendContainer<friendT>::iterator
            begin(Iterable<friendT, friendContainer, friendString>& i);

        template <typename friendT,
                  template <typename> class friendContainer,
                  class friendString>
        friend typename friendContainer<friendT>::iterator
            end(Iterable<friendT, friendContainer, friendString>& i);

        template <typename friendT,
                  template <typename> class friendContainer,
                  class friendString>
        friend typename friendContainer<friendT>::iterator
            cbegin(const Iterable<friendT, friendContainer, friendString>& i);

        template <typename friendT,
                  template <typename> class friendContainer,
                  class friendString>
        friend typename friendContainer<friendT>::iterator
            cend(const Iterable<friendT, friendContainer, friendString>& i);


    public:
        Iterable() = default;
        Iterable(const Iterable<T, Container, String>& c) = delete;
        Iterable& operator=(const Iterable<T, Container, String>& c) = delete;
        virtual ~Iterable() = default;

        template<typename... K>
        void performUniquenessCheck(const K&... args)
        {
            if(std::any_of(begin(*this),
                           end(*this),
                           T::hasSame(args...)))
            {
                throw "Element already exists";
            }
        }

        template<typename... K>
        T& create(K&&... args)
        {
            elements().emplace_back(args...);
            return elements().back();
        }

        virtual void remove(T& toRemove)
        {
            _c.erase(std::remove(begin(_c), end(_c), toRemove), end(_c));
        }

        template<typename... K>
        T& operator()(const K&... args)
        {
            auto it = std::find_if(begin(_c),
                                   end(_c),
                                   T::hasSame(args...));

            if(it == _c.end()) throw "Name not found. Did you call has() ?";

            return *it;
        }

        template<typename... K>
        std::vector<std::reference_wrapper<T> > getFamily(const K&... args)
        {
            std::vector<std::reference_wrapper<T> > vect;
            auto cond = T::hasSame(args...);

            for(auto& elt : _c)
            {
                if(cond(elt))
                {
                    vect.emplace_back(elt);
                }
            }

            return vect;
        }

        template<typename... K>
        bool has(K&&... args) const
        {
            return std::any_of(cbegin(_c),
                               cend(_c),
                               T::hasSame(args...));
        }

        Container<T>& elements() { return _c; }

    private:
        Container<T> _c; // Container ex. : std::vector<T>
};

template <typename T,
          template <typename> class Container = SimpleVec,
          class String = std::string>
typename Container<T>::iterator
    begin(Iterable<T, Container, String>& i)
{
    return begin(i._c);
}

template <typename T,
          template <typename> class Container = SimpleVec,
          class String = std::string>
typename Container<T>::iterator
    end(Iterable<T, Container, String>& i)
{
    return end(i._c);
}

template <typename T,
          template <typename> class Container = SimpleVec,
          class String = std::string>
typename Container<T>::iterator
    cbegin(const Iterable<T, Container, String>& i)
{
    return cbegin(i._c);
}

template <typename T,
          template <typename> class Container = SimpleVec,
          class String = std::string>
typename Container<T>::iterator
    cend(const Iterable<T, Container, String>& i)
{
    return cend(i._c);
}

It requires, as you can see in performUniquenessCheck, a hasSame method. What I did is a little macro trick to add properties to my classes, for simple properties, but I can also add it by hand if for instance I want a test using two elements.

For instance, if you have

class A1 {  }; class A2 { };
class B { private: A1& a1; A2& a2; }

And there is a collection of B's which share common A1 & A2 you can ask for all the B with a particular A1 or a particular A2.

Here is the property macro:

#pragma once
#include <functional>

#define GenerateUniqueProperty(Property, Type) \
    class has ## Property \
    { \
        public: \
            has ## Property(Type val): \
                _val(val) \
            { } \
            \
            virtual ~has ## Property() = default;\
            \
            Type get ## Property() const \
            { \
                return _val; \
            } \
            \
            void set ## Property(const Type& val) \
            { \
                _val = val; \
            } \
            \
            static std::function<bool(const has ## Property&)> hasSame(const Type& val) \
            { \
                return [&val] (const has ## Property& p) \
                { \
                    return p._val == val; \
                }; \
            } \
            \
        private: \
            Type _val; \
    };


GenerateUniqueProperty(Name, std::string)
GenerateUniqueProperty(Id, int)

So we can have our class which is to be contained :

#pragma once
#include"../properties/hasId.h"
#include"../properties/hasName.h"

class SomeObject: public hasName, public hasId
{
    public:
        using hasName::hasSame;
        using hasId::hasSame;

        SomeObject(std::string name, int id):
            hasName(name),
            hasId(id)
        {
        }

        ~SomeObject() = default;
        SomeObject(SomeObject&&) = default;
        SomeObject(const SomeObject&) = default;
        SomeObject& operator=(SomeObject&& g) = default;
        SomeObject& operator=(const SomeObject&) = default;

        bool operator==(const SomeObject& g) const
        {
            return g.getId() == getId();
        }

        bool operator!=(const SomeObject& g) const
        {
            return g.getId() != getId();
        }

};

And its custom container:

#pragma once
#include "SomeObject.h"
#include "../Iterable.h"

class SomeObjectManager : public Iterable<SomeObject>
{
    private:
        unsigned int _lastId = 0;

    public:
        SomeObject& createSomeObject(std::string&& name)
        {
            performUniquenessCheck(std::forward<std::string>(name));
            return create(name, _lastId++, SomeObjectChanged);
        }
};

So new we can do nice stuff like:

SomeObjectManager manager;
manager.createSomeObject("Cool object");
manager.createSomeObject("Cooler object");

std::cerr << manager("Cool object") == manager(1) << std::endl;
manager.remove(manager(1)); // Maybe here also it should do it by properties ?

for(auto& elt : manager) std::cerr << elt.getName() << std::endl;
\$\endgroup\$
  • 1
    \$\begingroup\$ arbitrary-keyed map, that would require the key to be stored in the object You mean like std::set<T> ? \$\endgroup\$ – Martin York Apr 17 '14 at 20:40
12
\$\begingroup\$

[...]I decided that it would be fine to have something like an arbitrary-keyed map, that would require the key to be stored in the object (which allows to use the object's name as a key for instance).

To restate your problem: you want the add behavior of a set (i.e., you add the object to the collection without any other information), but you want the retrieve behavior of a map (i.e., you retrieve the object by a key, not by a reference to that object). Additionally, from the code, it seems that you want to be able to retrieve an object by multiple keys (e.g., by both ID # and name), all of which then need to be unique.

First, it's probably a bad idea to have objects being keyed in more than one way in the same container. It effectively means you have aliases for the same object, and that can get quite confusing to manage. It also means your lookups are pretty much stuck at \$O(N)\$ (instead of \$O(log(N))\$ or \$O(1)\$). Why? Because faster than \$O(N)\$ lookups require that the data either be sorted (so an \$O(log(N))\$ search can be used), or hashed (so that an \$O(1)\$ probe can be performed). Using your example, "name" and "Id" fields won't both be such that sorting one will cause the other to be sorted, nor will their hash values come out identically. Thus, retrieving items from the container degenerates to \$O(N)\$ when doing lookups using anything other than the primary key.

This isn't entirely true -- with one map, you could jury-rig a string key with namespaces, and in that manner have multiple keys without a slowdown of the map (although the hash calculation time might increase as the strings get longer). More reasonably, you could have one map per key. I have an aggregate_automap proof-of concept that takes this approach. It's templated, and it allows an arbitrary number of maps (each based on an automap translator) to be added to, removed from, and (by selecting a specific map from the group) searched in. However, it's too big and too ugly for me to, in good conscience, put up onto CR at the moment. Know that it -is- possible, if you absolutely need to look up objects using multiple keys... but try to only use multiple keys as an absolute last resort. :)

What I would recommend is a wrapper around unordered_set, such that neither your class-to-be-contained nor your container have to be modified to deal with the special details of your auto-keying. I have an example of such a solution below, but due to the limitations of search speed (which I mentioned earlier), it does not implement multi-keying, nor does it implement your getFamily functionality. However, both of those pieces of functionality can be implemented in \$O(N)\$ time using iterator traversal logic similar to what you already have.

#include <cstdlib>
#include <iostream>
#include <string>
#include <unordered_map>

// A class that has data you want to construct automatic keys with.
// This class can be any existing class you like. It does not need to be
// modified to support auto-keying.
class MyClass
{
public:
    MyClass(const std::string& name, long long ssn) : m_name(name), m_ssn(ssn) {}
    const std::string& getName() const { return m_name; }
    long long getSsn() const { return m_ssn; }
private:
    std::string m_name;
    long long m_ssn;
};

// A general template that concrete AutomapTranslator classes can be based on.
template <typename Key, typename Value, typename Hash = std::hash<Key>, typename EqualTo = std::equal_to<Key>>
class AutomapTranslator
{
public:
    // The type of object the keys will map to.
    typedef Value mapped_type;

    // The type of the key
    typedef const Key key_type;

    // Custom hash and equal_to functions, if your Key does not have these
    // provided by default.
    typedef Hash hash;
    typedef EqualTo equal_to;
};

// A class that implements the logic for automatically generating keys from
// instances of a class.
// You will need to implement at least one of these for each class you want to
// auto-key. You might implement more than one of these for a single class, if
// you want to have different ways of auto-keying the class (e.g., if you want
// to be unique by SSN instead of name, or force both SSN and name into the
// key, or have a key based on a long long instead of a string...)
class MyClassAutomapTranslator : public AutomapTranslator<std::string, MyClass>
{
public:
    // For each constructor signature in mapped_type, you will need a
    // matching getKey function signature (for "emplace").
    static key_type getKey(const std::string& name, long long ssn) { return name; }

    // At minimum, you will also need a getKey that converts an
    // arbitrary mapped_type to key_type.
    static key_type getKey(const mapped_type& val) { return val.getName(); }

private:
};

// An extension of unordered_map, with functions that allow a translator object
// to auto-generate keys when inserting key-less values.
template <typename T>
class unordered_automap : 
    public std::unordered_map<
            typename T::key_type,
            typename T::mapped_type,
            typename T::hash,
            typename T::equal_to>
{
    // For convenience/brevity... :)
    typedef std::unordered_map<
            typename T::key_type,
            typename T::mapped_type,
            typename T::hash,
            typename T::equal_to> map_type;
public:
    template<typename... Args>
            std::pair<typename map_type::iterator, bool> autoemplace(Args&&... args)
            {
                    return this->emplace(T::getKey(args...), args...);
            }

    template<typename... Args>
            typename map_type::iterator autoemplace_hint(typename map_type::const_iterator position, Args&&... args)
            {
                    return this->emplace_hint(position, T::getKey(args...), args...);
            }

    std::pair<typename map_type::iterator, bool> autoinsert(const typename T::mapped_type& val)
    {
            return this->insert(typename map_type::value_type (T::getKey(val), val));
    }

    typename map_type::iterator autoinsert(typename map_type::const_iterator hint, const typename T::mapped_type& val)
    {
            return this->insert(hint, typename map_type::value_type(T::getKey(val), val));
    }

    // ... along with "auto" implementations for the rest of the insert operations ...
};

int main(int argc, char** argv)
{
    unordered_automap<MyClassAutomapTranslator> demo;

    // Insertion is done by value only. The key is auto-generated, based on MyClassAutomapTranslator.
    demo.autoinsert(MyClass("Bob", 123456789));
    demo.autoinsert(MyClass("Phil", 987654321));
    demo.autoinsert(MyClass("Sue", 121212120));
    demo.autoinsert(MyClass("Clara", 212121210));

    // Find is done by key.
    std::cout << "Phil's SSN is: " << demo.find("Phil")->second.getSsn() << std::endl;

    // Remove is done by key.
    demo.erase("Phil");

    // Iteration is as normal.
    for(auto& elt : demo) std::cout << elt.second.getName() << ": " << elt.second.getSsn() << std::endl;

    return EXIT_SUCCESS;
}

The above code compiles with g++ -Wall -pedantic -std=c++11 and generates no warnings. IMO, it's a lot easier to read and re-use, especially because there is no macro-magic involved, and because the per-class automapping logic is locked away in a single place.

If you insist on/must continue to use the solution you have outlined in your original question...

  • In the case where an exception occurs because of a (duplicate, not found, etc.) key/item, you should convert the conflicting item(s) into string representations, and include them at the end of the message string. It tends to be very helpful, when debugging a crash, to be able to see which dynamic values caused the fault. In your case, it would also be helpful to know which specific -mapping- the fault was in (e.g., was it Id or Name that collided?), so consider including that in your error message as well.
  • Don't allow Iterable<T>::create(K&&...) to bypass the uniqueness check, or you could wind up with two items in the collection with the same key. If items need to be unique, then Iterable<T> should ensure that constraint, not an external wrapper.
  • Comment the functions, especially with regard to the template parameter packs. It's unclear, e.g., how manager("Cool Object", "Cooler Object") is supposed to behave, vs. manager.getFamily("Cool Object", "Cooler Object"), without a very detailed reading of the code. Even then, that just tells the reader the as-implemented behavior, not the actual intended behavior.
  • At the very least, put the macro-generated classes in their own namespace. The "is-a" inheritance relationship you're currently using runs contrary to the "has-a" naming convention you're using, and the multiple-inheritance conflicts will likely make for misery and mistakes down the line. As such, I personally would consider removing these little "classlets" completely, and instead have the macros directly inject the required code into the consuming classes.
\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to Code Review. This is a really, really comprehensive first answer ... you passed the 'first post' review with flying colours. Thanks. \$\endgroup\$ – rolfl Apr 18 '14 at 0:55
  • \$\begingroup\$ Thanks for the thorought answer ! I will try to see how I can make good use for it. However in my case (explicitely, I understand this does not apply to everyone), I only work with < 100 elements, hence lookup speed is of no concern with regard to ease of use. \$\endgroup\$ – Jean-Michaël Celerier Apr 18 '14 at 9:09
  • \$\begingroup\$ Travis: when you say : "Throw the (duplicate, not found, etc.) key/item in your exceptions. It will make everyone's life a bit easier." How can I throw at the same time an error message and an item ? Should I make an exception object which bundles both ? (or the message can be the type of the exception). thanks. \$\endgroup\$ – Jean-Michaël Celerier Apr 18 '14 at 10:14
  • 1
    \$\begingroup\$ @Jean-MichaëlCelerier - short answer: any diagnostic information needs to be encoded in the exception's "what" string. I'm not up-to-date on the best practices there, but I presume throwing a real exception (e.g., "throw new std::range_exception(msg);") is preferred to throwing a bare string, and you can use an sstream to write important info (like the colliding key and attendant values of the existing/colliding objects) to a dynamic message string. \$\endgroup\$ – Travis Snoozy Apr 18 '14 at 17:27

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.