11
\$\begingroup\$

I am trying to build a class similar to std::shared_ptr just to learn and improve my way of thinking. I am hoping that you can tell me if this implementation is correct? If so, how can I improve it?

Here is the code:

#include <iostream>
#include <map>

template<typename dataType>
class shared_ptr
{
public:
    shared_ptr()
    {
        id++;
        internalId = id;
        countMap[id] = 1;
        ptr = new dataType();
    }
    shared_ptr(shared_ptr& a)
    {
        this->ptr = a.ptr;
        this->internalId = a.internalId;
        countMap[internalId]++;
    }

    void operator=(shared_ptr& a)
    {
        this->ptr = a.ptr;
        this->internalId = a.internalId;
        countMap[internalId]++;
    }

    ~shared_ptr()
    {
        countMap[internalId]--;
        if(countMap[internalId]==0)
        {
            delete ptr;
            countMap.erase(internalId);
        }
    }

private:
    static int id;
    int internalId = 0;
    static std::map<int,int> countMap;
    dataType* ptr;
};
template<typename  dataType>
 int shared_ptr<dataType>::id = 1;
 template<typename  dataType>
 std::map<int,int> shared_ptr<dataType>::countMap;

int main()
{
    {
    shared_ptr<int> sp1;
    {
        shared_ptr<int> sp3;
        shared_ptr<int> sp4(sp3);
        shared_ptr<int> sp5;
        sp5 = sp4;
    }
    shared_ptr<int> sp2(sp1);
    }
    return 0;
}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You know std::map isn't thread-safe, right? So you're intentionally only making a single-threaded version of shared_ptr, not trying to get all the lock-free atomics right? That's fine, but you'd normally want to say so. \$\endgroup\$ Apr 30, 2021 at 3:11
  • \$\begingroup\$ Yeah you are right \$\endgroup\$ May 1, 2021 at 13:38

3 Answers 3

12
\$\begingroup\$

Design review

Trying to roll your own shared_ptr is actually a really good practice project. This is not true for many other standard library components, but it is true for shared_ptr. You could try to duplicate the behaviour of std::shared_ptr exactly… but you don’t need to, because there are actually many, many different smart pointer designs. The ones in the standard library are just nice general-purpose smart pointers, but it’s very common to see custom smart pointers in libraries built for specific purposes.

Your shared_ptr actually has one important benefit over std::shared_ptr: it’s usually going to be half the size. The reason for that is std::shared_ptr uses a control block to keep track of how many shared pointers share the same pointer (among other things), so in a std::shared_ptr, there’s usually the actual pointer, and then the pointer to the control block… that’s two pointers, so double the size of a single pointer. You use a static map instead, so each of your shared pointers only holds the actual pointer. That could be an important benefit.

However, you also truck around an int as an ID. Is that necessary? Why not just use the pointer value itself as the key?

Something like so:

std::unordered_map<std::uintptr_t, std::size_t> count_map;

template <typename T>
class shared_ptr
{
public:
    constexpr shared_ptr() noexcept = default;

    explicit shared_ptr(T* p) : _ptr{p}
    {
        _increment_count();
    }

    shared_ptr(shared_ptr const& other) : _ptr{other._ptr}
    {
        _increment_count();
    }

    ~shared_ptr()
    {
        if (_ptr)
        {
            // find the iterator to the count
            //
            // this is better than `count_map[n]` because we might need to use
            // the iterator more than once: once to decrement and check the
            // count, and possibly once more to erase
            auto const n = static_cast<std::uintptr_t>(_ptr);
            if (auto const p = count_map.find(n); p != count_map.end())
            {
                // decrease the count, and see if it's zero
                if (--(p->second) == 0)
                {
                    delete _ptr;

                    // remove the map entry tracking the pointer
                    count_map.erase(p);
                }
            }
            else
            {
                // something went really wrong!
                //
                // you should never get here unless there's a bug somewhere
            }
        }
    }

    auto operator=(shared_ptr const& other) -> shared_ptr&
    {
        auto temp = other;

        std::ranges::swap(_ptr, temp->_ptr);

        return *this;
    }

    // other stuff...

private:
    auto _increment_count() -> void
    {
        if (_ptr)
        {
            // convert the pointer to a number
            auto const n = static_cast<std::uintptr_t>(_ptr);

            // add the number as a new key in the count map
            //
            // note that if the key already exists, this will just increment the
            // count, so your shared_ptr will safely work with duplicates...
            // something std::shared_ptr won't do!
            ++(count_map[n]);
        }
    }

