-9

In my program, I often need an owning array-like container - i.e. for data stored contiguously in memory, but vector is too flexible and less practical or efficient than it could be.

The requirements differ from std::vector in one or more aspects such as:

  • Elements can only be inserted at the end, without moving other elements
  • Capacity cannot be changed after construction / after compilation
  • Size can't be changed after construction / after compilation
  • Storage is inherent in the class and does not involve an allocator
  • No weird special-casing for a single type like std::vector<bool>
  • References and/or iterators don't get invalidated on insertion
  • etc.

If necessary, I'll implement such a container myself, but likely it already exists in the standard library or in a popular one like Boost.

The thing is, it can be hard to find, maybe it has a fancy name that you don't expect. So, what vector-like containers within the above parameter space exist?

Even if my requirements aren't met in an existing container, a reference list helps: if I do end up implementing a new container, I can adopt appropriate names and avoid confusing names.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 5
    This question has way too many "and/or"s in it. A runtime-sizeable array is very different from a compile-time sizeable array, and an array that can be resized with a fixed capacity is very different from the others. You basically seem to be asking for *every possible variation* of `vector`, perhaps on the assumption that every possible variation represents some kind of efficiency improvement over all of the others in some way. – Nicol Bolas May 06 '21 at 16:06
  • "You basically seem to be asking for every possible variation of vector" <- The question is about _one_ variation, but not about any specific one variation. And the information requested is what variations are well-established. So again not "every possible variation". If I asked about a specific one, the answer(s) would naturally focus on just that one, i.e. "this is widely known as foo_vector, use that" or "Not widely available, write it yourself". – einpoklum May 07 '21 at 10:01
  • 2
    "*The question is about one variation, but not about any specific one variation. And the information requested is what variations are well-established.*" That's a contradiction. You can be asking about "variations" in the plural if you're asking about "one variation". – Nicol Bolas May 07 '21 at 13:33
  • This question is [being discussed on Meta](https://meta.stackoverflow.com/questions/407489/this-question-of-mine-was-closed-due-to-lack-of-focus-but-it-shouldnt-be-more) – Machavity May 07 '21 at 14:06

1 Answers1

3

Here are the ones I know of:

There are also "variable-length arrays" and "arrays with runtime bounds", which do not exist in C++; the former exists in C. See also this question and this answer about these non-C++ containers.

Let's compare the features of all of these. If the container you want doesn't match one of the lines below exactly, you'll need to implement your own and choose a name for it.

Criterion C array array vector unique_ptr valarray dynarray static_vector small_vector stable_vector
Origin/library language std std std std discarded std Boost Boost Boost
Type parameters T,N T,N T,A T T T T,C,O T,N,A,O T,A
Capacity fix time Compile Compile Never (Construct) Never Construct Compile Never Never
Size fix time Compile Compile Never N/A Never Construct Construct Never Never
Size = capacity always? ✔ ✔ ✕ N/A ✕ ✔ ✕ ✕ ✕
Storage typically on Stack Stack Heap Heap Heap Heap Stack Stack/Heap Heap
Stable iterators? N/A N/A ✕ N/A N/A N/A (✔) ✕ ✔
Constraint on element type ✕ ✕ ✕ ✕ ✔ ✕ ✕ ✕ ✕

Template parameter legend:

  • A for allocator
  • T for element type
  • N for size in number of elements
  • C for capacity in number of elements
  • O for options

Finally, an interesting but less popular vector-like container is the "veque", or deque-vector amalgam.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 1
    Did you just write all this for this answer, or is there a source link for the information? It would help increase confidence that no mistakes crept in. Also, really I think the only thing that matches the question would be `static_vector` (_maybe_ VLAs if judiciously used). Other things seem close to the opposite of what's being asked (eg `stable_vector`) – sehe May 06 '21 at 09:50
  • @sehe: 1. Myself, I keep mixing up valarry with dynarray and having to look them up; and also forgetting whether what's already implemented is a container with capacity fixed on construction and variable size or both capacity and size fixed on construction. I keep remembering that dynarray is that, while it actually isn't. So, I decided to make a table of all of them 2. I added an "etc." to the question phrasing to make the correspondence with the answer clearer. – einpoklum May 06 '21 at 10:20
  • 1
    Oh. I see now that you're not trying to ask for a specific container.. When I read the question, I still get the impression your asking for one specific container that meets all the specified criteria (and you'll witte it yourself, but only if necessary). Do you mind if I propose an edit to clarify the question? – sehe May 06 '21 at 10:59
  • @sehe: No, I don't mind, and actually I think all users should be accepting of proposed edits without giving express permission. I mean, that's what the site is for, it's a collectively-edited Q&A. Go right ahead. That doesn't mean I'll like the edit of course - but if I don't I'll change it back or comment about it. – einpoklum May 06 '21 at 15:10