c++ - 更新元素 STL 列表列表

Question

我正在处理整数 vector 列表( 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是一个通过引用查找唯一 vector 组合的函数，但这似乎不会影响列表 z .注:distinct_z在我已经使用列表的第 i 个元素的代码的另一部分中确实可以正常工作。我提供了distinct_z以下。它包括来自 R 中 Rcpp 包的一些独特数据类型，但希望是可以理解的。本质上，我使用素数的对数和来识别整数的非唯一组合，因为整数的顺序无关紧要。重申一下，distinct_z确实在我的代码的另一部分工作，我将一个实际的整数 vector 列表传递给它。问题似乎是我正在尝试使用迭代器传递一些东西。

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++;
  }
}

做我想做的事的最佳方法是什么？

背景:数据结构可能看起来不必要地复杂，但我正在使用广度优先方法从顶点开始枚举所有连接的子图。因此，给定一个当前子图，我看到连接了哪些其他顶点以创建一组新的子图并重复。我最初使用整数 vector 列表来执行此操作，但删除重复项的速度非常慢，因为如果我删除了部分 vector ，我必须复制当前对象。即使结构更复杂，这种方法也快得多。

编辑:这是一个主要做我想要的解决方案，尽管它会导致一些不希望的复制。我更新了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>> ) 来存储唯一组合。将列表中的每个 vector 转换为一组整数，如果以前没有见过，则将其删除。

#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 2
1 3
3 4

工作版here .