std::vector-like class optimized to hold a small number of items [duplicate]

Question

In one time-critical part of the program there is a member of the class that looks like that: std::vector m_vLinks; During profiling I noticed that about 99.98% of executions this vector holds only 0 or 1 items. However in very rarely cases it might hold more. This vector is definitely a bottleneck according to profiler, so I'm thinking about following optimization:

1. Craft a hand-made class with vector-like interface
2. This class will hold true size, one item and optional pointer to the vector
3. In this case when vector holds 1 item there won't be any dynamic memory allocations, and also accessing this item will be (a bit) faster due to removing of one indirection.
4. When we need to hold more data vector is dynamically allocated
5. Of course this vector won't provide one memory block holding all items (not needed here), and also some operations will be more complex

Before starting to prototype this thing to see if it helps, I wonder if anyone encountered custom containers with similar functionality in some 3rd-party libraries?

I already thought about boost::array, but don't want size limit that it imposes

Answer 1

LLVM has a class for that called SmallVector.

Answer 2

In a non-time-critical part of your code, perform: m_vLinks.reserve(1);. That way, in the time-critical part, there will typically be no dynamic allocation.