Skip to content

Vectors

This small vector implementation includes:

  • Inline allocation for small vectors
  • Custom expected size
  • Special treatment of relocatable types
    • Relocatable types can be moved with memcpy, bypassing destructors and constructors.
    • Relocatable types are defined by default for POD types and aggregate types of PODs
    • The small::is_relocatable traits can be used as an extension point for custom types
  • Better growth factors
  • Consider the cache line size in allocations
  • Heap allocations can be disabled with small::max_size_vector

When there are fewer elements than a given threshold, the elements are kept in a stack buffer for small vectors. Otherwise, the vector works as usual. However, if you are 100% sure you will never need more than N elements, you can use a max_size_vector, where elements are always inline.

The default number of elements in a small vector is usually the number of elements we can already fit inline in a vector. For larger data types, the default_inline_storage trait can be used as an extension point where one can define how many elements a small vector of that type should contain by default. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//
// Copyright (c) 2022 alandefreitas (alandefreitas@gmail.com)
//
// Distributed under the Boost Software License, Version 1.0.
// https://www.boost.org/LICENSE_1_0.txt
//

#include <small/vector.hpp>
#include <iostream>

// A relocatable custom type whose default inline storage should be at least 10
// elements
struct my_type
{
    int a;
    double b;
};

namespace small {
    template <>
    struct is_relocatable<my_type> : std::true_type
    {};
    template <>
    struct default_inline_storage<my_type> : std::integral_constant<size_t, 10>
    {};
} // namespace small

int
main() {
    // Inline storage for at least 5 elements
    small::vector<my_type, 5> v1 = {
        {1, 1.1},
        {2, 2.2},
        {3, 3.3},
        {4, 4.4},
        {5, 5.5}
    };
    for (const auto &x: v1) {
        std::cout << '<' << x.a << ',' << x.b << '>' << ' ';
    }
    std::cout << "\n"; // <1,1.1> <2,2.2> <3,3.3> <4,4.4> <5,5.5>

    // Default inline storage for at least 10 elements
    small::vector<my_type> v2 = {
        {1, 1.1},
        {2, 2.2},
        {3, 3.3},
        {4, 4.4},
        {5, 5.5}
    };
    for (const auto &x: v2) {
        std::cout << '<' << x.a << ',' << x.b << '>' << ' ';
    }
    std::cout << "\n"; // <1,1.1> <2,2.2> <3,3.3> <4,4.4> <5,5.5>

    return 0;
}

When there's a reasonable default for the number of inline elements, this strategy avoids multiple vector type instantiations for different inline storage sizes.

This small vector implementation used folly, abseil, and LLVM as a reference.