构建可跟踪元素存储大小的容器：如何规避冗余样板代码？

我正在研究一种容器实现方案，除基础容器功能外，还能跟踪所存储元素的总大小。目前了解到的方案都需要为容器的每个修改型成员函数编写大量样板代码，而且大多假设元素存储后大小保持不变。

我不确定标准容器是否支持注入这类行为，以下是简化后的可行示例：

typedef uint8_t   Byte;
typedef Byte  PacketId;

template <class T>
struct CollectionTraits {
    typedef T             collection_type;
    typedef typename collection_type::value_type   value_type;
    typedef typename collection_type::size_type    size_type;
    typedef typename collection_type::iterator     iterator;
    typedef typename collection_type::reference    reference;
    typedef typename collection_type::const_iterator   const_iterator;

    const_iterator begin() const { return _collection.begin(); }
    const_iterator end() const  { return _collection.end(); }
    iterator begin() { return _collection.begin(); }
    iterator end()   { return _collection.end(); }

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

protected:
    T                _collection;
};

struct Packet : CollectionTraits<std::vector<Byte>>
{   
   PacketId           id;
};

容器实现如下：

struct  PacketList :  CollectionTraits<std::deque<Packet>>
{
public:
    typedef Packet::size_type             data_size;

    void     clear() { _collection.clear(); _total_size = 0; }

    data_size total_size() const  { return _total_size; }

    void push_back(const Packet& v) { 
        _collection.push_back(v); 
        _add(v);
    }

    void push_back(const Packet&& v) { 
        _collection.push_back(std::move(v)); 
        _add(v);
    }

    void push_front(const Packet& v) { 
        _collection.push_front(v); 
        _add(v);
    }

    void push_front(const Packet&& v) { 
        _collection.push_front(std::move(v)); 
        _add(v);
    }

    void pop_back() {
        _remove(_collection.back());
        _collection.pop_back(); 
    }

    void erase(const_iterator first, const_iterator last) {
        for(auto it = first; it != last; ++it) _remove(*it);
        _collection.erase(first, last);
    }    
    PacketList() : _total_size(0) {}
    PacketList(const PacketList& other) : _total_size(other._total_size) {}

private:
    void _add(const Packet& v)    { _total_size += v.size(); }
    void _remove(const Packet& v)  { _total_size -= v.size(); }

    data_size           _total_size;
};

最终容器接口需要和标准容器类似。请问有没有方法避免这类大量重复代码？是否存在针对该问题的标准解决方案？

1. 用装饰器模式封装标准容器 #

不用继承标准容器或自定义Traits，写一个通用的SizeTrackingContainer模板类，内部持有标准容器实例并维护总大小。通过转发非修改操作到内部容器，仅在修改元素的操作中插入大小更新逻辑，实现代码复用：

template <typename Container>
class SizeTrackingContainer {
public:
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;
    using iterator = typename Container::iterator;
    using const_iterator = typename Container::const_iterator;

    // 转发基础容器的非修改操作
    iterator begin() { return _container.begin(); }
    const_iterator begin() const { return _container.begin(); }
    iterator end() { return _container.end(); }
    const_iterator end() const { return _container.end(); }
    size_type size() const { return _container.size(); }
    bool empty() const { return _container.empty(); }

    // 自定义总大小查询接口
    size_type total_element_size() const { return _total_size; }

    // 插入元素时更新总大小
    void push_back(const value_type& val) {
        _container.push_back(val);
        _total_size += val.size();
    }

    void push_back(value_type&& val) {
        _container.push_back(std::move(val));
        _total_size += val.size();
    }

    void push_front(const value_type& val) {
        _container.push_front(val);
        _total_size += val.size();
    }

    void push_front(value_type&& val) {
        _container.push_front(std::move(val));
        _total_size += val.size();
    }

    // 删除元素时更新总大小
    void pop_back() {
        if (!_container.empty()) {
            _total_size -= _container.back().size();
            _container.pop_back();
        }
    }

    void pop_front() {
        if (!_container.empty()) {
            _total_size -= _container.front().size();
            _container.pop_front();
        }
    }

    iterator erase(const_iterator first, const_iterator last) {
        for (auto it = first; it != last; ++it) {
            _total_size -= it->size();
        }
        return _container.erase(first, last);
    }

    iterator erase(const_iterator pos) {
        _total_size -= pos->size();
        return _container.erase(pos);
    }

    void clear() {
        _container.clear();
        _total_size = 0;
    }

    // 转发构造函数，初始化时计算现有元素总大小
    template <typename... Args>
    explicit SizeTrackingContainer(Args&&... args) : _container(std::forward<Args>(args)...) {
        for (const auto& elem : _container) {
            _total_size += elem.size();
        }
    }

private:
    Container _container;
    size_type _total_size = 0;
};

使用时直接实例化：

using PacketList = SizeTrackingContainer<std::deque<Packet>>;

2. 处理元素大小动态变化的场景 #

如果元素存储后大小可能改变，仅在插入/删除时更新总大小不够。可以给元素添加观察者机制，让元素大小变化时主动通知容器：

struct Packet : CollectionTraits<std::vector<Byte>>
{   
    PacketId id;
    std::function<void(size_type old_size, size_type new_size)> on_size_change;

    // 重写修改内部vector的方法，触发回调
    void push_back(const Byte& b) {
        auto old_size = size();
        _collection.push_back(b);
        if (on_size_change) {
            on_size_change(old_size, size());
        }
    }

    // 其他修改vector的方法同理实现回调触发逻辑
};

然后在SizeTrackingContainer的插入逻辑中绑定回调：

void push_back(value_type&& val) {
    auto elem_it = _container.insert(_container.end(), std::move(val));
    auto& elem = *elem_it;
    _total_size += elem.size();
    // 绑定回调，同步元素大小变化到总大小
    elem.on_size_change = [this](size_type old_size, size_type new_size) {
        _total_size += (new_size - old_size);
    };
}

3. 标准库相关方案 #

C++标准库没有直接提供跟踪元素总大小的容器。分配器主要负责内存管理，不适合跟踪元素逻辑大小；如果可以使用第三方库，boost::container的decorated_container是现成的扩展方案，若不能依赖第三方库，自己实现装饰器是最直接的选择。

内容的提问来源于stack exchange，提问作者Swift - Friday Pie