ChunkVector
The ChunkVector class template provides a chunk-contiguous 1D vector intended for very large vectors in a possibly fragmented memory environment. The basic characteristics of ChunkVector include:
- The data is stored in a sequence of Chunk arrays. Since the data is non-contiguous you cannot access elements by incremented pointers.
- The chunk size is a power of 2 for efficient look-up: the exponent is specified by the user.
- Element access has the constant-time lookup speed of std::vector.
- ChunkVector is similar to std::deque but much faster.
- Index-based subscripting but not iterator access is provided.
- 0-based subscripting is provided by the [] operator, as in v[ i ].
- 1-based subscripting is provided by the () operator, as in v( i ).
- Subscripting does bounds checking in debug builds.
- Efficient dynamic size changing operations are provided.
- Array size and indexing types are std::size_t so very large arrays are supported on 64-bit platforms where std::size_t is a 64-bit unsigned integer.
Shorthand (typedef) names are provided for the common value types in the ChunkVector.fwd.hh header so, for example, we use ChunkVector_int instead of ChunkVector< int > on this page.
Construction
ChunkVectors are created in a straightforward fashion:
// ChunkVector with n elements
ChunkVector_int v( n, p ); // Chunk size is 2^p // Built-in types are uninitialized
ChunkVector_int w( n, p, 0 ); // Initialize elements to 0 |
The first constructor shown does not initialize the elements of built-in types such as int and float, for efficiency when constructing very large arrays that will be initialized after construction.
ChunkVectors can be constructed from std::vectors:
std::vector s;
...
ChunkVector_int v( s, p ); // Chunk size is 2^p |
and from an iterator range:
ChunkVector_int v( s.begin(), s.end(), p ); // Chunk size is 2^p |
ChunkVectors can also be default constructed and later sized:
ChunkVector_int v;
...
v.resize( n, p ); // Now size and allocate it |
ChunkVectors can also be copy constructed from any ChunkVector with assignment-compatible values:
ChunkVector_int v( n, p );
...
ChunkVector_double z( v );
|
Subscripting
ChunkVector elements can be accessed by 0-based or 1-based index:
ChunkVector_int v( n, p );
...
int i = v[ 0 ]; // First element
int j = v( 1 ); // First element |
Although the internal element access must compute a two-index lookup for each element the power-of-2 chunk sizing allows fast bit shift and mask operations to be used so there is very little performance difference from that of std::vector subscripting.
Subscripting accesses to a ChunkVector's elements are bounds-checked via assertions in a debug build.
Front and Back Elements
The first and last elements of a ChunkVector elements can be read or write accessed with the STL-compatible front and back functions:
ChunkVector_int v( n, p );
...
j = v.front(); // First element
v.back() = k; // Last element |
Assignment
ChunkVectors support assignment of any ChunkVector or std::vector with assignment-compatible values using the operators { =, +=, -= }:
ChunkVector_int v( n, p );
ChunkVector_double z( n, p );
... z = v;
...
z += v; |
and assignment of any assignment-compatible value with the operators { =, +=, -=, *=, /= }:
ChunkVector_int v( n, p );
... v = 123; // All elements set to 123
v += 4.2; // Now all elements are 127 |
Additional assignment functions are available for assigning a std::vector and setting the Chunk size:
ChunkVector_int v;
std::vector s;
...
v.assign( s, p ); |
or for assigning from an iterator range:
v.assign( s.begin(), s.end() ); |
or assigning a specified number of uniform-value elements:
v.assign( 1000, 123 ); // 1000 elements with value 123 |
Comparison
ChunkVectors can be compared with ChunkVector, std::vector, and uniform value objects using using the operators { ==, !=, <, <=, >=, > }.
Resizing
ChunkVectors can be efficiently grown and resized with a number of functions: push_back, pop_back, resize, reshape, append, and shrink. For efficiency when the resizing operation doesn't need to preserve the current values there are non_preserving_resize and non_preserving_reshape functions. The shrink function will remove any excess capacity in the last Chunk (the swap function can also be used in the common shrink-to-fit idiom but the shrink function does it more efficiently).
Special Functions
ChunkVectors can be reset to a default-constructed state that releases their memory with the clear member function. ChunkVectors have length and length_squared member functions to compute their L2 length and squared length and the normalize function to normalize the array to unit length. The dot_product function computes the dot (inner) product of two ChunkVectors. The distance and distance_squared functions compute the L2 distance and squared distance between two ChunkVectors.
Debugging
For performance, ChunkVector doesn't check for bounds errors in release builds (when NDEBUG is defined). It is therefore important to test assertion-enabled debug builds of code using ChunkVectors.
Output
A stream input and output operators are provided.
|