我一直在尝试查看在拥有许多小数据向量时是否可以优化案例。在我的用例中，这些向量可能有 100,000 多个，因此向量存储的大小至关重要。每个有时可能只有 1 或 2 个元素，但在许多情况下可能会增长更大的容量。
我曾尝试使用简单的 std::vector ，但这非常慢，因为它在堆上分配 N 个小缓冲区，这会浪费内存并且在时间关键型环境中花费的时间太长。实际上，向量上的小缓冲区优化 (SBO) 似乎是一个可行的解决方案。这意味着使用向量的内部（即堆栈）数据，直到超过它，然后才需要使用堆。
我偶然发现了似乎正是这样做的 LLVM SmallVector。然而，它似乎在 LLVM 框架中有很多依赖项，并且想知道在 Boost 中是否有类似的东西？Boost 实现可能会执行 SBO 优化，但我在搜索中找不到对此的任何引用。我已经看到，尽管由于一些关于迭代器的规则，STL 实现在技术上是禁止进行这种优化的？
链接：LLVM SmallVector在 LLVM 软件的内部源代码中。
Boost v1.58 （2015 年 4 月）的Container库有实验容器：small_vector
small_vector是一个类似矢量的容器，针对包含少量元素的情况进行了优化。它包含一些就地预分配的元素，这允许它在实际元素数量低于预分配阈值时避免使用动态存储分配。small_vector灵感来自 LLVM 的SmallVector容器。与 不同static_vector的是，small_vector 的容量可以增长到超出初始预分配容量。
small_vector<T, N, Allocator>可转换为small_vector_base<T, Allocator>，一种独立于预分配元素计数的类型，允许不需要在该N参数上模板化的客户端代码。small_vector 继承了所有 vector 的成员函数，因此它支持所有标准功能，如 emplacement、有状态分配器等。
您可能还对Electronic Arts 标准模板库中的一些容器感兴趣。
Github 上有一个存储库（看看固定大小的容器eastl::vector_*，它们类似于 LLVM 的 SmallVector）。
有了 Qt，就有了QVarLengthArray课程。
首先，您当然可以提取 LLVM 的 SmallVector，它具有相当少量的依赖项和自由许可证。据我所知，没有与 SmallVector 直接等效的 STL/Boost。Folly 中有一个小的矢量类（https://github.com/facebook/folly）
我为它创建了一张票作为功能请求：票#9165（https://svn.boost.org/trac/boost/ticket/9165）
可能可以用某种封装了 normal 的适配器/代理类来实现std::vector，并且可能std::array用于正常的“小向量”操作。只需在翻译索引时使用与 eg 相同的接口就std::vector足够了。最大的问题是迭代器，但这可能可以通过封装封装集合的迭代器来解决。
但是，将它们拼接在一起需要做很多工作，因此只需封装一个std::vector预先分配的内存可能会更简单。然后在push_backetc. 函数中检查添加的项目是否在预分配的内存中，只需将项目设置在正确的位置而不是调用向量push_back。
我设计了自己的带有移动语义的 SmallVector 版本。我试图保持简单。它不会尝试异常安全。我还使用无符号整数进行索引，因为我更喜欢它们而不是有符号整数。这是代码
#pragma once
#include <new>
#include <type_traits>
#include <initializer_list>
#include <utility>
#include <cstddef>
#include <cstdint>
#include <climits>
#include <cstdlib>
typedef std::ptrdiff_t integer;
typedef std::size_t uinteger;
const integer integer_max{ PTRDIFF_MAX };
#ifdef NDEBUG
#define IL_ASSERT(condition) \
((void) 0)
#else
#define IL_ASSERT(condition) \
(condition) ? (void) 0 : abort()
#endif
// This class is a vector class that has small sized optimization and does not
// attempt to be exception safe.
// - data_ always point to the beginning of the vector. It points to some
// memory on the heap when small size optimization is not used and points
// to data_small_ when small size optimization is used.
// - Objects on data_small_ are never destructed but are reinitialized to T{ }
// when not used anymore. Objects on the heap are desctucted when the are not
// plain old data and not used anymore.
// - The capacity of the vector is always >= than small_size wether small size
// optimization is in use (in this case the capacity is equal to small_size)
// or not.
//
// The class has been specialized for small_size = 0.
namespace il {
template <typename T, integer small_size = 0>
class SmallVector {
static_assert(small_size >= 0,
"il::SmallVector must have a non-negative small size");
private:
#ifndef NDEBUG
integer debug_size_;
integer debug_capacity_;
bool debug_is_data_small_used_;
#endif
T* data_;
T* size_;
T* capacity_;
T data_small_[small_size > 0 ? small_size : 1];
private:
bool is_data_small_used() const {
return data_ == data_small_;
}
public:
SmallVector() {
#ifndef NDEBUG
debug_size_ = 0;
debug_capacity_ = 0;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_small_;
capacity_ = data_small_ + small_size;
}
SmallVector(integer n) {
IL_ASSERT(n >= 0);
#ifndef NDEBUG
debug_size_ = n;
#endif
if (n <= small_size) {
#ifndef NDEBUG
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_ + n;
capacity_ = data_ + small_size;
} else {
#ifndef NDEBUG
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
data_ = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
size_ = data_ + n;
capacity_ = size_;
if (!std::is_pod<T>::value) {
for (integer k = 0; k < n; ++k) {
new (data_ + k) T{};
}
}
}
}
SmallVector(integer n, const T& x) {
IL_ASSERT(n >= 0);
#ifndef NDEBUG
debug_size_ = n;
#endif
if (n <= small_size) {
#ifndef NDEBUG
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_ + n;
capacity_ = data_ + small_size;
for (integer k = 0; k < n; ++k) {
data_[k] = x;
}
} else {
#ifndef NDEBUG
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
data_ = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
size_ = data_ + n;
capacity_ = size_;
for (integer k = 0; k < n; ++k) {
new (data_ + k) T{ x };
}
}
}
SmallVector(std::initializer_list<T> list) {
integer n{ static_cast<integer>(list.size()) };
#ifndef NDEBUG
debug_size_ = n;
#endif
if (n <= small_size) {
#ifndef NDEBUG
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_ + n;
capacity_ = data_ + small_size;
for (integer k = 0; k < n; ++k) {
data_[k] = *(list.begin() + k);
}
} else {
#ifndef NDEBUG
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
data_ = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
size_ = data_ + n;
capacity_ = size_;
for (integer k = 0; k < n; ++k) {
new (data_ + k) T{ *(list.begin() + k) };
}
}
}
SmallVector(const SmallVector<T, small_size>& A) {
integer n{ A.size() };
#ifndef NDEBUG
debug_size_ = n;
#endif
if (n <= small_size) {
#ifndef NDEBUG
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_ + n;
capacity_ = data_ + small_size;
for (integer k = 0; k < n; ++k) {
data_[k] = A.data_[k];
}
} else {
#ifndef NDEBUG
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
data_ = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
size_ = data_ + n;
capacity_ = size_;
for (integer k = 0; k < n; ++k) {
new (data_ + k) T{ A.data_[k] };
}
}
}
SmallVector(SmallVector<T, small_size>&& A) {
integer n{ A.size() };
#ifndef NDEBUG
debug_size_ = n;
#endif
if (n <= small_size) {
#ifndef NDEBUG
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_ + n;
capacity_ = data_ + small_size;
for (integer k = 0; k < n; ++k) {
data_[k] = std::move(A.data_[k]);
}
} else {
#ifndef NDEBUG
debug_capacity_ = A.debug_capacity_;
debug_is_data_small_used_ = false;
#endif
data_ = A.data_;
size_ = A.size_;
capacity_ = A.capacity_;
#ifndef NDEBUG
A.debug_size_ = 0;
A.debug_capacity_ = 0;
A.debug_is_data_small_used_ = false;
#endif
A.data_ = data_small_;
A.size_ = data_small_;
A.capacity_ = data_small_ + small_size;
}
}
SmallVector& operator=(const SmallVector<T, small_size>& A) {
if (this != &A) {
integer n{ A.size() };
bool needs_memory{ capacity() < n };
if (needs_memory) {
#ifndef NDEBUG
debug_size_ = n;
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
data_ = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
size_ = data_ + n;
capacity_ = size_;
for (integer k = 0; k < n; ++k) {
new (data_ + k) T{ A.data_[k] };
}
} else {
if (!std::is_pod<T>::value) {
if (is_data_small_used()) {
for (integer k = size() - 1; k >=n ; --k) {
*(data_ + k) = T{ };
}
} else {
for (integer k = size() - 1; k >= n; --k) {
(data_ + k)->~T();
}
}
}
#ifndef NDEBUG
debug_size_ = n;
#endif
size_ = data_ + n;
for (integer k = 0; k < n; ++k) {
data_[k] = A.data_[k];
}
}
}
return *this;
}
SmallVector& operator=(SmallVector<T, small_size>&& A) {
if (this != &A) {
integer n{ A.size() };
if (n <= small_size) {
if (!is_data_small_used()) {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
#ifndef NDEBUG
debug_size_ = n;
debug_capacity_ = small_size;
debug_is_data_small_used_ = true;
#endif
data_ = data_small_;
size_ = data_small_ + n;
capacity_ = data_small_ + small_size;
for (integer k = 0; k < n; ++k) {
data_[k] = std::move(A.data_[k]);
}
} else {
if (is_data_small_used()) {
for (integer k = 0; k < small_size; ++k) {
data_[k] = T{ };
}
} else {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
#ifndef NDEBUG
debug_size_ = A.debug_size_;
debug_capacity_ = A.debug_capacity_;
debug_is_data_small_used_ = false;
#endif
data_ = A.data_;
size_ = A.size_;
capacity_ = A.capacity_;
#ifndef NDEBUG
A.debug_size_ = 0;
A.debug_capacity_ = 0;
A.debug_is_data_small_used_ = true;
#endif
A.data_ = A.data_small_;
A.size_ = A.data_small_;
A.capacity_ = A.data_small_ + small_size;
}
}
return *this;
}
~SmallVector() {
if (!is_data_small_used()) {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
}
const T& operator[](integer k) const {
IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
return data_[k];
}
T& operator[](integer k) {
IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
return data_[k];
}
const T& operator()(integer k) const {
IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
return data_[k];
}
T& operator()(integer k) {
IL_ASSERT(static_cast<uinteger>(k) < static_cast<uinteger>(size()));
return data_[k];
}
T* data() {
return data_;
}
const T* data() const {
return data_;
}
const T* begin() const {
return data_;
}
const T* end() const {
return size_;
}
integer size() const {
return static_cast<integer>(size_ - data_);
}
integer capacity() const {
return static_cast<integer>(capacity_ - data_);
}
integer max_size() const {
return integer_max;
}
bool empty() const {
return size_ == data_;
}
void resize(integer n) {
IL_ASSERT(n >= 0);
if (n <= capacity()) {
#ifndef NDEBUG
debug_size_ = n;
#endif
if (is_data_small_used()) {
if (!std::is_pod<T>::value) {
if (n < size()) {
for (integer k = size() - 1; k >= n ; --k) {
data_[k] = T{ };
}
} else {
for (integer k = size(); k < n ; ++k) {
data_[k] = T{ };
}
}
};
} else {
if (!std::is_pod<T>::value) {
if (n < size()) {
for (integer k = size() - 1; k >= n; ++k) {
(data_ + k)->~T();
}
} else {
for (integer k = size(); k < n; ++k) {
new (data_ + k) T{ };
}
}
}
}
size_ = data_ + n;
} else {
#ifndef NDEBUG
debug_size_ = n;
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
integer n_old{ size() };
T* new_data = static_cast<T*>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
for (integer k = 0; k < n_old; ++k) {
new (new_data + k) T{ std::move(data_[k]) };
}
if (is_data_small_used()) {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
data_[k] = T{ };
};
}
} else {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
data_ = new_data;
size_ = data_ + n;
capacity_ = size_;
}
}
void reserve(integer p) {
IL_ASSERT(p >= 0);
if (p > capacity()) {
#ifndef NDEBUG
debug_capacity_ = p;
debug_is_data_small_used_ = false;
#endif
integer n_old{ size() };
T *new_data = static_cast<T *>(::operator new(
static_cast<std::size_t>(p) * sizeof(T)));
for (integer k = 0; k < n_old; ++k) {
new (new_data + k) T{ std::move(data_[k]) };
}
if (is_data_small_used()) {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
data_[k] = T{ };
};
}
} else {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
for (integer k = n_old; k < p; ++k) {
new (new_data + k) T{ };
}
data_ = new_data;
size_ = data_ + n_old;
capacity_ = data_ + p;
}
}
void push_back(const T& x) {
if (size_ == capacity_) {
integer n_old{ size() };
integer n{ n_old > 1 ? (3 * n_old) / 2 : n_old + 1 };
T *new_data = static_cast<T *>(::operator new(
static_cast<std::size_t>(n) * sizeof(T)));
for (integer k = 0; k < n_old; ++k) {
new (new_data + k) T{ std::move(data_[k]) };
}
if (is_data_small_used()) {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
data_[k] = T{ };
};
}
} else {
if (!std::is_pod<T>::value) {
for (integer k = size() - 1; k >= 0; --k) {
(data_ + k)->~T();
}
}
::operator delete(data_);
}
data_ = new_data;
#ifndef NDEBUG
debug_capacity_ = n;
debug_is_data_small_used_ = false;
#endif
capacity_ = data_ + n;
}
#ifndef NDEBUG
++debug_size_;
#endif
if (is_data_small_used()) {
*size_ = x;
} else {
new (size_) T{ x };
}
++size_;
}
};
}
我在这里找到了一个版本：https ://github.com/thelink2012/SmallVector 没有 LLVM 依赖项。