listvector：连续内存，插入时无需重新分配！

• 下载 main.zip - 4.2 KB

上帝模式开启

我发明了一种新型内存，它始终是连续的，但在我执行 insert() 或 push_back() 时，元素无需重新定位。它由放射性钋 210 制成，半衰期为 32 毫秒，每兆字节价格高达 14.3 亿美元。

我将在 2042 年于国际空间站举行的计算机科学会议上展示它。如果您无法参加，至少可以在稍后查看包含 6.023x10^23 页的论文集。

届时我将已获得图灵奖。还记得 std::future() 和 std::promise() 吗？是的，它们承诺给我很多钱。不幸的是，实现这样的容器比我为了获得那个著名的奖杯所要做的事情要便宜和容易得多 :)

上帝模式关闭

好吧，我不是上帝。我只是喜欢尝试一些奇怪的东西。

其实并不难。基本上，这是一个 Windows 文件映射技巧。容器中的每个元素都有自己的固定地址，元素在内存中不是连续的（就像 std::list 一样），但还有一个额外的映射指向实际地址，您获得的迭代器包含这些指针地址。

您有两种指针。一种是内部集合。这是元素实际存储的地方，这就像 std::list 一样管理：插入/删除是恒定的，因为没有任何东西被移动，但是内部集合不是连续的。

外部集合（用户通过迭代器看到的内容）仅仅是通过 MapViewOfFileEx 进行的映射，指向内部指针。在插入/删除时，它们会被重新映射，以便指向正确的元素，同时始终保持连续。

因此，您同时拥有了连续内存和高度优化的插入/删除！

- 真正的 - 难点

对齐是 65536 字节。 ouch。抱歉，这是 Win32 的页面粒度。因此，容器中的每个元素都需要 65536 字节的倍数，这意味着，为了使用我们的容器，您要么存储大型对象（实际上，略低于 65536 的倍数），要么您完全痴迷于性能。

嗯，这两点都适用于我 :P。我们开始吧！

 

为什么要有一个新容器？

扩展现有容器时存在一些困难。

• STL 容器不是为了继承而设计的（没有虚函数/析构函数）等。
• 自定义分配器只能分配/释放，没有任何关于谁在调用、迭代器位置等的通知。

因此，我无法继承 std::list 或 std::vector，也无法只编写一个自定义分配器。必须创建一个全新的类。

 

内部

每个元素都存储为 listvector::MAP 类。这个结构包含一个指向实际内存（保持固定）的指针和一个指向映射内存的指针。

GetSystemInfo() 函数返回最小分配粒度。在我的系统上是 64KB。

InitFull() 创建句柄和映射（从构造函数调用）。

MemPerElement() 函数决定每个元素需要多少内存，并将其对齐到分配粒度。

GetMaxMemoryNeeded() 根据容器的容量和每个元素所需的内存来决定我们需要的内存量。

MapTheList() 和 UnmapTheList() 将元素的实际、固定、非连续内存地址映射和取消映射到非固定连续内存地址，以便 data()、at() 和 operator[] 可以工作。映射是通过 MapViewOfFileEx 以读/写访问进行的，它强制 Windows 为我们使用特定的映射地址。

SetMinAddress() 找到当前容量的最佳基映射地址。这就是 data() 返回的值。

CreateH() 和 DestroyH() 实际创建和销毁文件映射对象和内存的实际映射。

recreate() 如果容量需要增长，则会重新创建整个容器。

ClearAndDestroy() 进行清理（由 recreate() 和析构函数使用）。

FindMapAtPosition() 根据实际地址查找元素。它由 FindFreeAreaForElement() 用于为新元素创建固定内存。

smartadd() 根据当前和请求的大小更改容量。

CreateMemoryAtEnd() 由 push_back 等函数调用，为末尾的插入创建内存。它是 CreateMemoryBeforePosition() 的优化版本。

CreateMemoryBeforePosition() 由任何其他内存创建调用。

 

 

template <typename T> listvector

该类是 std::list 和 std::vector 的组合，提供几乎相同的功能集，除了少数我们将指出的例外。该类是模板形式的，这意味着它可以用于所有有资格包含在 STL 容器中的类型。

如果任何 Win32 操作失败，该类将抛出 std::bad_alloc。

构造函数、operator =() 和析构函数

// Creates an empty listvector with capacity = 10
listvector();

// Creates a listvector with a specific size.
listvector(size_t); 

// Constructs from an initializer_list.
listvector(const std::initializer_list<T>&); 
listvector(std::initializer_list<T>&&);

// Constructs from a vector
listvector(const std::vector<T>&);
listvector(std::vector<T>&&);

// Constructs from a list
listvector(const std::list<T>&);
listvector(std::list<T>&&);

// Constructs from a listvector
listvector(const listvector<T>&);
listvector(listvector<T>&&);

// Destructor
~listvector(); 

每个构造函数都附带其相关的 operator =()。

 

 

at()、operator[] 和位置请求

T& at(size_t idx);
T& operator[](size_t idx);
T& back();
T& front();

