c++ - 在 vector 之间共享元素的想法

Question

我正在研究一种玩具语言，以下是我正在尝试做的事情，

x = [1 2 3 4 5]

这定义了一个 vector ，

y = rest(x)

现在 y 包含 x 的所有元素，除了第一个。在 native 端 x 是一个 vector ，当用户调用 rest 时，它会自己制作一个完整的拷贝，除了第一个元素。这是我只有 2 kb 的 ram 的问题，制作完整的拷贝很昂贵。使用链表可以解决这个特殊问题，但如果在这种情况下会占用大量内存，则链表本身就是链表。那么是否有一种结构对于共享元素的这些类型的操作(首先是最频繁的操作)具有内存效率？

这是一种函数式语言，所以一旦 x 被定义，它就不会改变，而且没有可用的 boost 或 std c++ 库，我将实现一切。

Answer 1

你可以将 [1, 2, 3, 4, 5] 存储在一些内存中，并使 x 指向那 block 内存，即

template <typename T>
struct slice { T* begin; T* end; };

....

int backing_store[] = {1, 2, 3, 4, 5};
// ^-- the expression [1 2 3 4 5] create this

....

slice<int> x (backing_store, backing_store + 5);
// ^-- the assignment x = [1 2 3 4 5] does this

然后你可以将rest实现为

template <typename T>
slice<T> rest(slice<T> p) {
   return slice<T>(p.begin + 1, p.end); 
}

您可以使用一些引用计数方案或 GC(可能对您的内存来说太大)来确保 backing_store 在没有“切片”使用它时被释放。