Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Container of fixed dynamic size

Is there a standard container for a sequence of fixed length, where that length is determined at runtime. Preferrably, I'd like to pass an argument to the constructor of each sequence element, and use that argument to initialize a const member (or a reference). I'd also like to obtain the sequence element at a given index in O(1). It seems to me that all of my requirements cannot be met at the same time.

  • I know std::array has fixed length, but that length has to be known at compile-time.
  • std::vector has dynamic size, and allows passing contructor arguments using emplace. Although you can reserve memory to avoid actual reallocations, the type still has to be movable to theoretically allow such reallocations, which e.g. prevents const members.
  • Then there is std::list and std::forward_list, which don't require a movable type, but which are still resizable and will perform rather poorly under random-access patterns. I also feel that there might be considerable overhead associated with such lists, since each list node will likely be allocated separately.
  • Strangely enough, std::valarray is my best bet so far, since it has a fixed length and won't resize automatically. Although there is a resize method, your type won't have to be movable unless you actually call that method. The main deficit here is the lack for custom constructor arguments, so initializing const members isn't possible with this approach.

Is there some alternative I missed? Is there some way to adjust one of the standard containers in such a way that it satisfies all of my requirements?


Edit: To give you a more precise idea of what I'm trying to do, see this example:

class A {   void foo(unsigned n); };  class B { private:   A* const a;   const unsigned i; public:   B(A* aa) : a(aa), i(0) { }   B(A* aa, unsigned ii) : a(aa), i(ii) { }   B(const std::pair<A*, unsigned>& args) : B(args.first, args.second) { }   B(const B&) = delete;   B(B&&) = delete;   B& operator=(const B&) = delete;   B& operator=(B&&) = delete; };  void A::foo(unsigned n) {   // Solution using forward_list should be guaranteed to work   std::forward_list<B> bs_list;   for (unsigned i = n; i != 0; --i)     bs_list.emplace_front(std::make_pair(this, i - 1));    // Solution by Arne Mertz with single ctor argumen   const std::vector<A*> ctor_args1(n, this);   const std::vector<B> bs_vector(ctor_args1.begin(), ctor_args1.end());    // Solution by Arne Mertz using intermediate creator objects   std::vector<std::pair<A*, unsigned>> ctor_args2;   ctor_args2.reserve(n);   for (unsigned i = 0; i != n; ++i)     ctor_args2.push_back(std::make_pair(this, i));   const std::vector<B> bs_vector2(ctor_args2.begin(), ctor_args2.end()); } 
like image 259
MvG Avatar asked Feb 15 '13 12:02

MvG


2 Answers

I think const std::vector<T> has the properties you ask for. Its elements aren't actually defined with const, but it provides a const view of them. You can't change the size. You can't call any of the member functions that need T to be movable, so for normal use they won't be instantiated (they would be if you did an extern class declaration, so you can't do that).

If I'm wrong, and you do have trouble because T isn't movable, try a const std::deque<T> instead.

The difficulty is constructing the blighter -- in C++11 you can do this with an initializer list, or in C++03 you can construct a const vector from a non-const vector or from anything else you can get iterators for. This doesn't necessarily mean T needs to be copyable, but there does need to be a type from which it can be constructed (perhaps one you invent for the purpose) .

like image 22
Steve Jessop Avatar answered Oct 09 '22 06:10

Steve Jessop


Theoretically vector has the properties you need. As you noted, actions that possibly do assignments to the contained type, including especially any sequence modifications (empace_back, push_back, insert etc.) are not supported if the elements are noncopyable and/or nonassignable. So to create a vector of noncopyable elements, you'd have to construct each element during vector construction.

As Steve Jessop points out in his answer, if you define the vector const in the first place you won't even be able to call such modifying actions - and of course the elements remain unchanged as well.

If I understand correctly, you have only a sequence of constructor arguments, not the real object sequence. If it's only one argument and the contained type has a corresponding constructor, things shoule be easy:

struct C {   const int i_;     C(int i) : i_(i) {} };  int main() {   const std::vector<C> theVector { 1, 2, 3, 42 }; } 

If the constructor is explicit, you have to make a list first or explicitly construct the objects in the initializer-list:

int main() {   auto list = { 1, 2, 3, 4 };   const std::vector<C> theVector (std::begin(list), std::end(list));   const std::vector<C> anotherVector { C(1), C(44) }; } 

If it's more than just one argument per constructed object, consider a intermediate creator object:

struct C {   const int i_;     C(int i, int y) : i_(i+y) {} };  struct CCreator {    int i; int y;    explicit operator C() { return C(i,y); } };  int main() {   const std::vector<CCreator> ctorArgs = { {1,2}, {3,42} };   const std::vector<C> theVector { begin(ctorArgs), end(ctorArgs) }; } 
like image 118
Arne Mertz Avatar answered Oct 09 '22 04:10

Arne Mertz