Max-sized array with normal STL interface, similar

问题:

Is there a class in boost similar to array which is a POD-like type with an array but provides for a variable number of items in the container. That is, I want to say the array has at most 10 items, but may contain from 0 to 10 items at any given moment.

boost::array unfortunately fixes size() to the constant N, so it can't work as a drop in replacement for a vector. In particular I'd like the readers of the structure not to know it is a static array, they can use begin() and end() like any other container.

Obviously push_back() would have to through an exception if it would grow beyond the capacity.

Something already in boost would be preferred.

NOTE: it must be a POD-like data type. For clarity, the entire array-like object, included the contents (which will themselves by POD-like types) must be POD-like. This is for serialization/copying reasons (and for performance related to that serialization/copying).

By POD-like I mean:

• has compile-time constant size
• can be safely memcpy'd

---

For those who say it can't work or isn't possible. There is nothing ingenious about this. The boost::array is a POD-like type. All it would take is adding one extra field, for the current size, to make that into what I want. I'm looking for an implementation that already exists (and is thus properly tested/maintained).

回答1:

The problem is (probably) initialization. How do you initialize the size, if it is a POD? How do you enforce the invariant size() <= max_size?

Technically, it would be easy to define something, but whether it would be useful or safe is another question. Why don't you just use boost::array, and maintain your current size as a separate variable?

-- James Kanze

回答2:

The closer thing I know of would be llvm::SmallVector<T,N> however it's slightly more complicated since it uses dynamically allocated storage when the size grows beyond N (it also copies the existing items, since the storage is guaranteed to be contiguous).

I don't think it would be difficult to realize such a container though, especially using boost::array as a backend. A simple wrapper to maintain the size and move the items around (taking inspiration from the code of vector for example) should be sufficient.

回答3:

You say "it must be a POD data type". Your collection does not need to be POD?

If the data type is POD then std::vector provides the functionality you need and many implementation will optimise copy/move semantics where the data is POD.

Why do you need to replace vector?

To answer the question directly though: I doubt there is such a class in boost as vector (maintaining a size) already achieves the purpose and therefore they would consider no real need for it. boost::array does not have a concept of a different size and capacity.

You could easily write your own wrapper class around vector or boost::array to throw if it has exceeded the capacity you set.

Now if you were going to implement this the most likely approach would be a class that contains a vector or a boost array or a regular array and then implement all your functions. I would say that is intuitive but there may be a more clever solution to overload the allocator instead to internally hold a boost::array and use it to make your vector's "allocations". If your allocator runs out of capacity (because its internal array is full) you throw (should probably be bad_alloc). Users then simply use the class as vector and can call all its functions but you will throw if they try to grow the vector higher than its size.

Due to the nature of vector your allocator not be expected to work as a heap where you free certain objects. You will simply be maintaining a contiguous buffer.

With regards to the POD or nearly POD issue, the actual data in the vector is guaranteed to be a contiguous buffer, and internally your allocator is using boost::array so it will be contiguous. If you want something for serialization then boost::serialize will already work with vectors properly.

The whole collection, container and contents, must be a single block of memory of fixed size: determined at compile-time

Your allocator could look like this:

typename< typename T, size_t SIZE >
class Allocator
{
    struct Data
    {
        size_t num_used;
        T[SIZE] data;
    } d;

public:
    // implement allocator's methods
};

Implement these

回答4:

POD stand for plain old data. "A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type." Basically by definition anything that can be resized at runtime cannot be POD.

回答5:

One other alternative (if you cannot be bothered to RYO) is to use boost::optional<T> for the array, for example:

boost::array<boost::optional<int>, 10>

The advantage of the above is that you can test each entry to see if it has been set or not rather than using some value state for uninitialized. This should still allow a direct memcopy of the object (whether it's stack or dynamically allocated).

回答6:

I needed something similar, the motivation was performance, as the cache locality is obviously better than in the dynamically allocated vector.

I created very simple custom class to do this for me.

#pragma once
#include <boost/array.hpp>

template<class T, class IndexType, IndexType MaximumSize>
class StaticVector : public boost::array<T, MaximumSize>
{
  IndexType count;
public:
  StaticVector() : count(0) {}
  inline void add(const T& value)
  {
    if (this->full())
      throw std::runtime_error("Can't add (size = %d)\n", MaximumSize);
    (*this)[this->count] = value;
    this->count++;
  }

  inline void addDirty()
  {
    if (this->full())
      throw std::runtime_error("Can't add, container full.");
    this->count++;
  }

  inline void remove(IndexType index)
  {
    if (this->count > 1)
      (*this)[index] = (*this)[count - 1];
    this->count--;
  }

  inline void clear() { this->count = 0; }
  inline IndexType size() const { return this->count; }
  inline bool empty() const { return this->count == 0; }
  inline bool full() const { return this->count == MaximumSize; }
  inline const T& back() const { return (*this)[this->count - 1]; }
  inline T& back() { return (*this)[this->count - 1]; }

  inline typename boost::array<T, MaximumSize>::iterator  end()       { return this->elems + count; }
  inline typename boost::array<T, MaximumSize>::const_iterator  end() const { return this->elems + count; }
  inline typename boost::array<T, MaximumSize>::const_iterator cend() const { return this->elems + count; }
};