如何实现一个类似STL的容器并限制容器大小？

Question

在重构时，我想要更改一个数组，其中条目被添加到std :: vector中，但为了兼容性（持久性，降级等），它仍然需要具有上限。
有没有最好的方法（优雅，类似于STL，额外代码有限），可以拥有类似于STL的容器，其大小受限制，因此您知道插入条目会失败？ 编辑:
澄清一下：我想要一个类似于STL的容器，它从空开始，您可以填充条目并可能删除条目，并且可以迭代已填充的条目，但不允许放入超过例如50个条目，因此几乎就像是一个顺序容器，但具有上限。

- stefaanv

---

你正在寻找一个循环缓冲区吗？ - John Dibling

@stefaanv：如果用户向已满容器中添加新元素会发生什么？ - John Dibling

@John：我们记录下该操作失败的信息。 - stefaanv

不，我的意思是元素和集合会发生什么情况？我猜测元素会被丢弃，而集合保持不变？ - John Dibling

@John：是的，这就是应该发生的事情，用户必须知道，因此需要记录。 - stefaanv

Answer 1

一个简单的解决方案是在自己限定大小的容器内封装一个向量。你可以使用私有组合或私有继承——请注意，私有继承模拟了实现方式，并且没有公有继承的某些缺点。

编辑：使用私有继承的解决方案草图

template <typename T, unsigned int N>
class fixed_vector : std::vector<T>
{
    typedef std::vector<T> vector_type;
public:
    typedef typename vector_type::reference reference;
    typedef typename vector_type::const_reference const_reference;
    typedef typename vector_type::iterator iterator;
    typedef typename vector_type::const_iterator const_iterator;
    typedef typename vector_type::value_type value_type;
    typedef typename vector_type::size_type size_type;

    fixed_vector() : vector_type() {}
    fixed_vector( size_type size, value_type const & value = value_type() )
       : vector_type(size,value)
    {}      

    void push_back( value_type v ) {
        ensure_can_grow();
        vector_type::push_back( v );
    }
    iterator insert( iterator position, value_type const & v ) {
        ensure_can_grow();
        vector_type::insert( position, v );
    }
    void reserve( size_type size ) {
        if ( size > N ) throw std::invalid_argument();
        vector_type::reserve( size );
    }
    size_type capacity() const {
        // In case the default implementation acquires by default 
        // more than N elements, or the vector grows to a higher capacity
        return std::min( vector_type::capacity(), N );
    }
    // provide other insert methods if required, with the same pattern
    using vector_type::begin;
    using vector_type::end;
    using vector_type::operator[];
    using vector_type::erase;
    using vector_type::size;
    using vector_type::empty;
private:
    void ensure_can_grow() const {
        // probably a different exception would make sense here: 
        if ( this->size() == N ) throw std::bad_alloc();
    }
};

这里有很多比较抽象的描述... std::vector 接受更多的参数，可以添加到外观中。如果您需要其他方法或 typedefs，则可以使用 using 声明将它们引入作用域，重新定义 typedef，或使用特定测试实现适配器。

此外，在此实现中，大小是编译时常量，但很容易将其修改为构造函数参数。

- David Rodríguez - dribeas

---

私有继承固然不错，但容器接口过于繁琐。看看需求列表和可选需求，再加上vector更多的要求... - Potatoswatter

用户需求似乎较少：填写条目、删除、迭代。您可以实现一个非标准容器，只提供所需的功能，可能不到50行代码（包括所有适当的typedef）。 - David Rodríguez - dribeas

注意：这个草图已经有47行了，而且非常简洁。将这个类的限制与我的解决方案中构造对象后仅需调用“reserve”的单一要求进行对比。 - Potatoswatter

@Potatoswatter：这个草图超出了问题中建立的要求。使用有限的分配器是错误的，因为容器增长的方式是未定义的。请注意，仅构造向量（而不实际将元素插入其中）可能已经触发了分配。在创建向量之前没有控制容量的方法，并且不能保证一旦创建它就已经太晚了。 - David Rodríguez - dribeas

@David：OP没有尝试描述他的所有要求...使用STL类更加简洁，不必担心功能集。虽然分配时间表是实现定义的，但请求大于Allocator::max_size的分配有点愚蠢，因为reserve已经需要将其参数与max_size进行比较。对于一个空向量分配内存需要一种相当悲观的实现。按照同样的逻辑，任何向量都有可能在一开始就崩溃。 - Potatoswatter

@David：谢谢，我选择了私有组合，但最终它与你的代码类似。 - stefaanv

Answer 2

定制向量类以施加上限。可能，您可以公开一个新的api，该api将检查大小是否超过上限，并在超过时返回false，否则调用常规插入方法。

- Hemant

---

@Hemant：你有没有代码片段来说明你的观点？你可能想看一下https://dev59.com/f3NA5IYBdhLWcg3wh-cC - Chubsdad

@stefaanv：不允许继承。定制化正是我采取的方法。 - Potatoswatter