    T* _ptr = nullptr;
};

By using the pointer value itself as the key, rather than an int ID, your shared_ptr can now be the size of a single raw pointer.

So your design—using an external map to keep track of the count—has some benefits: notably it is now possible to make your smart pointer the same size as a raw pointer. But, of course, it has some drawbacks:

  1. If you have a lot of shared_ptrs, that map can get huge.
  2. Copying and destroying your shared_ptrs will be slow. std::shared_ptr has the pointer to the control block right on hand, so it just needs to do a single pointer indirection. Especially for making copies (and increasing the count), that’s fast (relatively speaking). Your shared_ptr has to search through a map (which is probably not going to be hot in cache) for each operation. That means that while auto sp1 = sp2; is really fast for std::shared_ptr it will be slow for your shared_ptr (and will get slower the more pointers you have). But that’s a pretty standard engineering size-versus-speed trade-off; your shared_ptr takes up less space, at the cost of speed.

Testing

Rather than simply wondering whether your code works or not, you should test it.

Now, something like shared_ptr is not easy to test… but not impossible. As a start, you could run your shared_ptr through all of its operations, and use a tool like Valgrind to check for bad memory access or leaks. Actually properly unit-testing something like shared_ptr is complex, and way beyond the scope here.

But a really easy trick is to simply insert a bunch of std::cout statements in your class member functions to print all the data about what’s going on. Yes, this isn’t the “sexy” way to test your code, but you’re a beginner; focus more on your code actually being correct than on doing things the “sexy” way.

In your destructor, you should also print the contents of the count map. That will give you a way to spot leaks, or other problems with the counts.

As I said, this isn’t technically the “right” way to do testing, but screw it, it’s quick, it’s easy, and it works. Even I develop code this way sometimes, if I’m experimenting with something difficult or “clever”. It’s cheap and hacky, but in the early stages of figuring something out, it does the job.

Code review

For starters, you should really be putting your own classes and stuff into your own, personal namespace. For example, I always use indi:

namespace indi {

template <typename T>
class shared_ptr
{
    // ... [snip] ...
};

} // namespace indi

auto main() -> int
{
    indi::shared_ptr<int> sp1;
    // ...
}

Putting your stuff in your own namespace is a good habit to get into in any case.

template<typename dataType>

dataType is a bad name for a template parameter. By convention, template parameters are written in “UpperCamelCase”. Also by convention, T is most commonly used. And it’s a hell of a lot shorter than dataType.

    shared_ptr()
    {
        id++;
        internalId = id;
        countMap[id] = 1;
        ptr = new dataType();
    }

Your default constructor actually allocates a new object. That’s… not a great idea. Default construction should be simple, fast, and—ideally—no fail.

Not only that, this behaviour is pretty surprising for a pointer. Consider:

using pointer = int*;

auto p1 = pointer{};                // p1 == nullptr, no-fail and fast
auto p2 = std::unique_ptr<int>{};   // p2 == nullptr, no-fail and fast
auto p3 = std::shared_ptr<int>{};   // p3 == nullptr, no-fail and fast
auto p4 = shared_ptr<int>{};        // p4 != nullptr, very slow, and the allocation might throw

Default construction for every other smart pointer I’ve seen gives you a null pointer. That should be the case for your smart pointer, too.

If you want a constructor that actually allocates the object—which is a good idea—you can use a “tagged constructor”. A good tag is std::in_place:

    constexpr shared_ptr() noexcept = default;

    explicit shared_ptr(std::in_place_t)
    {
        id++;
        internalId = id;
        countMap[id] = 1;
        ptr = new dataType();
    }

And you’d use it like this:

auto sp1 = shared_ptr<int>{std::in_place};

You could get even more advanced with perfect forwarding:

    template <typename... Args>
    explicit shared_ptr(std::in_place_t, Args&&... args)
    {
        id++;
        internalId = id;
        countMap[id] = 1;
        ptr = new dataType{std::forward<Args>(args)...};
    }

So now you could do:

auto sp = shared_ptr<std::string>{std::in_place, '*', 8};
// sp points to a string containing 8 asterisks

