Updates:
2025-07-15 - Fixed build error when using the clear() method
2025-07-15 - Fixed pop_back method.
Hello. This small article is dedicated to the StaticVector class, with similar std::vector
The main distinguishing feature of this class is that it stores can store data in the inner fields of the object, if the volume of data does not fit in the inner fields of the class, then the memory is allocated in a heap. This approach allows you to reduce the execution time on the allocated of memory.
If the memory is allocated in the heap of the size of the block of the allocated block is determined by the following rules:
This blog is conducted with two purposes so that the written things were beneficial and was not boring. Therefore, I also apply the video how the development of this class took place.
Attention: After this video, the OffsetSize parameter was added to the class template and additional changes were made during optimization.
Description of the degree function
That is, in the case of memory of memory in a heap, we distinguish memory with a reserve. The size of the buffer in this case is determined by the degree function of the degree N.
This power function can be set as a linear increase
OffsetSize = 0;
StepSize = 16;
StepModule = 1;
N BufferSize
0 8
1 16
2 24
3 32
and increase in power mode
OffsetSize = 0;
StepSize = 2;
StepModule = 2
N BufferSize
0 2
1 6
2 14
3 30
Using this function, you can get the result equivalent to 2^N by setting the OffsetSize parameter, equal to 2.
OffsetSize = 2;
StepSize = 2;
StepModule = 2
N BufferSize
0 4
1 8
2 16
3 32
Description of a fixed increase function
For superly large values, the size of the buffer can be calculated according to the second function, which has a fixed increase in the size of the buffer when calculating the next step and is used if the resulting sizes of the buffer exceeds the value of MaxPow
MaxPowStepSize step size is determined as the difference in the steppe function of the following after the MaxPow and its previous value.
F(Laststep) - F(Laststep -1)
And MaxPowStart is the first value of the degree function that follows the MaxPow parameter.
A brief description of the class
The class template has the following view:
template <
typename Ty,
unsigned int StaticSize=16,
unsigned int OffsetSize=2,
unsigned int StepSize=2,
unsigned int StepModuleInt=2,
unsigned int StepModuleFrac=0,
unsigned int MaxPow=0>
class StaticVector;
Description of the parameters of the template
typename Ty - Type of stored elements
unsigned int StaticSize - Maximum number of elements stored in the internal buffer
unsigned int OffsetSize - The offset size used in the calculation function
unsigned int StepSize - The step size used in the calculation function
unsigned int StepModuleInt - The integer part of the StepModule parameter used in the calculation function
unsigned int StepModuleFrac - Fractional part of the StepModule parameter number used in the calculation function
unsigned int MaxPow - The limit value after which the buffer size calculation goes into linear form and a simple increment is performed. If the value is 0, but this functionality is not used
The class itself in use is similar to std::vector. It has iterators, access element by index and the push_back() and pop_back() operation
fcf::StaticVector<int, 32> v;
for(int j = 0; j < a_vecSize; ++j) {
v.push_back(j);
}
for(auto it = v.begin(); it = v.end(); ++it) {
std::cout << *it << std::endl;
}
The speed of execution
And most importantly. Comparison with the speed of std::vector.
Comparison of push_back operations and creating a container with a given value.
Launching on Linux (GCC)
Speed compare StaticVector with std::vector...
Number of iterations: 1024
StaticSize parameter: 64
StaticVector std::vector std::vector/StaticVector
Push back test (1 items): 3 24 8
Push back test (4 items): 8 83 10.375
Push back test (8 items): 11 115 10.4545
Push back test (16 items): 18 145 8.05556
Push back test (64 items): 70 226 3.22857
Push back test (256 items): 345 450 1.30435
Push back test (1024 items): 1305 1191 0.912644
Push back test (32768 items): 98878 105334 1.06529
Push back test (131072 items): 438563 430047 0.980582
Initialize test(1 items): 8 13 1.625
Initialize test(4 items): 7 31 4.42857
Initialize test(8 items): 8 18 2.25
Initialize test(16 items): 9 19 2.11111
Initialize test(64 items): 13 27 2.07692
Initialize test(256 items): 68 76 1.11765
Initialize test(1024 items): 210 249 1.18571
Initialize test(32768 items): 8371 8750 1.04528
Initialize test(131072 items): 46040 45214 0.982059
Launching on Windows (Visual Studio 2022)
Speed compare StaticVector with std::vector...
Number of iterations: 1024
StaticSize parameter: 64
StaticVector std::vector std::vector/StaticVector
Push back test (1 items): 2 77 38.5
Push back test (4 items): 7 342 48.8571
Push back test (8 items): 12 495 41.25
Push back test (16 items): 23 664 28.8696
Push back test (64 items): 123 1542 12.5366
Push back test (256 items): 1044 2533 2.42625
Push back test (1024 items): 3544 3548 1.00113
Push back test (32768 items): 105358 201082 1.90856
Push back test (131072 items): 421519 480350 1.13957
Initialize test(1 items): 12 71 5.91667
Initialize test(4 items): 13 70 5.38462
Initialize test(8 items): 16 73 4.5625
Initialize test(16 items): 26 80 3.07692
Initialize test(64 items): 22 87 3.95455
Initialize test(256 items): 136 120 0.882353
Initialize test(1024 items): 347 474 1.36599
Initialize test(32768 items): 10175 10527 1.03459
Initialize test(131072 items): 52172 47994 0.919919
The first and second column is the time of the test, and the third is the ratio of the second column to the first
As can be seen from the results with a small volume of StaticVector has a significant increase in performance, but it all depends on the platform
You can download a separate class from the repository to github: https://github.com/fcf-framework/short-fcfcpp-StaticVector
Top comments (0)