2
\$\begingroup\$

I was trying to find any way of developing a "string_id", a non-modifiable string holder that is O(1)-copyable and O(1)-comparable to be used as an id. The "creator" of the string_id is who knows the meaning of each "string_id". So, if two different entites creates two ids, that string_id identifiers represent different ids even if they strings representations are equal. Each newly and non-copied object creates a different id.

So, two string_ids refers to the same string iif they are in the same copy-hierarchy (a tree of copied objects), and not because their values compares equal.

An obvious way of implementing the string_id class could be holding a shared_ptr and comparing the saved address instead of the string contents, but, since the shared_ptr is thread-safe, it adds an extra overhead not needed in certain situations (for example, in my case, all of string_id instances are going to be used in the gui/main-thread).

So, I have implemented a light shared pointer as auxiliary class for implementing the string_id class. It has the following characteristic:

  • It has no default constructor. You need always to pass a unique_ptr holding the wanted object, to explicitly state the wanted value and that the instance is going to be non-shared (externally).

  • It's not thread-safe, but it is exception-safe and copying and comparision is O(1), as said before (all methods are).

  • It doesn't use a reference counter to don't manage two dynamic objects. Instead, it use a doubled-linked circular list of "family members". When the first object is created, the "next" and "previous" pointers point to this (a => a).

  • When an object b is created as a copy of a, b follows a (a => b => a). When an object is deleted, it is removed from the list. If I'm the last one of my hierarchy (if I point to myself), I remove the shared pointer.

  • It can be further improved with a deleter, or implementing the move constructor/assignment to make it a bit faster (I trust the compiler though).

The class:

template<class resource_t>
class family_member
{
    resource_t* p_raw_resource;

    mutable family_member const* p_previous;
    mutable family_member const* p_next;

public:
    explicit family_member(std::unique_ptr<resource_t>&& resource) 
      noexcept
        : p_raw_resource(resource.release()),
          p_previous(this), p_next(this)
    {}

    family_member(family_member const& sibling) noexcept
        : p_raw_resource(sibling.p_raw_resource),
          p_previous(std::addressof(sibling)), p_next(sibling.p_next)
    { p_next->p_previous = sibling.p_next = this; }

    family_member& operator=(family_member const& sibling) noexcept
    {
        p_raw_resource = sibling.p_raw_resource;
        p_previous = std::addressof(sibling);
        p_next = sibling.p_next;
        p_next->p_previous = sibling.p_next = this;

        return *this;
    }

    ~family_member()
    {   
        if (p_next == this) // I'm the last one
            delete p_raw_resource;
        else {
            p_next->p_previous = p_previous;
            p_before->p_next = p_next;
        }
    }

    resource_t& get() noexcept { return *p_raw_resource; }
    resource_t const& get() const noexcept { return *p_raw_resource; }

    bool same_family(family_member const& stranger) const
    { return p_raw_resource == stranger.p_raw_resource; }
};

To add support for non C++-14 users (no std::make_unique support), the following free function is provided:

template<class resource_t, class... args_t>
family_member<resource_t> make_family_member(args_t&& ...args)
{
    return family_member<resource_t>(std::unique_ptr<resource_t>
        (new resource_t(std::forward<args_t>(args)...))
    );
}

And the string_id class:

class string_id
{
    family_member<std::string> str_id;

public:
    explicit string_id(std::string const& id) : str_id(make_family_member<std::string>(id))
    {}

    operator std::string const&() const
    { return str_id.get(); }

    operator char const*() const
    { return str_id.get().c_str(); }

    friend bool operator==(string_id const& a, string_id const& b)
    {
        return a.str_id.same_family(b.str_id);
    }
};

The question is, is that implementation "memory"-safe? Can it be seen as an anti-pattern? Should I go for other solutions two carry-on, at the same time, the id and the string nature of the same object?

And the most important question of alls, is it worthy?

\$\endgroup\$
  • 2
    \$\begingroup\$ I get a sense of an XY problem thing going on here. How and where are you using this? I would do using string_id = std::shared_ptr<std::string>; and only replace it if it proves too slow. Which I doubt it will. The overhead of shared pointer is small compared to what ever else you are doing. If copying is taking too long, then you might want to just make less copies, change your user code. \$\endgroup\$ – Emily L. Apr 1 '17 at 7:08
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Apr 1 '17 at 8:51
  • \$\begingroup\$ @EmilyL. And I'm right now in the point of "If you are not sure, don't use it and use the std instead", which is precisely what you are recommending me. But the thing is, a string_id, is a string, not a pointer!! I don't want user code use the string_id as if it were a pointer. But maybe I can replace the family_member class by a shared_ptr as you suggested. \$\endgroup\$ – Peregring-lk Apr 1 '17 at 13:51
2
\$\begingroup\$

The copy constructor looks correct.

family_member(family_member const& sibling) noexcept
    : p_raw_resource(sibling.p_raw_resource),
      p_previous(std::addressof(sibling)), p_next(sibling.p_next)
{ p_next->p_previous = sibling.p_next = this; }

But the point of writing code in a high level language is to try and make it readable. Please don't chain assignments like that. It does not cost you anything to put each on its own line.

{
    p_next->p_previous = this;
    sibling.p_next     = this;
}

The assignment operator has a bug.

family_member& operator=(family_member const& sibling) noexcept
{
    p_raw_resource = sibling.p_raw_resource;
    p_previous = std::addressof(sibling);
    p_next = sibling.p_next;
    p_next->p_previous = sibling.p_next = this;

    return *this;
}

You correctly add it to the new chain. But you did not remove it from the old chain. So the previous chain that it was in now is broken as it links into the new chain via this.

You have an issue with your get(). You have no way to tell if the class actually contains a valid pointer. It is perfectly legal to initialize this object with a nullptr (via an empty std::unique_ptr). Since you can't tell if the object contains a nullptr every call to get() is a game of russian roulette at some point you are going to invoke undefined behavior.

\$\endgroup\$
  • \$\begingroup\$ Yes, I forgot to call the destructor inside the assignment operator. Fixed it now. Thanks. About the get() method, the class never holds a uninitialized object. It has no default constructor, and the only constructor is the one receiving a unique_ptr; ok, I didn't check if it contains a valid object, so, I have to ensure it somehow, but the id must hold always an object by design, although I would like to know if don't allowing null ids is a bad idea. \$\endgroup\$ – Peregring-lk Apr 1 '17 at 2:16
  • 1
    \$\begingroup\$ Yeah. I would not call the destructor. After that is called the object is considered dead (technically the lifespan of the object has finished). You would need to call the constructor (using placement new) after the destructor to bring it back to life (otherwise undefined behavior). An easier technique though is to put that functionality into a function called unlink() that both the destructor and assignment operator call. \$\endgroup\$ – Martin York Apr 1 '17 at 2:44
  • 2
    \$\begingroup\$ PS. You should not change your code after it has been reviewed. \$\endgroup\$ – Martin York Apr 1 '17 at 2:45

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.