But let’s dig into the meat of the constructor:

    shared_ptr()
    {
        id++;
        internalId = id;
        countMap[id] = 1;
        ptr = new dataType();
    }
  1. The first line can’t fail. So no problems yet (or so it seems!).
  2. The second line also can’t fail. This is the only safe line in this entire constructor. (And even then, it’s not perfectly safe; it would be dangerous in concurrent code. But concurrency is a whole other beast.)
  3. This line can fail. When you do countMap[id], the map will try to find a key matching id, and will (presumably) fail. So it will need to allocate a new node. That allocation might fail. This won’t be too serious a problem… all it means is that you’ll skip an ID.
  4. This line can also fail, either in the allocation phase, or the construction of the new object. Either way, this is bad, because now countMap holds a node with an ID and count of 1 that will never be freed. Since no other shared pointer will use the same ID, this is only a minor leak… but it’s still a leak.

If you don’t care about losing IDs, you could fix this constructor by doing something like so:

    shared_ptr()
    {
        id++;
        internalId = id;
        countMap[id] = 1;

        try
        {
            ptr = new dataType();
        }
        catch (...)
        {
            countMap.erase(id);
            throw;
        }
    }

But the moral here is to always consider which expressions can throw, and what that means for the function as a whole.

    shared_ptr(shared_ptr& a)
    {
        this->ptr = a.ptr;
        this->internalId = a.internalId;
        countMap[internalId]++;
    }

The correct form for a copy constructor is to take the argument by const reference.

Failure to do so means this code won’t work:

auto const sp1 = shared_ptr<int>{};
auto const sp2 = sp1; // won't compile

Other than that, this copy constructor is okay. Most C++ programmers would gripe about the this-> stuff, because it’s unnecessary and ugly, but it’s not actually wrong, or harmful. (You could also use a member initializer list, but meh. For these simple types it doesn’t really matter.)

    void operator=(shared_ptr& a)
    {
        this->ptr = a.ptr;
        this->internalId = a.internalId;
        countMap[internalId]++;
    }

@1201ProgramAlarm has already pointed out one of the bugs in this function, but the best way to fix it is to rethink the whole function entirely, and use the “copy-and-swap” technique.

You see, if you follow @1201ProgramAlarm’s advice directly… you’ll have another problem. Let me show you—suppose you did this:

auto operator=(shared_ptr const& a) -> shared_ptr&
{
    // first decrement the count of the current pointer, and delete if necessary
    --countMap[internalId];
    if (countMap[internalId] == 0)
        delete ptr;

    // now set the new data
    ptr = a.ptr;
    internalId = a.internalId;
    ++countMap[internalId];

    return *this;
}

This looks innocuous… but it’s a trap. It won’t explode easily, but it will explode if you do this:

auto sp = shared_ptr<int>{};
sp = sp; // self-assignment

Consider what happens during the self-assignment above. Before the self-assignment, the count for the pointer is 1 (because it’s the only smart pointer that owns it). So the first line of the assignment operator does the decrement… and now the count is zero. So, of course, the object gets freed.

Then the “new” data gets transferred over. But… the new data is the same as the old data. So ptr is set to… itself… the pointer which now points to the deleted object. internalId is also set to itself, but that’s harmless. Then the count gets re-incremented, so it goes from zero to one again.

The net result is that your shared pointer appears to still be working—still keeping the count to some pointer—but the pointer points to deleted memory. If you access it, boom. And of course, when the last shared pointer pointing to it is destroyed, it will try to free it again. Double delete. Boom.

So I recommend the “copy-and-swap” technique:

auto operator=(shared_ptr const& a) -> shared_ptr&
{
    // copy a into a temporary...
    auto temp = a;

    // ... then swap the contents of the temporary with this
    std::ranges::swap(ptr, temp->ptr);                  // cannot fail
    std::ranges::swap(internalId, temp->internalId);    // cannot fail

    return *this;

    // when temp goes out of scope, it will be destroyed
    //
    // since it now holds the *OLD* internalID that this had, it will
    // decrement *THAT* count, and if it's zero, free the *OLD* ptr this held
    //
    // in the case of self-assignment, all the copy will do is increase the
    // count (to 2), and then the destruction will decrease it (back to 1),
    // so no harm, no foul
}

“Copy-and-swap” is technically less efficient… but it avoids very subtle bugs, like the self-assignment bug I described. You should do “copy-and-swap” in copy assignment operators by default.

Also, your copy-assignment operator is malformed. It should take a const reference, and it should return a non-const reference to this… not void.

The destructor is fine, so I’ll skip it.

    static int id;
    int internalId = 0;
    static std::map<int,int> countMap;

Okay, there are a couple of issues here.

First, I don’t know if you realize it, but since shared_ptr is a template, that means that there will be multiple id and countMap objects… one for each template parameter set.

