C++：从一个向量中删除另一个向量中的元素

Question

我需要删除出现在向量A和向量B中的元素，但保留仅在向量A中的元素。向量的大小可以是任意的，但不一定相等。

例如，如果： 向量A包含值<1,4,66,22> 向量B包含值<1,22,44,93,102,543> 那么执行操作后： 向量A应该包含<4,66> 向量B应该包含<44,93,102,543> 我需要遍历两个向量并对比值来实现吗？还是有一个函数可以简化这个过程？ 这是我尝试过的方法，但似乎不起作用。

string rawInput;
string fileInput;
vector<string> stdInput; //vector to hold standard input values
vector<string> fileList; //vector to hold file values   

sizeIn = stdInput.size();
sizeFile = fileList.size(); 

if (sizeIn >= sizeFile)
    {
        for (count = 0;count <= sizeIn; count++)
        {
            for (count1 = 0; count1 <= sizeFile; count1++)
            {
                if (stdInput[count1] == fileList[count])
                {
                    stdInput.erase(stdInput.begin()+count1-1);
                    fileList.erase(fileList.begin()+count-1);

                }

            }
        }
    }
    else
    {
        for (count = 0; count <= sizeFile; count ++)
        {
            for (count1 = 0; count1 <= sizeIn; count1++)
            {
                if (stdInput[count] == fileList[count1])
                {
                    stdInput.erase(stdInput.begin()+count-1);
                    fileList.erase(fileList.begin()+count1-1);

                }   
            }
        }
    }

- hournet562

---

保留的元素是否需要保持相对顺序？ - Arun

如果这两个向量都是已排序的，你可以使用 std::set_difference。 - Some programmer dude

不，我会在 sort(fileList.begin(), fileList.end()) 之后重新排列它们。 - hournet562

@hournet562 在使用之前最好对它们进行排序，并像之前所述使用 std::set_difference。-- 并且使用 strncmp 比较值 -- strcmp？？？ - PaulMcKenzie

Answer 1

这是一项繁重的工作。我本来会建议使用std::set_difference，但由于您想要原地进行操作，以下代码可以为您完成此操作，算法复杂度较好：

template<typename T>
void remove_intersection(std::vector<T>& a, std::vector<T>& b){
    std::unordered_multiset<T> st;
    st.insert(a.begin(), a.end());
    st.insert(b.begin(), b.end());
    auto predicate = [&st](const T& k){ return st.count(k) > 1; };
    a.erase(std::remove_if(a.begin(), a.end(), predicate), a.end());
    b.erase(std::remove_if(b.begin(), b.end(), predicate), b.end());
}

C++不是很美吗？ :-)

---

一个演示：

int main(){
    std::vector<int> a = {1,4,66,22};
    std::vector<int> b = {1,22,44,93,102,543};

    remove_intersection(a, b);

    for(auto k : a) std::cout << k << ' ';
    std::cout << std::endl;
    for(auto k : b) std::cout << k << ' ';
}

输出：

4 66 
44 93 102 543 

请点击 此处 查看实时演示。

以上方法有很多变种。例如，如果你担心在计数很大时，count 可能会花费太长时间，你可以实现一个简单的函数来查找并计算最多 2 个元素；或者你可以使用两个不同的无序集合。

- WhiZTiM

Answer 2

感谢 @WhiZTiM 提供的好代码示例。

但对于我的应用程序，它有一些问题：

• 只适用于向量
• 从 a 中删除了不在 b 中但重复的元素
• 不关注const正确性

这个改良版解决了这些问题。

template <typename ContainerT>
void remove_intersection(ContainerT& a, ContainerT& b)
{
    std::unordered_set<ContainerT::value_type> const uniqueAs { a.cbegin(), a.cend() };
    std::unordered_multiset<ContainerT::value_type> st { uniqueAs.cbegin(), uniqueAs.cend() };

    st.insert(b.begin(), b.end());
    auto const predicate = [&st](ContainerT::value_type const& k) { return st.count(k) > 1; };
    a.erase(std::remove_if(a.begin(), a.end(), predicate), a.cend());
    b.erase(std::remove_if(b.begin(), b.end(), predicate), b.cend());
}

- S. Weis

Answer 3

不，我会在之后通过 sort(fileList.begin(), fileList.end()) 对它们进行排序。

因此，在渐近意义下，在排序之前和之后是相同的。

使用 set_difference，您可以执行类似以下操作：

template<typename T>
void remove_intersection(std::vector<T>* c1, std::vector<T>* c2) {
  assert(c1 != nullptr);
  assert(c2 != nullptr);

  std::sort(std::begin(*c1), std::end(*c1));  // O(n1 logn1)
  std::sort(std::begin(*c2), std::end(*c2));  // O(n2 logn2)

  std::vector<T> difference1, difference2;
  difference1.reserve(c1->size());
  difference2.reserve(c2->size());

  std::set_difference(std::begin(*c1), std::end(*c1),
                      std::begin(*c2), std::end(*c2),
                      std::back_inserter(difference1));
  // O(2*[N1 + N2 - 1])

  std::set_difference(std::begin(*c2), std::end(*c2),
                      std::begin(*c1), std::end(*c1),
                      std::back_inserter(difference2));
  // O(2*[N1 + N2 - 1])

  *c1 = std::move(difference1);  // O(1)
  *c2 = std::move(difference2);  // O(1)
}

- BiagioF

Answer 4

for (auto& d : deleteCommands) {
    auto it = stackCommands.begin();
    while (it != stackCommands.end()) {

        if (d == *it._Ptr) {

            commands[d]->Exit(this);

            it = stackCommands.erase(it);
        }

        else { it++; }
    }
}

- Дмитрий Мизантропович

Answer 5

我可能会尝试类似以下的东西。

// Create sets from vectors. This eliminates the duplicate elements.
const unordered_set<int> setA{vecA.cbegin(), vecA.cend()};
const unordered_set<int> setB{vecB.cbegin(), vecB.cend()};

PopulateSetDiff(vecA, setA, setB);
PopulateSetDiff(vecB, setB, setA);

// Populate 'vec' with 'set1 - set2'
template <typename T>
void PopulateSetDiff(
  vector<T>& vec,
  unordered_set<T> const& set1,
  unordered_set<T> const& set2) {
  vec.clear();
  for (const auto elem : set1) {
    if (set2.find(elem) == set2.cend()) {
      vec.push_back(elem);
    }
  }
  vec.shrink_to_fit();
}

- Arun