更新列表的元素stl列表

Question

我正在处理一个整数矢量（std::list<std::list<std::vector<int>>> z(nlevel)）列表。

我可能有类似的东西：

{ {1} {2} {3} }
{ {1 2} {2 1} {1 3} }
{ {1 2 3} {2 1 3} {1 2 4} }

我需要删除整数的非唯一组合，因此，上面列表的第二个元素应变为

{ { 1 2 } {1 3} }

这是一个大对象，因此我尝试通过引用更新最外面的列表的每个元素。我已经尝试过类似的东西：

lit = z.begin();
for (i = 0; i < nlevel; i++) {
    distinct_z(*lit, primes);
    lit++;
}

其中distinct_z是通过引用查找唯一矢量组合的函数，但这似乎不会影响列表z。注意：distinct_z在我已经使用列表的第ith个元素的代码的另一部分中工作正常。我在下面提供了distinct_z。它包括R中Rcpp包中的一些唯一数据类型，但希望可以理解。本质上，我使用质数的对数和来标识整数的非唯一组合，因为整数的顺序无关紧要。重申一下，distinct_z在我的代码的另一部分中确实起作用，在此我向其传递了一个完整的int向量的实际列表。问题似乎是我正在尝试使用迭代器传递某些东西。

void distinct_lz(std::list<std::vector<int>> &lz,
                      const IntegerVector &primes) {
  int i, j, npids = lz.size();

  NumericVector pids(npids);
  std::list<std::vector<int>>::iterator lit = lz.begin();
  int z_size = lit -> size();
  for(i = 0; i < npids; i++) {
    for (j = 0; j < z_size; j++) {
      // cprime = primes[lit -> at(j)];
      // pids[i] += log(cprime);
      // cprime = primes[lit -> at(j)];
      pids[i] += log(primes[lit -> at(j)]);
    }
    lit++;
  }
  LogicalVector dup = duplicated(round(pids, 8));
  lit = lz.begin();
  for(i = 0; i < npids; i++) {
    if(dup(i) == 1) {
      lz.erase(lit);
    }
    lit++;
  }
}

做我想做的最好的方法是什么？

背景：数据结构可能看起来不必要地复杂，但是我正在使用广度优先方法枚举所有从顶点开始的连接子图。因此，给定当前子图，我将看到其他哪些顶点被连接以创建一组新的子图并重复。最初，我使用int向量列表来完成此操作，但是由于如果删除部分向量，则必须复制当前对象，因此删除重复项的速度非常可笑。即使结构更复杂，此方法也要快得多。

编辑：这是一个解决方案，主要完成我想要的操作，尽管它会导致某些不希望的复制。我更新了distinct_z以返回对象的副本，而不是修改引用，然后替换了lit处的元素。

  lit = z.begin();
  for (i = 0; i < nlevel; i++) {
    (*lit) = distinct_z(*lit, primes);
    lit++;
  }

Answer 1

在C ++中，有一个众所周知的成语，称为erase-remove idiom，用于从STL容器中删除元素。它基本上涉及将不需要的物品洗到容器的末端，然后擦除不需要的尾巴。

我们可以使用谓词函数（例如lambda）选择要删除的项目，并使用<algorithm>中的函数。在您的情况下，我们使用一组整数（std::<set<int>>）来存储唯一组合。将列表中的每个向量转换为一组整数，如果以前从未见过，则将其删除。

#include <set>
#include <list>
#include <vector>
#include <algorithm>
#include <iostream>

void distinct_lz(std::list<std::vector<int>>& lz)
{
    std::set<std::set<int>> unqiueNums;

    lz.erase(std::remove_if(lz.begin(), lz.end(),
        [&unqiueNums](std::vector<int>& v) {
            std::set<int> s{ v.cbegin(), v.cend() };
            if (unqiueNums.find(s) != unqiueNums.end())
                return true;
            else
            {
                unqiueNums.insert(s);
                return false;
            }
        }), lz.end());

}

int main()
{
    std::list<std::vector<int>> lv = { {1, 2}, {2, 1}, {1, 3}, {3,4} };
    distinct_lz(lv);
    for (auto &v: lv)
    {
        for( auto n: v)
        {
            std::cout << n << " ";
        }

        std::cout << "\n";
    }
}

输出：

1 21 33 4

工作版本here。