C++多集中的重复计数

Question

UPD:-
值实例
2.3
3.2
5.1

我想将multiset中存在的所有实例的计数限制为1。

#include<bits/stdc++.h>
using namespace std;
int main() {
multiset<int> p1;

p1.insert(5);
p1.insert(2);
p1.insert(3);
p1.insert(3);
p1.insert(2);
p1.insert(2);

for(auto itr : p1) {

if(p1.count(itr) > 1)
p1.erase(itr);
cout << itr;
}

}

如何解决此问题？

Answer 1

我的评论：

在这种情况下，您应该使用std::set<int>，因为这实际上符合您的需求。如果愿意，还可以使用std::map<int, int>将关键字映射到出现次数。

OP回复：

你能把这个添加到一个完整的答案中吗，这样我就可以接受这个问题了？

开始：

只过滤重复：

#include <iostream>
#include <set>
int main()
{
int sample[] = { 5, 2, 3, 3, 2, 2 };
// add all values at most once
using Table = std::set<int>;
Table table;
for (int value : sample) table.insert(value);
// output the result
for (const Table::value_type& entry : table) {
std::cout << "Value " << entry << "n";
}
}

输出：

Value 2
Value 3
Value 5

在coliru上演示

---

计数出现次数：

#include <iostream>
#include <map>
int main()
{
int sample[] = { 5, 2, 3, 3, 2, 2 };
// add all values at most once but count the number of occurrences
using Table = std::map<int, unsigned>;
Table table;
for (int value : sample) ++table[value];
// output the result
for (const Table::value_type& entry : table) {
std::cout << "Value " << entry.first << " (" << entry.second << " times)n";
}
}

输出：

Value 2 (3 times)
Value 3 (2 times)
Value 5 (1 times)

在coliru上演示

诀窍：

std:：map:：operator[]在键还不存在的情况下插入一个元素。该元素(在本例中为std::pair<const int, unsigned>(默认初始化，这允许它以{ key, 0 }开始。

因此，有两种情况：

• 键还不存在：
  元素被创建为{ key, 0 }，并且值(元素的.second(立即递增，从而产生{ key, 1 }
• 键已经存在：
  值(元素的.second(将再次递增

---

过滤重复项的变化：

这保持了原始输入顺序，但删除了重复(通过在单独的std::set中记账(。

#include <iostream>
#include <set>
#include <vector>
int main()
{
using Sample = std::vector<int>;
Sample sample = { 5, 2, 3, 3, 2, 2 };
// remove duplicates
using Table = std::set<int>;
Table table;
Sample::iterator iterRead = sample.begin();
Sample::iterator iterWrite = sample.begin();
for (; iterRead != sample.end(); ++iterRead) {
if (table.insert(*iterRead).second) *iterWrite++ = *iterRead;
}
sample.erase(iterWrite, sample.end());
// output the result
for (const Sample::value_type& entry : sample) {
std::cout << "Value " << entry << "n";
}
}

输出：

Value 5
Value 2
Value 3

在coliru上演示

诀窍：

std:：set：：insert((返回一对iterator和bool
iterator指向集合中的密钥(已插入或已存在(。bool表示密钥是被插入(true(还是已经在那里(false(。

另一个技巧：

仅仅从std::vector中擦除每个找到的重复将导致更糟糕的复杂性O(n²(。

因此，使用了两个迭代器，一个用于读取，另一个用于写入。因此，还没有在记账表中(因此第一次出现(的每个输入值都会被写回，否则就不会。因此，第一次出现的每个值都会朝着开头移动，并附加到第一次发生的以前的值上。此外，iterWrite指向循环后最后一个写入的元素，可用于擦除其余元素(包含所有重复的左输入值(。

该算法的复杂度为O(n(——比简单的方法要好得多。

Btw。标准算法std:：remove((、std:：move_if((以相同的方式执行。

因此，std::remove_if():可以实现相同的算法

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
int main()
{
using Sample = std::vector<int>;
Sample sample = { 5, 2, 3, 3, 2, 2 };
// remove duplicates
using Table = std::set<int>;
Table table;
Sample::iterator last
= std::remove_if(sample.begin(), sample.end(),
[&](int value) { return !table.insert(value).second; });
sample.erase(last, sample.end());
// output the result
for (const Sample::value_type& entry : sample) {
std::cout << "Value " << entry << "n";
}
}

输出：

类似于

在coliru上演示

Answer 2

#include <iostream>
#include <set>
using namespace std;
int main()
{
multiset<int> p1; 
p1.insert(5);
p1.insert(2);
p1.insert(3);
p1.insert(4);
p1.insert(2);
p1.insert(2);
for (auto iter = p1.begin(); iter != p1.end();)
{
p1.count(*iter) > 1 ? iter = p1.erase(iter) : iter++;
}
for (auto & iter : p1)
{
cout << iter << ", ";
}

return 0;
}