2
\$\begingroup\$

So, yes, I know that "you shouldn't derive from std containers" but by now it's more of philosophical rule in my mind than a technical one. I've googled again for the one fundamental reason one should never-ever-ever-ever-do-that-ever-ever-ever-or-you-die but couldn't find it.

So, if there's nothing fundamentally wrong with the following and if we set aside performance considerations, can I a get a plain-old code review of this:

namespace growth
{
    template<size_t N>
    class linear
    {
    public:
        static_assert(N != 0, "Linear growth requires positive factor");

        static size_t grow(size_t size, size_t capacity)
        {
            return (size == capacity) ? capacity + N : capacity;
        }
    };

    template<typename Ratio = std::ratio<2, 1>>
    class geometric
    {
    public:
        static_assert(Ratio::num > Ratio::den, "Geometric growth requires ratio greater than 1");

        static size_t grow(size_t size, size_t capacity)
        {
            return (size == capacity) ? std::max((size_t)(capacity * (Ratio::num / (double)Ratio::den)), capacity + 1) : capacity;
        }
    };
}

template<typename T, typename Growth, class Allocator = std::allocator<T>>
class custom_growth_vector : public std::vector<T, Allocator>
{
public:
    using vector = std::vector<T, Allocator>;

    using vector::vector;

    void push_back(T&& value)
    {
        vector::reserve(Growth::grow(vector::size(), vector::capacity()));
        vector::push_back(value);
    }

    // Also replace emplace_back, insert, etc.
};

// ...

// Grows by 50% rather than double when size == capacity.
custom_growth_vector<int, growth::geometric<ratio<3, 2>>> cgvi;
\$\endgroup\$
  • 2
    \$\begingroup\$ As it happens I just wrote a blog about that. lokiastari.com/blog/2016/03/25/resizemaths Turns out you want a growth factor 1 < r < = 1.618 (assuming you want to be able to reuse released memory). \$\endgroup\$ – Martin York Apr 1 '16 at 20:15
2
\$\begingroup\$

Let's start with an attempt at a short summary of the situation with inheritance.

As long as you just create/use/destroy an object of your type, the fact that it inherits publicly from a standard container doesn't lead to a problem.

The problem arises if you have pointer (or reference) to the base class that refers to an object of the derived class, and you destroy the object via that pointer to base.

std::vector<int> *t = new custom_growth_vector<int, growth::geometric<ratio<3, 2>>>;

// ...

delete t; // This causes undefined behavior

Unfortunately, there's nothing you can do in your class to prevent this--part of the definition of public inheritance is that it allows implicit conversion to the base class.

Aside from that:

Linear growth

Using your growth::linear class means that any vector you create this way no longer meets the requirement for push_back to have amortized-constant complexity. In the other direction, this does mean the amount of space that's "wasted" by growing the vector is limited to a constant.

push_back

push_back normally has overloads for both const lvalue reference, and rvalue reference, though this may just be another member function you haven't provided (yet).

Growth Factor

I guess the biggest problem I see in the end is the fairly simple question what the real point of this is supposed to be. Most systems use virtual memory, which typically means that even if you think you're expanding an allocation following a geometric series, chances good that the system will allocate actual storage for your data following an arithmetic series, almost regardless of what you try to do.

\$\endgroup\$
  • \$\begingroup\$ "Destroying an instance of a class that derives from a base with a non-virtual destructor through a pointer or reference to said base class causes undefined behavior" is the never-ever-ever-ever-do-that-ever-ever-ever-or-you-die reason I was looking for. \$\endgroup\$ – screwnut Apr 1 '16 at 22:38

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.