Is it unefficient to use a std::vector when it only contains two elements?

Question

I am building a C++ class A that needs to contain a bunch of pointers to other objects B.

In order to make the class as general as possible, I am using a std::vector<B*> inside this class. This way any number of different B can be held in A (there are no restrictions on how many there can be).

Now this might be a bit of overkill because most of the time, I will be using objects of type A that only hold either 2 or 4 B*'s in the vector.

Since there is going to be a lot of iterative calculations going on, involving objects of class A, I was wondering if there is a lot of overhead involved in using a vector of B's when there are only two B's needed.

Should I overload the class to use another container when there are less than 3 B present?

to make things clearer: A are multipoles and B are magnetic coils, that constitute the multipoles

Answer 1

Premature optimization. Get it working first. If you profile your application and see that you need more efficiency (in memory or performance), then you can change it. Otherwise, it's a potential waste of time.

Answer 2

If you need an array of B* that will never change its size, you won't need the dynamic shrinking and growing abilities of the std::vector.

So, probably not for reasons of efficiency, but for reasons of intuition, you could consider using a fixed length array:

struct A {
  enum { ndims = 2 };
  B* b[ndims];
};

or std::array (if available):

struct A {
  std::array<B*, 2> b;
};

see also this answer on that topic.

Answer 3

I would use a vector for now, but typedef a name for it instead of spelling std::vector out directly where it's used:

typedef std::vector vec_type;

class A {
    vec_type<B*> whatever;
};

Then, when/if it becomes a problem, you can change that typedef name to refer to a vector-like class that's optimized for a small number of contained objects (e.g., does something like the small-string optimization that's common with many implementations of std::string).

Another possibility (though I don't like it quite as well) is to continue to use the name "vector" directly, but use a using declaration to specify what vector to use:

class A {
    using std::vector;

    vector<B*> whatever;
};

In this case, when/if necessary, you put your replacement vector into a namespace, and change the using declaration to point to that instead:

class A {
    using my_optimized_version::vector;

    // the rest of the code remains unchanged:
    vector<B*> whatever;
};

As far as how to implement the optimized class, the typical way is something like this:

template <class T>
class pseudo_vector { 
    T small_data[5];
    T *data;
    size_t size;
    size_t allocated;
public:
// ...
};

Then, if you have 5 or fewer items to store, you put them in small_data. When/if your vector contains more items than that fixed limit, you allocate space on the heap, and use data to point to it.

Depending a bit on what you're trying to optimize, you may want to use an abstract base class, with two descendants, one for small vectors and the other for large vectors, with a pimpl-like class to wrap them and make either one act like something you can use directly.

Yet another possibility that can be useful for some situations is to continue to use std::vector, but provide a custom Allocator object for it to use when obtaining storage space. Googling for "small object allocator" should turn up a number of candidates that have already been written. Depending on the situation, you may want to use one of those directly, or you may want to use them as inspiration to write your own.

Answer 4

Vectors are pretty lean as far as overhead goes. I'm sure someone here can give more detailed information about what that really means. But if you've got performance issues, they're not going to come from vector.

In addition I'd definitely avoid the tactic of using different containers depending on how many items there are. That's just begging for a disaster and won't really give you anything in return.