与 STL 类似。 at() 执行边界检查（抛出 std::out_of_range），而 operator[] 不执行。还存在 const 版本。

 

迭代器

listvectoriterator<T> begin();
const listvectoriterator<T> cbegin() const;
listvectoriterator<T> rbegin();
const listvectoriterator<T> crbegin() const;
listvectoriterator<T> end();
const listvectoriterator<T> cend() const;
listvectoriterator<T> rend();
const listvectoriterator<T> rend() const;

与 STL 类似。还存在 const 版本。迭代器始终指向元素的映射地址，这些地址在调整大小时会改变，但实际元素不会改变，因为它们的原始地址保持固定。

listvectoriterator 还提供 ++、+、-、==、!= 等运算符。

 

insert()、emplace()、splice() 和 push 操作

template <class... Args>
        listvectoriterator<T> emplace(const listvectoriterator<T> position,Args&&... args);
template <class... Args>
        void emplace_back(Args&&... args);
template <class... Args>
        void emplace_front(Args&&... args);
listvectoriterator<T> insert(const listvectoriterator<T> position,const T& val);
listvectoriterator<T> insert(const listvectoriterator<T> position,T&& val);
void insert(const listvectoriterator<T> pos,size_t count,const T& value);
void insert(const listvectoriterator<T> pos,std::initializer_list<T> li);
template <class InputIterator>
        listvectoriterator<T> insert(const listvectoriterator<T> pos,InputIterator first,InputIterator last);
void push_back(const T& val);
void push_back(T&& val);
void push_front(const T& val);
void push_front(T&& val);
void splice(const listvectoriterator<T> pos,listvector& x);
void splice(const listvectoriterator<T> pos,listvector&& x);
void splice(const listvectoriterator<T> pos,listvector& x,const listvectoriterator<T> i);
void splice(const listvectoriterator<T> pos,listvector&& x,const listvectoriterator<T> i);
void splice(const listvectoriterator<T> pos,listvector& x,const listvectoriterator<T> first,const listvectoriterator<T> last);
void splice(const listvectoriterator<T> pos,listvector&& x,const listvectoriterator<T> first,const listvectoriterator<T> last);

与 STL 类似。当发生插入时，容器不会移动/复制任何其他元素。相反，它会重新映射它们的实际地址（它们是固定的且不连续的）到映射地址，而映射地址始终是连续的。如果插入不强制更改容量，则原始起始地址（即 data() 返回的地址）保持不变。如果插入强制更改容量，则基地址也会改变，并且项目会被移动到新的位置。

 

erase()、remove() 和 pop 操作

void remove(const T& val);
template <class Predicate>
        void remove_if(Predicate pred);
listvectoriterator<T> erase(listvectoriterator<T> position);
listvectoriterator<T> erase(listvectoriterator<T> first,listvectoriterator<T> last);
void pop_back();
void pop_front();

与 STL 类似。删除不会改变容量。

 

更多内部细节

在这里您将看到有关该容器的一些有趣细节。

迭代器的增量/减量不仅仅是简单地将指针类型本身加上一个偏移量，因为我们需要对齐。因此，让我们看一个示例

 listvectoriterator<T>& operator++()
     {
     size_t pp = (size_t)p;
     if (R)
         pp -= sz;
     else
         pp += sz;
     p = (T*)pp;
     return *this;
     }

for (size_t i = 0; i < elements.size(); i++)
    {
    size_t bb = b;
    bb += i*MemPerElement();
    ULARGE_INTEGER mp = {0};
    mp.QuadPart = (unsigned long long)elements[i].ActualPtr;
    mp.QuadPart -= (unsigned long long)FullMap;
    elements[i].Map = (T*)MapViewOfFileEx(hF,FILE_MAP_ALL_ACCESS,mp.HighPart,mp.LowPart,grd,(LPVOID)bb);
    if (!elements[i].Map)
        throw std::bad_alloc();
    }

template <class... Args>
listvectoriterator<T> emplace(const listvectoriterator<T> position,Args&&... args)
    {
    MAP& m = CreateMemoryBeforePosition(position.idx());
    new (m.ActualPtr) T(std::forward<T>(args...));
    listvectoriterator<T> r((size_t)MinAddress,(size_t)m.Map,MemPerElement());
    return r;
    }

void sort()
    {
    UnmapTheList();
    std::sort(elements.begin(),elements.end());
    MapTheList();
    }

其他 STL 助手

以下函数也可用

• capacity();
• clear();
• data();
• size();
• max_size();
• reserve();
• resize();
• reverse();
• shrink_to_fit();
• sort() 和带有 Compare 类的模板 sort。
• swap();
• unique() 和带有 BinaryPredicate 类的模板 unique。

还有一些函数缺失，例如 assign() 和 merge()。

测试

文件中包含一些测试函数，它们将向您展示容器的工作原理。我还创建了一个具有复制/移动构造函数等的类 F 来验证是否调用了正确的函数。

历史

• 13 - 09 - 2015：首次发布