14

I want to have a certain kind of std::vector that cannot have more than const int MAX_LENGTH elements. I understand that I cannot override std::vector non-virtual functions, which I'd need to do to put a size check in all the relevant member functions (e.g., assign, push_back...there are so many). The most obvious way to do this is to wrap std::vector in a class that ensures no operation adds beyond the maximum length. But this seems clunky. Is there a more elegant solution than a wrapper class to limit std::vector size?

helloB
  • 3,472
  • 10
  • 40
  • 87
  • @LuchianGrigore Nope, I need a vector or vector-like interface. – helloB Jul 31 '15 at 16:10
  • 5
    What kind of behavior do you expect if this is violated? If the vector is at it's capacity, what should `push_back` (or equiv) do? Throw an exception? Silently discard that element? Add that element at the expense of the first element (FIFO queue kind of behavior)? – Cory Kramer Jul 31 '15 at 16:10
  • @CoryKramer I would want to throw an exception and remind the user they had violated the terms of using that particular kind of vector (the vector being one that uses a particular allocator) – helloB Jul 31 '15 at 16:12
  • I don't think you need to use a custom allocator to achieve this. If you did, you'd still need to write exception behaviour for custom allocator. A wrapper class actually does sound like least clunky solution. – kchoi Jul 31 '15 at 16:23
  • Just don't add more than `MAX_LENGTH` elements... – Lightness Races in Orbit Jul 31 '15 at 16:32
  • @LightnessRacesinOrbit This might be included in a large code base with multiple clients, so that's not an option. That's why I need to throw an error if the client violates terms of use. – helloB Jul 31 '15 at 16:34
  • 3
    Then your "clunky" solution sounds spot-on and actually perfectly elegant. Ensure you use private inheritance as Kuba explains. (Isn't this use case the entire point of private inheritance?) – Lightness Races in Orbit Jul 31 '15 at 16:35
  • A custom allocator limiting the maximum capacity should do it. –  Jul 31 '15 at 16:40
  • 1
    @DieterLücking: but the requirement is to limit the size, and vectors are in effect required by the standard to over-allocate on appends for performance reasons, which means that a capacity limit will sometimes trigger before the size has reached the limit. I assume the questioner wants the size to be able to reach the limit, but if that's not a requirement you could use a custom allocator that always throws ;-). Then since the capacity cannot exceed 0 that "ensures no operation adds beyond the maximum length", but I don't think that's intended to be acceptable... – Steve Jessop Jul 31 '15 at 17:22
  • @SteveJessop: Nice point (making my comments useless) –  Jul 31 '15 at 17:25
  • 2
    In `c++11` the header `` was added, which defines a container `std::array` with the exact functionality of `std::vector`, only you specify its exact length using the template parameter `N`. If the max size you want isn't very large then the fact that you always allocate max memory space doesn't hurt too much. If you want to still keep track of how much you've actually used, then unless your `T` has a `NULL` version, this won't be of much use. – Arthur Jul 31 '15 at 21:55
  • Inheritance and composition are the two main design forces. Use them wisely. – vz0 Nov 01 '16 at 12:36

3 Answers3

13

Are you sure that the vector itself can't grow, or that merely the consumers of such a vector need to limit the size of the arguments? If it's the latter, then simply assert(arg.size() <= MAX_LENGTH) where needed, document it, and be done. Otherwise, read on.

A std::vector can have unlimited size. If you limit that size, it's not a std::vector anymore. So, you cannot publicly derive from std::vector and limit the size without breaking the Liskov Substitution Principle. The derived class is still a vector, but doesn't act as one, and can't be used as one, and such an interface will thoroughly confuse your users, and the compiler will not catch serious usage bugs that will ensue. It's a bad idea.

The best you can do is to privately derive from vector, or have-a vector as a member, and expose all of the vector's interfaces while enforcing the size. Such a vector must not be convertible to std::vector, although obviously you can allow it to be copied or moved to a std::vector. It'll still perform just as well as a vector would, will still allow access via iterators, etc.

We're talking of a very small class, and its implementation simply has to follow the standard (or at least the cpp reference), you're leaving all the real work to the private std::vector. So that's not clunky, that's the only sane way to do it.

Community
  • 1
  • 1
Kuba hasn't forgotten Monica
  • 95,931
  • 16
  • 151
  • 313
  • I take your point. I like this idea of assert(arg.size() <=MAX_LENGTH) but where would this go if not in a custom wrapper class? I can't force clients to put them in front of every call, so is there a way to automatically do so? – helloB Jul 31 '15 at 16:36
  • you wouldn't use an assert if you wanted to raise a specific exception, you would use it to crash your program because you have made a mistake – Grady Player Jul 31 '15 at 16:38
  • @helloB The clients definitely can put them in if they truly can't accept a vector too large. That's what asserts are for. Otherwise, it'd seem you're making up a problem. The vector doesn't care about its size, now the clients don't care either, so why the question? If the clients care, they have to check or only accept a limited-size vector class, not `std::vector`. If the clients don't care, why do you? – Kuba hasn't forgotten Monica Jul 31 '15 at 16:48
  • 1
    @KubaOber the clients care but can be forgetful. – helloB Jul 31 '15 at 16:51
  • It's a client problem then. There are ways of dealing it at the client end that can be enforced through the api, but that doesn't imply a non-growing `std::vector`, just a convertible wrapper that checks the size when it's constructed. – Kuba hasn't forgotten Monica Jul 31 '15 at 17:53
2

Since C++11, custom allocators are permitted to have state (previous to C++11, custom allocators had to be stateless). Each C++ container that takes a custom allocator stores an instance of it.

Your allocator can then detect whether or not it has already fulfilled a request for the maximum allotment, and throw otherwise.

jxh
  • 69,070
  • 8
  • 110
  • 193
  • This only works if I have an individual allocator instance for each vector no? Or I'd have to have quite a lot of state recorded in the allocator, tracking each vector it had allocated. – helloB Jul 31 '15 at 16:44
  • @helloB: Yes. Each vector has its own instance of the allocator (second sentence of first paragraph). – jxh Jul 31 '15 at 16:45
  • That's not necessarily the case. I have seen allocators shared among containers. – helloB Jul 31 '15 at 16:53
  • @helloB: Use allocate traits to control what happens with the allocator when the container gets copied. See: http://en.cppreference.com/w/cpp/memory/allocator – jxh Jul 31 '15 at 16:56
  • A stateless allocator is fine, too. The limitation is capacity (allocation) <= MAX_LENGTH (A vector is no list) –  Jul 31 '15 at 16:58
  • @jxh Maybe my fault: Thinking MAX_LENGTH is a constant –  Jul 31 '15 at 17:02
  • 1
    Even if `MAX_LENGTH` is a constant, the *first* time that the vector tries to allocate `MAX_LENGTH` or more will typically be at a point where the size of the vector is some factor smaller than `MAX_LENGTH`, because vectors over-allocate in order to have amortized constant-time append. Thowing here would be over-zealous, it would limit the vector to less than the specified max size. By the *second* over-size allocation, the vector has grown to its capacity, which typically is more than `MAX_LENGTH`. So I don't think this works, but maybe I've missed the point. – Steve Jessop Jul 31 '15 at 17:16
  • I think you'd need to do something with the allocator's `construct()` function: compare the address passed in to the address of element 0 of the vector, and deduce the size that way. – Steve Jessop Jul 31 '15 at 17:20
  • @SteveJessop: Yes, I think the asker really wants a wrapper around a dynamically created `std::array`. – jxh Jul 31 '15 at 17:22
2
#include <vector>
#include <string>
using namespace std;

template <typename T, typename A>

void add_or_throw(std::vector<T,A> &vec, int max, T value)
{
    if (vec.size() < max)
    {
        vec.push_back(value);
    }else{
        throw length_error("vecor too beaucoup");
    }
}

int main() {
    std::vector<std::string> v;
    add_or_throw(v, 2, string("hi"));
    add_or_throw(v, 2, string("there"));
    add_or_throw(v, 2, string("man!"));

    return 0;
}
Grady Player
  • 14,399
  • 2
  • 48
  • 76