c – 索引集(用于向量中的有效删除)

发布时间：2020-12-16 05:03:44 所属栏目：百科来源：网络整理

导读：我正准备实现我自己的类,以便从数组中有效删除,但我想我会问,看看它是否已经存在.我想要的是类似列表的访问效率,但使用数组.我想使用数组是出于缓存一致性的原因,所以我不必一直调用内存分配器(因为在分配节点时使用std :: list). 我想做的是创建一个包含两

我正准备实现我自己的类,以便从数组中有效删除,但我想我会问,看看它是否已经存在.我想要的是类似列表的访问效率,但使用数组.我想使用数组是出于缓存一致性的原因,所以我不必一直调用内存分配器(因为在分配节点时使用std :: list).

我想做的是创建一个包含两个数组的类.第一个是一组元素,第二个数组是一组整数,其中每个整数是第一个数组中的空闲槽.因此,我可以非常轻松地从数组中添加/删除元素,而无需为它们分配新内存,只需从空闲列表中获取索引并将其用于新元素即可.

有这样的事情吗？如果我自己做,我还必须自己创建迭代器,所以你可以迭代这个集合,避免数组中的任何空槽,我不太喜欢它.

谢谢.

注意：我想在集合上执行的操作类型是：

>迭代
>通过索引(或“我正在考虑的”句柄)随机访问单个元素
>删除集合中任何位置的元素
>在集合中添加元素(顺序不重要)

的std ::列表< T>实际上听起来与您工作的理论上正确的数据结构完全相同,因为它支持您列出的四个操作,所有操作都具有最佳的空间和时间复杂度. std :: list< T> :: iterator是一个句柄,即使你在列表中添加/删除其他项目,它仍然有效.

可能存在可以与std :: list< T,Allocator>一起使用的自定义分配器(即,不是std :: allocator< T>).获得所需的性能(内部池节点,然后每次添加或删除节点时都不进行运行时分配).但这可能有点矫枉过正.

我会开始使用std :: list< T>使用默认分配器,然后只查看自定义分配器或其他数据结构,如果您发现性能对您的应用程序来说太糟糕了.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!