In other words:

auto sp1 = shared_ptr<int>{};
auto sp2 = shared_ptr<long>{};

You probably think that the internalId for sp1 will be 2, and for sp2 it will be 3. Nope. It will be 2 for both. Why? Because sp1 is using shared_ptr<int>::id, and sp2 is using shared_ptr<long>::id. Those are two different ints.

In fact:

auto sp01 = shared_ptr<char>{};
auto sp02 = shared_ptr<signed char>{};
auto sp03 = shared_ptr<unsigned char>{};
auto sp04 = shared_ptr<int>{};
auto sp05 = shared_ptr<unsigned int>{};
auto sp06 = shared_ptr<short>{};
auto sp07 = shared_ptr<unsigned short>{};
auto sp08 = shared_ptr<long>{};
auto sp09 = shared_ptr<unsigned long>{};
auto sp10 = shared_ptr<std::string>{};
auto sp11 = shared_ptr<std::u8string>{};
auto sp12 = shared_ptr<std::vector<int>>{};
auto sp13 = shared_ptr<std::vector<long>>{};

The above code will create thirteen different id ints, and thirteen different countMap std::map<int, int>s. Every unique type you instantiate a shared_ptr with will create a new id and countMap. If you make shared_ptrs using many different types, that will balloon your static memory usage. And the bad thing about static memory usage is that it exists for the whole program. It is created when the program starts even if you never actually use it, and it exists until the program ends, even if you’re long done with it. Indeed, if you only allocate a single shared_ptr<foo> one time in the middle of your program, you’re paying for it for the whole program. You’re even paying for it if you allocate zero shared_ptr<foo> objects… but only mention one as a conditional possibility!

So this is not good. You probably only want a single map and id counter for all types in your program. To do that, you need to pull those static objects out of the template. You have multiple options for how you can do that. You can simply use global objects (probably hidden in a detail namespace). Or you can use a non-template base class and put all the statics in there.

Another issue is the use of int for both the ID and the count. int is only guaranteed to hold 65,536 values, though in practice it will usually hold at least 4,294,967,296. Four billion sounds like a lot, and it probably is, but it is not inconceivable that if a program runs long enough, and does enough allocating and deallocating, it could run out. (Far more likely to have that happen if you only have 65,536 values, of course.)

Whenever you’re keeping a count of something, the standard type to use in C++ is std::size_t. On most 64-bit systems, this will give you at 18,446,744,073,709,551,616 different IDs. That should be enough. You should use this for both the ID and the count.

So, perhaps you might do this:

// these could be hidden in a detail namespace, or a base class
//
// watch out for the static initialization order fiasco!
static auto next_id = std::size_t{0}; // in C++23 "= 0uz;" would work
static auto count_map = std::map<std::size_t, std::size_t>{};

// since the static variables are not in the template, they won't be
// duplicated for every T
template <typename T>
class shared_ptr
{
    // ...
};

Finally, you should consider using std::unordered_map rather than std::map. You don’t need the ordering, and the unordered map may be faster.

All that’s left is main():

shared_ptr<int> sp1;

You should really avoid this kind of declaration. The gold standard in modern C++ is the “always auto” style:

auto sp1 = shared_ptr<int>{};

There are a number of reasons why this form is better, too many to get into here. But as a bonus, once you get in the habit of using auto, numerous other bugs and quirks go away, and many lines of code become simpler. For example, instead of:

shared_ptr<int> sp2(sp1);

You could just do:

auto sp2 = sp1;

Shorter, simpler, clearer, and it avoids all kinds of bugs.