@stefaanv：不仅不鼓励这样做，对于容器来说这是一个相当糟糕的想法。您必须复制所有构造函数，包括两个以棘手的方式别名的构造函数。 - Potatoswatter

人们经常夸大从STL容器派生的问题。如果您没有添加数据成员，那么您不需要虚析构函数，除非派生容器本身（而不是它们的元素）的所有权很复杂，否则通过基指针意外销毁的问题也不存在。在您做出这种设计决策的95％时间中，显然是安全的。您通常也不需要所有构造函数。如果您提供一个用于任意客户端使用的库，则应更加担心 :-）。 - Tony Delroy

关于上述内容的另一个要点是，派生问题是健壮可维护性的问题，尽管存在不完美的边角情况，但采取明显的方法会极大地受益于简单和清晰。这些问题已经被充分理解。随意编写一些替代方案通常更容易出错，并可能降低生产力和健壮性。 - Tony Delroy

Answer 3

您可以创建一个自定义分配器（例如派生自std::allocator），拒绝为大于给定大小的数组分配内存。

请注意，在向对象添加内容之前，您需要调用reserve(vector_max)。我正在对C++标准提出缺陷报告，因为这个要求是不必要的（在最近版本的GCC上也是如此）。

template< typename T, size_t N >
struct limited_alloc : std::allocator< T > {
    size_t max_size() const { return N; }
    typename std::allocator<T>::pointer allocate( size_t n ) {
        if ( n < N ) return std::allocator<T>::allocate( n );
        throw std::length_error( "array too large" );
    }

    limited_alloc() {} // silly cruft for standard requirements:
    template< typename T2 >
    limited_alloc( limited_alloc<T2,N> const & ) {}
    template< typename T2 >
    struct rebind { typedef limited_alloc<T2,N> other; };
};

enum { vector_max = 40 };

template< typename T >
struct limited_vector {
    typedef std::vector< T, limited_alloc< T, vector_max > > type;
};

void f() {
    limited_vector< int >::type x;
    x.reserve( vector_max );
    x.assign( vector_max + 1, 3 ); // throws.
}

- Potatoswatter

---

向量扩展容量的方式与它们的使用大小不同（例如，单个push_back可能会触发要求加倍容量），这似乎阻止了这种方法：你正在限制容量，但在size()达到预期极限之前可能会达到容量上限。 - Tony Delroy

标准并不保证每次都会加倍，例如可能在前两次分配时分配对象的内存页，然后才会加倍。reserve()是一个相当强烈的要求，不要将分配填充。 - Tony Delroy

@Tony：是的，尽管大多数实现只会翻倍或更少。实际上，max_size 为 vector 提供了足够的信息，使得一个好的实现不应该超过它。vector 可以和应该捕获 bad_alloc 并使用 max_size 重试分配。然而，GNU 不这样做，它只在大小溢出时使用 max_size，这有点奇怪。与所有分配器相关的事情一样，标准在这个问题上也很混乱。 - Potatoswatter

@stefaanv：分配器不能拥有东西，所以不行。但是你可以调用reserve(vector_max)或在调用reserve(vector_max)的工厂函数中生成数组；这将可靠地设置一个硬限制。 - Potatoswatter

哎呀，我对GNU的说法太早了。GCC 4.2.1仅在将容量乘以2导致算术溢出时使用max_size；GCC 4.5每次都使用max_size进行检查，并且应该与此分配器无缝配合。 - Potatoswatter

Answer 4

请查看我一段时间前发现的这个static_vector实现，我认为它恰好符合您的要求。

它采用非常自由的boost许可证分发，因此您可以对其进行几乎任何操作。

- sbi

---

这可能是最好的选择，因为它会提供一个完整的容器，但即使使用自由许可证的代码也需要获得批准，所以我将从向量开始进行自己的实现。 - stefaanv

@stefaanv：糟糕，公司头疼了。虽然我不是律师，但把_你的_代码合并到公司的代码中会有问题吗？如果没有，那么该代码的许可证足够自由，让你可以从头文件中删除代码并将其放入自己的头文件中，使用任何你想使用的版权。然后你只需要面对被认为较小的障碍，即获得批准使用你自己的代码。这比用官僚系统打败它自己的武器要好一些。:) - sbi

谢谢你的建议，但目前我对我的实现感到满意（类似于dribeas的建议）。 - stefaanv

Answer 5

看一下Boost.Array

作为普通数组的替代，STL提供了std::vector类。然而，std::vector<>提供了动态数组的语义。因此，它管理数据以便能够更改元素的数量。这会导致一些开销，如果只需要静态大小的数组。

- dirkgently

---

如果您的上限非常低，那就是这样。 - Viktor Sehr

那么，我仍然需要自定义数组以提供添加/删除功能吗？ - stefaanv

Answer 6

看一下 boost::array

编辑：如果需要添加/删除元素，可以使用 boost::optional 作为 boost::array 的元素类型。

- dimba

---

你仍然需要一个数组的迭代器。 - Potatoswatter