c++ - 替代 C++ std::vector 的两个指针

Question

一般std::vector对象大小为 24 字节，因为它实现为 3 个指针(在 64 位 CPU 上每个指针大小为 8 字节)。这些指针是:

vector 开始

vector 结束

vector 保留内存结束( vector 容量)

我们是否有任何类似的容器提供相同的接口(interface)( 除了容量特性 )但仅使用两个指针(或者可能是指针 + 大小值)实现？
在某些情况下，例如我当前的项目，这很有意义。我在内存中保存了数百万个 vector ，但我不需要区分 vector 大小和容量，内存使用正在成为瓶颈。我考虑了几个选项:

std::string实现可能很棘手，包括短字符串优化之类的东西，这可能更糟。

std::unique_ptr到一些分配的缓冲区。界面不如std::vector方便，我最终会创建自己的类来包装指针加上缓冲区的大小，这是我试图避免的。

那么有什么现成的替代品吗？接受基于 Boost 库的解决方案。

Answer 1

这是封装 unique_ptr<T[]> 的绝对最小值在模拟 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}

我评论了两个版本

添加带有初始化器的构造函数指南live

并添加复制/移动语义live

奖励:单指针大小
在上面的基础上，我意识到大小可以在 dyn_array 的分配范围内。 正好 1 个指针 .
Live Demo

#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 已经退出，因为构建后大小不会改变。