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\$
1
  • 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\$ 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\$
5
  • \$\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
  • \$\begingroup\$ Can you explain what you mean by the storage allocated following an arithmetic series instead of a geometric series? Geometric growth for a container I understand to mean that when reallocating for a bigger container it follows a multiplication model, for example 1.5 times larger than the existing size. If you reallocate a bigger size of 1.5 times, what does it that the actual storage will "follow an arithmetic series"? \$\endgroup\$
    – Zebrafish
    Aug 19 at 2:34
  • \$\begingroup\$ @Zebrafish: Basically, that when allocate more space (let's say double your current size), the OS is typically going to give you address space, with no memory committed to most of it. Then it'll allocate actual memory as you use it, typically in one-page increments (usually 4K or 8K apiece). Depending on the amount of memory your system has free, above some fairly low limit, the time to allocate N pages will usually be roughly proportional to N. \$\endgroup\$ Aug 19 at 4:52
  • \$\begingroup\$ So if I've got this straight: You ask for 256 bytes, the OS grants you that and returns to you a pointer to it. Let's say page size is 32, you write to byte [0] and [31], which both fit on the first page. Then I want to write to byte [67], which crosses onto another page. The OS takes my pointer value of base_ptr_address + 67 divided by the page size, and finds that it's on page [2], it then goes to page 2 and the modulus result is the address on that page? Are pages not contiguous in memory? \$\endgroup\$
    – Zebrafish
    Aug 19 at 9:48
  • \$\begingroup\$ @Zebrafish: Yes, the address you use gets split into a page number, and an offset in that page. No, pages aren't necessarily at contiguous addresses. \$\endgroup\$ Aug 19 at 16:06

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.