Re:Data Structures Part 3: Arrays of Arrays
by bullen on Tuesday October 01, 2019 @03:16AM
(#21122782)
What is the difference between this "small" vector and a vector?
[ Parent
| on HN ]
Re:Data Structures Part 3: Arrays of Arrays
by PixelOfDeath on Tuesday October 01, 2019 @05:08AM
(#21123428)
The small vector class contains a static array of a few bytes. And as long as your data fits in it, no extra heap allocation is needed. A vector always does heap allocation, even if you only use a few bytes.
Re:Data Structures Part 3: Arrays of Arrays
by bullen on Tuesday October 01, 2019 @08:05AM
(#21124371)
Ok, thx!
If I use the trick Niklas calls “array with holes” in part 1, will each hole larger than the cache frame result in a cache miss?
Re:Data Structures Part 3: Arrays of Arrays
by Vogtinator on Tuesday October 01, 2019 @07:15AM
(#21124101)
Sounds like small string optimization (SSO), which is common in C++.
Re:Data Structures Part 3: Arrays of Arrays
by QuadDamaged on Tuesday October 01, 2019 @04:51AM
(#21123345)
`SmallVec` allocates a contiguous array in the struct holding the vector itself (so it can be located on the stack), then if the capacity is insufficent, fallbacks to a heap-allocated `Vec` equivalent.
The `Vec` struct contains the capacity and used length integers, as well as a pointer to the heap-allocated storage.