c++ - 具有持久查找的线性内存容器？

Question

我一直在网上搜索能够最好地处理这种情况的容器:

1. 线性内存(没有像对象池或分配器那样的间隙)

2. 以某种方式提供对容器中对象的引用，该对象在添加/删除之间保持持久。或者一种快速搜索以找到原始对象的方法。

3. 相当快地添加到末尾和从中间移除(但不需要插入)

到目前为止，我能找到的唯一解决方案是使用 std::vector，当发生删除时，我会更新当前删除索引上方的所有引用索引。这看起来很糟糕，正在寻找任何其他更有效的解决方案。

Answer 1

这是一个可怕的想法。我根本没有尝试过，所以可能有很多错误。

  template <typename T>
  class InsaneContainter {
  public:
     class MemberPointer {
        friend class InsaneContainer;
        size_t idx_;
        InsaneContainter* parent_;
     public:
        MemberPointer(InsaneContainter* parent,size_t idx) idx_(idx),parent_(parent){}
        T& operator*() {
           parent->members[idx_];
        }
     };
     friend class MemberPointer;
     using Handle = std::shared_ptr<MemberPointer>;
     Handle insert(const T& t) {
        members.push_back(std::make_tuple(T{t},Handle{new MemberPointer{this,members.size()}));
        return std::get<1>(members.back());
     }
     Handle GetHandle(size_t idx) {
       return std::get<1>(members[idx]);
     }
     void delete(size_t idx) {
         //swap with end
         std::swap(members[idx],members.back());
         std::get<1>(members[idx])->idx_=idx;
         members.pop_back();
     }
private:
     std::vector<std::tuple<T,std::shared_ptr<MemberPointer>> members_;
};

想法是，在插入时，您将收到一个始终具有 O(1) 查找和删除时间的句柄。虽然查找对象的时间复杂度为 O(n)，但一旦找到它，您就可以获得将保持最新的句柄。

这种结构的使用是......至少可以说是有限的，所以我怀疑这里有 X vs Y 问题。