两个指针替代 C++ std::vector
Two pointers alternative to C++ std::vector
通常 std::vector 对象大小为 24 字节，因为它被实现为 3 个指针（在 64 位 CPU 上每个指针大小为 8 字节）。这些指标是：
- 矢量开始
- 向量结束
- 向量保留内存结束（向量容量）
我们是否有任何类似的容器提供相同的接口（容量特性除外）但仅使用两个指针（或者可能是指针 + 大小值）实现？
它在某些情况下很有意义，比如我当前的项目。我在内存中保存了数百万个向量，但我不需要区分向量大小和容量，内存使用正在成为瓶颈。我考虑了几个选项：
std::string 实施可能很棘手，包括短字符串优化之类的东西，这可能更糟。std::unique_ptr 到一些分配的缓冲区。该接口不像 std::vector 那样方便，我最终会创建自己的 class 来包装指针加上缓冲区的大小，这是我试图避免的。
所以有现成的替代品吗？接受基于 Boost 库的解决方案。
I do not need to change its size after dynamic allocation (from the comments)
由于您不需要动态扩展向量，std::valarray<T> 可能是一个不错的选择。它的大小在构造时是固定的，所以实现不需要第三个指针。
这是将 unique_ptr<T[]> 封装在第一个 class 值类型中的绝对最小值，它模拟了 RandomAccessRange:
#include <memory>
template <typename T>
struct dyn_array {
explicit dyn_array(size_t n)
: _n(n), _data(std::make_unique<T[]>(n)) { }
auto begin() const { return _data.get(); }
auto end() const { return begin() + _n; }
auto begin() { return _data.get(); }
auto end() { return begin() + _n; }
auto size() const { return _n; }
private:
size_t _n {};
std::unique_ptr<T[]> _data;
};
那是 15 行代码。看看吧Live
int main() {
using std::begin;
using std::end;
for (int n; (n = size_gen(prng)) != 10;) {
dyn_array<double> data(n);
std::iota(begin(data), end(data), 0);
static_assert(sizeof(data) == 2*sizeof(void*));
fmt::print("Size {} data {}\n", n, data);
}
}
打印例如
Size 8 data {0, 1, 2, 3, 4, 5, 6, 7}
Size 6 data {0, 1, 2, 3, 4, 5}
Size 7 data {0, 1, 2, 3, 4, 5, 6}
Size 6 data {0, 1, 2, 3, 4, 5}
我评论了两个版本
奖励：单指针大小
在上面的基础上，我意识到大小可以在内部分配dyn_array 恰好1个指针[=61] =].
#include <memory>
#include <cstdlib> // committing the sin of malloc for optimization
template <typename T>
struct dyn_array {
dyn_array(std::initializer_list<T> init)
: _imp(allocate(init.size(), true))
{ std::uninitialized_move(init.begin(), init.end(), begin()); }
dyn_array(dyn_array const& rhs)
: _imp(allocate(rhs.size(), true))
{ std::uninitialized_copy(rhs.begin(), rhs.end(), begin()); }
dyn_array(dyn_array&& rhs) { rhs.swap(*this); }
dyn_array& operator=(dyn_array rhs) { rhs.swap(*this); }
explicit dyn_array(size_t n = 0)
: _imp(allocate(n))
{ }
auto size() const { return _imp? _imp->_n : 0ull; }
auto begin() const { return _imp? _imp->_data + 0 : nullptr; }
auto begin() { return _imp? _imp->_data + 0 : nullptr; }
auto end() const { return begin() + size(); }
auto end() { return begin() + size(); }
auto empty() const { return size() == 0; }
bool operator==(dyn_array const& rhs) const {
return size() == rhs.size() &&
std::equal(rhs.begin(), rhs.end(), begin());
};
void swap(dyn_array& rhs) {
std::swap(_imp, rhs._imp);
}
private:
struct Impl {
size_t _n;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
T _data[]; // C99 extension
#pragma GCC diagnostic pop
};
struct Deleter {
void operator()(Impl* s) const {
while (s->_n) { s->_data[--(s->_n)].~T(); }
std::free(s);
}
};
using Ptr = std::unique_ptr<Impl, Deleter>;
Ptr _imp;
static Ptr allocate(size_t n, bool uninitialized = false) {
if (!n)
return {};
auto p = std::malloc(sizeof(Impl) + n*sizeof(T)); // could be moreconservative
auto s = Ptr(reinterpret_cast<Impl*>(p));
s->_n = n;
if (!uninitialized)
std::uninitialized_default_construct_n(s->_data, n);
return s;
}
};
我们可以用作：
#include <fmt/ranges.h>
static size_t constructions = 0;
static size_t default_ctor, copy_ctor = 0;
static size_t destructions = 0;
struct Sensor final {
Sensor() { ++constructions; ++default_ctor; }
Sensor(Sensor const&) { ++constructions; ++copy_ctor; }
~Sensor() { ++destructions; }
};
int main() {
fmt::print("With initializers: {}, {}\n",
dyn_array{3.1415f},
dyn_array{"one", "two", "three"});
fmt::print("Without: {}, {}\n",
dyn_array<std::string_view>{3},
dyn_array<float>{1},
dyn_array<int>{}); // empty by default, no allocation
auto a = dyn_array{3,2,1};
fmt::print("sizeof(a) == sizeof(void*)? {}\n", sizeof(a) == sizeof(void*));
auto copy = a;
fmt::print("copy: {} == {}? {}\n", copy, a, (copy == a));
auto move = std::move(copy);
fmt::print("move: {} == {}? {}\n", move, a, (move == a));
fmt::print("copy now moved-from: {}, empty? {}\n", copy, copy.empty());
dyn_array<Sensor>(4); // test destructors
fmt::print("constructions({}) and destructions({}) match? {}\n",
constructions, destructions, constructions == destructions);
fmt::print("all default, no copy ctors? {}\n",
(copy_ctor == 0) && (default_ctor == constructions));
dyn_array { Sensor{}, Sensor{}, Sensor{} };
fmt::print("constructions({}) and destructions({}) match? {}\n",
constructions, destructions, constructions == destructions);
fmt::print("initializers({}) were uninitialized-copied: {}\n",
copy_ctor,
(copy_ctor == 3) && (default_ctor + copy_ctor == constructions));
}
打印：
With initializers: {3.1415}, {"one", "two", "three"}
Without: {"", "", ""}, {1}
sizeof(a) == sizeof(void*)? true
copy: {3, 2, 1} == {3, 2, 1}? true
move: {3, 2, 1} == {3, 2, 1}? true
copy now moved-from: {}, empty? true
constructions(4) and destructions(4) match? true
all default, no copy ctors? true
constructions(10) and destructions(10) match? true
initializers(3) were uninitialized-copied: true
Of course you can do this without using C99 flexible array members, but I didn't want to meddle with alignment manually right now.
奖励：[] 索引，front，back，at 访问器
添加这些真的很简单：
auto& operator[](size_t n) const { return *(begin() + n); }
auto& operator[](size_t n) { return *(begin() + n); }
auto& at(size_t n) const { return n<size()?*(begin() + n): throw std::out_of_range("dyn_array::at"); }
auto& at(size_t n) { return n<size()?*(begin() + n): throw std::out_of_range("dyn_array::at"); }
auto& front() const { return at(0); }
auto& front() { return at(0); }
auto& back() const { return at(size()-1); }
auto& back() { return at(size()-1); }
当然 push_back/erase/etc 已经过时了，因为构建后尺寸不会改变。
通常 std::vector 对象大小为 24 字节，因为它被实现为 3 个指针（在 64 位 CPU 上每个指针大小为 8 字节）。这些指标是：
- 矢量开始
- 向量结束
- 向量保留内存结束（向量容量）
我们是否有任何类似的容器提供相同的接口（容量特性除外）但仅使用两个指针（或者可能是指针 + 大小值）实现？
它在某些情况下很有意义，比如我当前的项目。我在内存中保存了数百万个向量，但我不需要区分向量大小和容量，内存使用正在成为瓶颈。我考虑了几个选项：
std::string实施可能很棘手，包括短字符串优化之类的东西，这可能更糟。std::unique_ptr到一些分配的缓冲区。该接口不像std::vector那样方便，我最终会创建自己的 class 来包装指针加上缓冲区的大小，这是我试图避免的。
所以有现成的替代品吗？接受基于 Boost 库的解决方案。
I do not need to change its size after dynamic allocation (from the comments)
由于您不需要动态扩展向量，std::valarray<T> 可能是一个不错的选择。它的大小在构造时是固定的，所以实现不需要第三个指针。
这是将 unique_ptr<T[]> 封装在第一个 class 值类型中的绝对最小值，它模拟了 RandomAccessRange:
#include <memory>
template <typename T>
struct dyn_array {
explicit dyn_array(size_t n)
: _n(n), _data(std::make_unique<T[]>(n)) { }
auto begin() const { return _data.get(); }
auto end() const { return begin() + _n; }
auto begin() { return _data.get(); }
auto end() { return begin() + _n; }
auto size() const { return _n; }
private:
size_t _n {};
std::unique_ptr<T[]> _data;
};
那是 15 行代码。看看吧Live
int main() {
using std::begin;
using std::end;
for (int n; (n = size_gen(prng)) != 10;) {
dyn_array<double> data(n);
std::iota(begin(data), end(data), 0);
static_assert(sizeof(data) == 2*sizeof(void*));
fmt::print("Size {} data {}\n", n, data);
}
}
打印例如
Size 8 data {0, 1, 2, 3, 4, 5, 6, 7}
Size 6 data {0, 1, 2, 3, 4, 5}
Size 7 data {0, 1, 2, 3, 4, 5, 6}
Size 6 data {0, 1, 2, 3, 4, 5}
我评论了两个版本
奖励：单指针大小
在上面的基础上，我意识到大小可以在内部分配dyn_array 恰好1个指针[=61] =].
#include <memory>
#include <cstdlib> // committing the sin of malloc for optimization
template <typename T>
struct dyn_array {
dyn_array(std::initializer_list<T> init)
: _imp(allocate(init.size(), true))
{ std::uninitialized_move(init.begin(), init.end(), begin()); }
dyn_array(dyn_array const& rhs)
: _imp(allocate(rhs.size(), true))
{ std::uninitialized_copy(rhs.begin(), rhs.end(), begin()); }
dyn_array(dyn_array&& rhs) { rhs.swap(*this); }
dyn_array& operator=(dyn_array rhs) { rhs.swap(*this); }
explicit dyn_array(size_t n = 0)
: _imp(allocate(n))
{ }
auto size() const { return _imp? _imp->_n : 0ull; }
auto begin() const { return _imp? _imp->_data + 0 : nullptr; }
auto begin() { return _imp? _imp->_data + 0 : nullptr; }
auto end() const { return begin() + size(); }
auto end() { return begin() + size(); }
auto empty() const { return size() == 0; }
bool operator==(dyn_array const& rhs) const {
return size() == rhs.size() &&
std::equal(rhs.begin(), rhs.end(), begin());
};
void swap(dyn_array& rhs) {
std::swap(_imp, rhs._imp);
}
private:
struct Impl {
size_t _n;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wpedantic"
T _data[]; // C99 extension
#pragma GCC diagnostic pop
};
struct Deleter {
void operator()(Impl* s) const {
while (s->_n) { s->_data[--(s->_n)].~T(); }
std::free(s);
}
};
using Ptr = std::unique_ptr<Impl, Deleter>;
Ptr _imp;
static Ptr allocate(size_t n, bool uninitialized = false) {
if (!n)
return {};
auto p = std::malloc(sizeof(Impl) + n*sizeof(T)); // could be moreconservative
auto s = Ptr(reinterpret_cast<Impl*>(p));
s->_n = n;
if (!uninitialized)
std::uninitialized_default_construct_n(s->_data, n);
return s;
}
};
我们可以用作：
#include <fmt/ranges.h>
static size_t constructions = 0;
static size_t default_ctor, copy_ctor = 0;
static size_t destructions = 0;
struct Sensor final {
Sensor() { ++constructions; ++default_ctor; }
Sensor(Sensor const&) { ++constructions; ++copy_ctor; }
~Sensor() { ++destructions; }
};
int main() {
fmt::print("With initializers: {}, {}\n",
dyn_array{3.1415f},
dyn_array{"one", "two", "three"});
fmt::print("Without: {}, {}\n",
dyn_array<std::string_view>{3},
dyn_array<float>{1},
dyn_array<int>{}); // empty by default, no allocation
auto a = dyn_array{3,2,1};
fmt::print("sizeof(a) == sizeof(void*)? {}\n", sizeof(a) == sizeof(void*));
auto copy = a;
fmt::print("copy: {} == {}? {}\n", copy, a, (copy == a));
auto move = std::move(copy);
fmt::print("move: {} == {}? {}\n", move, a, (move == a));
fmt::print("copy now moved-from: {}, empty? {}\n", copy, copy.empty());
dyn_array<Sensor>(4); // test destructors
fmt::print("constructions({}) and destructions({}) match? {}\n",
constructions, destructions, constructions == destructions);
fmt::print("all default, no copy ctors? {}\n",
(copy_ctor == 0) && (default_ctor == constructions));
dyn_array { Sensor{}, Sensor{}, Sensor{} };
fmt::print("constructions({}) and destructions({}) match? {}\n",
constructions, destructions, constructions == destructions);
fmt::print("initializers({}) were uninitialized-copied: {}\n",
copy_ctor,
(copy_ctor == 3) && (default_ctor + copy_ctor == constructions));
}
打印：
With initializers: {3.1415}, {"one", "two", "three"}
Without: {"", "", ""}, {1}
sizeof(a) == sizeof(void*)? true
copy: {3, 2, 1} == {3, 2, 1}? true
move: {3, 2, 1} == {3, 2, 1}? true
copy now moved-from: {}, empty? true
constructions(4) and destructions(4) match? true
all default, no copy ctors? true
constructions(10) and destructions(10) match? true
initializers(3) were uninitialized-copied: true
Of course you can do this without using C99 flexible array members, but I didn't want to meddle with alignment manually right now.
奖励：[] 索引，front，back，at 访问器
添加这些真的很简单：
auto& operator[](size_t n) const { return *(begin() + n); }
auto& operator[](size_t n) { return *(begin() + n); }
auto& at(size_t n) const { return n<size()?*(begin() + n): throw std::out_of_range("dyn_array::at"); }
auto& at(size_t n) { return n<size()?*(begin() + n): throw std::out_of_range("dyn_array::at"); }
auto& front() const { return at(0); }
auto& front() { return at(0); }
auto& back() const { return at(size()-1); }
auto& back() { return at(size()-1); }
当然 push_back/erase/etc 已经过时了，因为构建后尺寸不会改变。