\$\endgroup\$
18
  • 1
    \$\begingroup\$ Note that using the pointer value as the key prevents pointers from sharing ownership if they don't point to the same address, which has dire consequences for pointing to base/derived classes. It may not be relevant for this simple educational shared_ptr, but would be worth mentioning. \$\endgroup\$ Apr 29, 2021 at 9:14
  • 1
    \$\begingroup\$ Regarding the cost of maintaining a std::map, I found that it is both slow and has a lot of space overhead. The std::unordered_map is often better, though the default hash function for pointers is usually very bad. Last time I needed a "pointer to size_t" map, I rolled my own which let me avoid the usual standard library inefficiencies (still not thread-safe, though). A control block might need more space, but makes lock-free refcounting much easier. \$\endgroup\$
    – amon
    Apr 29, 2021 at 10:03
  • 1
    \$\begingroup\$ @AngewisnolongerproudofSO I mean, if you violate the interface contract of any type—even std::shared_ptr—you get “dire circumstances”. So, yanno, just don’t do that. It’s not like you trigger this problem accidentally; you have to be deliberately trying to undermine the interface by doing something obviously shady; this type doesn’t have std::shared_ptr’s converting constructors, so the only way to have two shared_ptrs, one a Base the other a Derived both pointing to the same object, would be explicitly make two shared_ptrs that way. So just don’t do that. \$\endgroup\$
    – indi
    Apr 29, 2021 at 20:16
  • 1
    \$\begingroup\$ @amon The pros: all the same costs of a raw pointer (size and access cost) except when copying/destroying. The cons: no conversions (like derived to base, which std::shared_ptr can do), no aliasing, and you can’t take ownership of a pointer—to have the count where it’s supposed to be, the allocation must be done by the smart pointer itself. Is this design worth it? 🤷🏼 I mean, not to me, because I avoid shared ownership like the plague, and when I must use it, the cost of the extra pointer in std::shared_ptr doesn’t matter. \$\endgroup\$
    – indi
    Apr 29, 2021 at 20:20
  • 1
    \$\begingroup\$ @JDługosz std::ranges::swap() has nothing to do with ranges. It just happens to be in that namespace because it was developed along with ranges (and concepts, etc.). It has all the benefits of being a neibloid, which are too many to list here, but for just one: there is no need for the two-step (using std::swap; swap(...);), so even if the types change, it will always Just Work™. In C++20 and beyond, it should be the default choice: the question isn’t “why are you using std::ranges::swap()?”, it is “why aren’t you using it?”. \$\endgroup\$
    – indi
    Apr 29, 2021 at 20:21
8
\$\begingroup\$

It will leak memory. Aside from not having move constructor or assignment, a big problem is that the assignment operator does not decrease the count for the assigned to object ("this", the value on the left of the equals sign). The result is that the memory allocated when sp5 is constructed is not freed when it is replaced using sp5 = sp4;.

One way to check for proper cleanup is to have a check on program exit (after all shared_ptr objects should have been destroyed) that countMap is empty.

Calling your class shared_ptr, while legal, can lead to confusion and possible conflicts if std::shared_ptr is used elsewhere in the code. Calling it something else (my_shared_ptr, shared_pointer, etc.) would avoid that possible confusion.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you for your review and spotting that memory leak! \$\endgroup\$ Apr 28, 2021 at 18:04
6
\$\begingroup\$

Design

Your design pays all the costs std::shared_ptr does and then some, but drops many of the capabilities.

  1. The smart-pointer itself is not smaller (assuming int is at least as big as a pointer, or the latter has alignment equal to size).

  2. Create and destroy enough of your smart pointers, and your id overflows. Hilarity ensues.

  3. The bookkeeping is likely not smaller (a map-node per unique id, 2 * pointer + 2 * number + whatever). std::shared_ptr has pointer to functions + managed pointer + 2 * number + stored deallocator (likely optimized out).

  4. Independent smart-pointers to the same type aren't independent, as they share the bookkeeping data (map and next id). Thus copying, creating and destroying smart-pointers leads to data races.

  5. Creating, copying, or destroying a smart-pointer has to do at least one expensive map-lookup. A big map is a major problem. Not so with std::shared_ptr.

  6. You cannot point to a sub-object, as doing so looses the association with the right bookkeeping data, and knowledge how to delete the object.

  7. You cannot accept a custom deleter. Where to store it?

The first two points can be fixed and the fourth mitigated by mapping directly from payload-pointer to owner-count, but that makes the last two much harder to tackle. Nor does it do anything for three and five. Best redesign properly.

Implementation

  1. You unconditionally create a managed object in the default ctor. Seems your design must be used with std::optional to represent null pointers too.

  2. Your copy-ctor and copy-assignment don't accept by constant reference. That is a pointless limitation, as they don't and shouldn't modify the argument.

  3. Copy-assignment fails to free the targets resources. Take care to accept self-assignment when fixing that.

  4. You have some spurious spaces at the beginning of some of the following lines. Also a spurious doubled space. Consider engaging some auto-formatter.

    template<typename  dataType>
     int shared_ptr<dataType>::id = 1;
     template<typename  dataType>
     std::map<int,int> shared_ptr<dataType>::countMap;
    

Testprogram

  1. Indentation in main() is lacking.

  2. return 0; is implicit in main().

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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