快速搜索和删除 std::list 个对象

Question

我有一个非常大的对象（节点）列表，我希望能够 remove/delete 基于列表中的一组值的元素。最好在恒定时间...

对象（除其他外）的值如下：

long long int nodeID;
int depth;
int numberOfClusters;
double [] points;
double [][] clusters;

我需要做的是查看列表，并检查除nodeID之外的所有字段中是否有任何元素具有相同的值。

现在我正在做这样的事情：

for(i = nodes.begin(); i != nodes.end(); i++)
{
    for(j = nodes.begin(); j != nodes.end(); j++)
    {
        if(i != j)
        {
            if(compareNodes((*i), (*j)))
            {
                j = nodes.erase (j);
            }
        }
    }
}

其中compareNodes()比较两个节点内的值。但这是非常低效的。

我正在使用 erase，因为这似乎是删除 std::list 中间元素的唯一方法。

最理想的是，我希望能够根据这些值找到一个元素，如果存在则将其从列表中删除。

我正在考虑某种哈希映射来在恒定时间内找到元素（指向元素的指针），但即使我能做到，我也找不到不迭代就删除元素的方法名单。看来我必须使用 erase ，但这需要遍历列表，这意味着列表大小的线性复杂性。还有 remove_if 但同样，列表大小的线性复杂度问题相同。

有没有办法在不遍历整个列表的情况下从 std::list 中删除一个元素？

Answer 1

首先，您可以通过从 std::next(i) 而不是 nodes.begin() 开始 j 来加速您现有的解决方案（假设您的 compareNodes 函数是可交换的）。

其次，hashmap 方法听起来可行。但是，既然可以保留迭代器，为什么还要保留指向元素的指针作为映射中的值呢？它们都是 "a thing which references the element," 但您可以使用迭代器删除元素。并且 std::list 迭代器不会在列表被修改时失效（它们很可能只是引擎盖下的指针）。

第三，如果您想 encapsulate/automate 查找和顺序访问，您可以查看 Boost.Multi-index 以构建一个同时具有顺序访问和散列访问的容器。

快速搜索和删除 std::list 个对象

Fast search and delete in a std::list of objects

c++

list

stdlist