vecarray

The vecarray container is so named because it can be thought of as a cross between a std::vector and a std::tr1::array.  Like std::vector it provides operations such as push_back(), insert(), pop_back() to alter the number of elements in the container whilst like std::tr1::array it provides a fixed memory footprint and fast access.

You specify a max-size for the vecarray via a template parameter which determines the maximum number of elements that can be added.  Unlike a std::vector which has to store a pointer to element memory (to support reallocation) and dereference that pointer each time an operation such as push_back() is called the memory for vecarray's elements is from an array which is a member of the vecarray itself.  Unlike a std::vector a vecarray (and its elements) can be placed easily on the stack allowing quick stack frame based element access.

You can download the implementation here (v3.0.1) (Changelog).

Unlike the standard containers you can copy/assign a vecarray from a vecarray with different template parameters so the following is legal:

    neolib::vecarray<int, 10> va1;
    va1.push_back(42);
    neolib::vecarray<int, 5> va2(va1); /* even though va2 is smaller than va1 va1 only contains one element so an overflow exception is not thrown */
    neolib::vecarray<float, 20> va3;
    va3 = va2; /* I am not sure if I should allow this, anyone? :) */

WARNING: By default buffer overflow prevention is enabled which causes the exception neolib::vecarray_overflow to be thrown when inserting an item when the vecarray is full.  If overflow is protected against elsewhere then you can disable this checking (and remove its small overhead) by instantiating the vecarray with a third parameter of neolib::nocheck (e.g. neolib::vecarray<int, 10, neolib::nocheck> va;)

UPDATE: Boost now contains a container very similar to vecarray called static_vector. Currently vecarray marginally outperforms static_vector in some tests (such as the one below); when static_vector outperforms vecarray in all tests vecarray can be retired.

Here is an example of usage:

int main()
{
    neolib::vecarray<int, 10> numbers;

    int v;
    while(!numbers.full() && std::cin >> v)
        numbers.push_back(v);

    std::cout << "The " << numbers.size() << " items you entered were: " <<
        std::endl;
    std::copy(numbers.begin(), numbers.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

A similar example this time illustrating the fact that an overflow exception is thrown when attempting to add an item when the vecarray is full:

int main()
{
    typedef neolib::vecarray<int, 10> numbers_t;
    numbers_t numbers;

    try
    {
        std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(),
            std::back_inserter<numbers_t>(numbers));
    }
    catch(neolib::vecarray_overflow) {}

    std::cout << "The " << numbers.size() << " items you entered were: " <<
        std::endl;
    std::copy(numbers.begin(), numbers.end(),
        std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;

    return 0;
}

Note: in this example if an overflow occurs the last number that was read from std::cin is lost.

An example which illustrates the possible performance gains of vecarray over std::vector:

struct timer
{
    timer(const char* message) 
    { 
        std::cout << message; 
        QueryPerformanceCounter(&iStartTime);
    }
    ~timer() 
    {
        LARGE_INTEGER endTime;
        QueryPerformanceCounter(&endTime);
        LARGE_INTEGER freq;
        QueryPerformanceFrequency(&freq);
        std::cout.precision(4);
        std::cout << std::fixed << (float)(endTime.QuadPart - iStartTime.QuadPart)/(float)freq.QuadPart << " seconds" << std::endl; 
    }
    LARGE_INTEGER iStartTime;
};

inline int quick_rand()
{
    static int result = 0;
    return( ((result = result * 214013L
        + 2531011L) >> 16) & 0x7fff );
}

int main()
{
    int optimizerBlackHole = 0;
    const int iterations = 400000;
    const int size = 10000;
    {
        timer time("std::vector (naive) push_back: ");
        for (int i = 0; i != iterations; i++)
        {
            std::vector<int> v;
            for (int i = 0; i != size; i++)
            {
                v.push_back(quick_rand());
            }
            optimizerBlackHole += v[quick_rand() % v.size()];
        }
    }
    {
        timer time("std::vector (reserved) push_back: ");
        for (int i = 0; i != iterations; i++)
        {
            std::vector<int> v;
            v.reserve(size);
            for (int i = 0; i != size; i++)
            {
                v.push_back(quick_rand());
            }
            optimizerBlackHole += v[quick_rand() % v.size()];
        }
    }
    {
        timer time("std::vector (reuse) push_back: ");
        std::vector<int> v;
        v.reserve(size);
        for (int i = 0; i != iterations; i++)
        {
            v.clear();
            for (int i = 0; i != size; i++)
            {
                v.push_back(quick_rand());
            }
            optimizerBlackHole += v[quick_rand() % v.size()];
        }
    }
    {
        timer time("boost::container::static_vector push_back: ");
        for (int i = 0; i != iterations; i++)
        {
            boost::container::static_vector<int, size> v;
            for (int i = 0; i != size; i++)
            {
                v.push_back(quick_rand());
            }
            optimizerBlackHole += v[quick_rand() % v.size()];
        }
    }
    {
        timer time("neolib::vecarray push_back: ");
        for (int i = 0; i != iterations; i++)
        {
            neolib::vecarray<int, size> v;
            for (int i = 0; i != size; i++)
            {
                v.push_back(quick_rand());
            }
            optimizerBlackHole += v[quick_rand() % v.size()];
        }
    }
    std::cout << std::string(' ', optimizerBlackHole % 2) << std::endl;;
}

The output of which is (compiled with VC++ 2008, optimized for speed, running on an Intel(R) Core(TM) i7-2720QM CPU):

std::vector (naive) push_back: 13.0613 seconds
std::vector (reserved) push_back: 9.2304 seconds
std::vector (reuse) push_back: 9.1129 seconds
boost::container::static_vector push_back: 8.5157 seconds
neolib::vecarray push_back: 8.4142 seconds


You can e-mail comments to the author.

Back to project page