Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Everyone knows you can't put a Derived in an std::vector<Base>. I decided to implement a collection which does allow you to do this:

#pragma once
#include <boost/iterator/indirect_iterator.hpp>
#include <type_traits>
#include <vector>

template<typename T, std::size_t BLOCK_SIZE, std::size_t ALIGNMENT=alignof(T)>
class DerivedVector {
    struct Block;
  public:
    using value_type = T;
    using reference = T&;
    using const_reference = T const&;
    using pointer = T*;
    using const_pointer = T const*;

  private:
    struct TypeInfo {
        using deleter_t = void(*)(void*);
        deleter_t deleter;
        using mover_t = void(*)(Block&, void*);
        mover_t mover;
    };

    template<typename D>
    struct TypeInfoImpl {
        static_assert(std::is_destructible<D>::value, "Derived class not destructible");
        static_assert(std::is_move_constructible<D>::value, "Derived class not move-constructible");
        static_assert(std::is_base_of<T, D>::value, "Class is not derived");
        static_assert(sizeof(D) <= BLOCK_SIZE, "Derived class too big");
        static_assert(ALIGNMENT % alignof(D) == 0, "Derived class has incompatible alignment");

        static void deleter(void* p) {
            static_cast<D*>(p)->~D();
        }

        static void mover(Block& p, void* o) {
            new (p.data()) D(std::move(*static_cast<D*>(o)));
        }

        static TypeInfo* get() {
            static TypeInfo info{deleter, mover};
            return &info;
        }
    };

    struct Block {
        using element_type = T;
        TypeInfo* info = nullptr;
        typename std::aligned_storage<BLOCK_SIZE, ALIGNMENT>::type storage;

        Block() = default;

        template<typename D, typename CONDITION = typename std::enable_if<std::is_base_of<T, typename std::remove_reference<D>::type>::value>::type>
        Block(D&& d) {
            construct(std::forward<D>(d));
        }

        Block(Block&& b) : info(b.info) {
            if (info)
                info->mover(*this, b.data());
        }

        Block& operator=(Block&& b) {
            if (this == &b)
                return *this;
            destroy();
            info = b.info;
            info->mover(*this, b.data());
            return *this;
        }

        Block(Block const& b) = delete;
        void operator=(Block const&) = delete;

        template<typename D>
        void construct(D&& d) {
            using D_Val = typename std::remove_reference<D>::type;
            static_assert(!std::is_same<D_Val, D>::value || std::is_copy_constructible<D_Val>::value,
                "Derived class must be copy-constructible for this usage");
            new (data()) D_Val(std::forward<D>(d));
            info = TypeInfoImpl<D_Val>::get();
        }

        ~Block() {
            destroy();
        }

        void destroy() {
            if (!info)
                return;
            auto deleter = info->deleter;
            info = nullptr;
            deleter(data());
        }

        const_reference operator*() const {
            return *data();
        }

        reference operator*() {
            return *data();
        }

        const_pointer operator->() const {
            return data();
        }

        pointer operator->() {
            return data();
        }

        const_pointer data() const {
            return reinterpret_cast<const_pointer>(&storage);
        }

        pointer data() {
            return reinterpret_cast<pointer>(&storage);
        }
    };

    using container_type = std::vector<Block>;
    container_type elements;

  public:
    using size_type = typename container_type::size_type;
    using difference_type = typename container_type::difference_type;
    using iterator = boost::indirect_iterator<typename container_type::iterator>;
    using const_iterator = boost::indirect_iterator<typename container_type::const_iterator>;

    DerivedVector() = default;
    DerivedVector(DerivedVector&&) = default;
    DerivedVector& operator=(DerivedVector&&) = default;
    DerivedVector(DerivedVector const&) = delete;
    void operator=(DerivedVector const&) = delete;

    bool empty() const {
        return elements.empty();
    }

    size_type size() const {
        return elements.size();
    }

    size_type max_size() const {
        return elements.max_size();
    }

    reference operator[](size_type i) {
        return *elements[i];
    }

    const_reference operator[](size_type i) const {
        return *elements[i];
    }

    const_iterator begin() const {
        return elements.begin();
    }

    iterator begin() {
        return elements.begin();
    }

    const_iterator cbegin() const {
        return elements.cbegin();
    }

    const_iterator end() const {
        return elements.end();
    }

    iterator end() {
        return elements.end();
    }

    const_iterator cend() const {
        return elements.cend();
    }

    template<typename D>
    void push_back(D&& d) {
        elements.emplace_back(std::forward<D>(d));
    }

    void pop_back() {
        elements.pop_back();
    }

    template<typename D>
    void reconstruct(size_type i, D&& d) {
        elements[i].destroy();
        elements[i].construct(std::forward<D>(d));
    }
};

I'm looking for all-round feedback and criticism, suggestions for features, and any correctness concerns that may be present. Suggestions for an automatic way of determining BLOCK_SIZE and ALIGNMENT are also welcome. I'm also curious about what extra assertions I could be making to make the code fail in clearer ways when used with unreasonable Ts and Ds.

EDIT: I found some significant bugs, so the code has been updated.

share|improve this question
1  
Without having looked at the code in detail, could you please describe what advantage this solution has over just composing over a std::vector<std::unique_ptr<Base>> and exposing a value access interface? That would at the very least drastically reduce the code complexity. –  Konrad Rudolph Dec 7 '12 at 14:37
    
@KonradRudolph: I did it for the fun of it, but perhaps this could help with cache locality? Just taking a wild guess there. –  Anton Golov Dec 8 '12 at 19:16
    
It doesn’t help with cache locality – the vector of unique pointers is about as cache local as it gets. There’s an unrelated use-case where it does prove inconvenient: when you are using the same custom deleter for every object. Because then the vector of unique_ptr stores the custom deleter redundantly for every item in the vector, which is obviously a huge waste. But that’s not a concern here. –  Konrad Rudolph Dec 9 '12 at 14:59
1  
@KonradRudolph: Uhm, the objects themselves are nearly contiguous, unlike the way they'd be in the unique_ptr case, or am I missing something? –  Anton Golov Dec 9 '12 at 16:38
    
If your objective is to implement it for fun, just ignore the rest of this message. If your objective is to implement something you have not found anywhere, you might want to take a look to boost pointer container: boost.org/doc/libs/1_52_0/libs/ptr_container/doc/… For vectors: boost.org/doc/libs/1_52_0/libs/ptr_container/doc/… Maybe you will be able to find good ideas to complete your library, too. –  user20540 Dec 23 '12 at 15:49
show 1 more comment

1 Answer

Interesting.

You should add template <typename D, typename... Args> emplace_back(Args&&...).

In terms of automatically determining blocksize, you can add a helper function like:

template <typename... Args>
std::size_t get_max_size() {
  return std::max({ sizeof(Args)... });
}

Users can then list the derived classes they want to use and use that to compute the block size.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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