我想使用set来移除重复元素并保持它们插入的顺序

Question

我希望使用set来去重并保持顺序。因此，我尝试更改比较参数，使它们按照插入顺序排序。

#include <set>
#include <iostream>
using namespace std;


template <class T>
struct compare
{
    bool operator() (T x, T y) 
    {
        return true;
    }
};

void main()
{
    set<int,compare<int>> one;

    one.insert(5);
    one.insert(3);
    one.insert(9);
    one.insert(1);
    one.insert(5);
    one.insert(5);
}

IDE中的表达式是：无效操作符<。

- lee

---

一个 std::set 已经对其项进行排序并且不包含重复项。你不需要在任何这些问题上“帮助”集合。所以我猜 set 不是你应该使用的容器。 - PaulMcKenzie

你想使用std::set有什么原因吗？你想做什么？ - Beta

我知道里面没有重复项。我只想让所有元素按照它们插入的顺序排列。 - lee

例如，“5,3,6,7,1”已经逐个插入到一个集合中，我希望它们在被插入到该集合后仍保持相同的顺序，“5,3,6,7,1”。 - lee

std::set 需要一个简单的弱排序。插入顺序并不能满足这个条件。你的比较器也不行。 - juanchopanza

Answer 1

std::set 依赖于比较器来维护严格弱序并确保每个值都是唯一的。你不能让一个 std::set 按照插入的顺序排序。

可能的解决方案是使用两个容器，一个 std::set 包含唯一元素，一个 std::vector 索引来保持它们被插入的顺序。向量可能包含对集合中迭代器的引用。

将这两个容器封装在自己的类中并具有自己的迭代器可能是方便的。这里是一个简单实现：

class MySetIterator {
  std::vector<std::set<int>::iterator>::iterator pos;
public:
  MySetIterator(std::vector<std::set<int>::iterator>::iterator pos) : pos(pos) {}
  int operator*() { return **pos; }
  MySetIterator& operator++() { ++pos; return *this; }
  bool operator!=(const MySetIterator& rhs) { return pos != rhs.pos; }    
};

class MySet {
 std::set<int> vals;
 std::vector<std::set<int>::iterator> order;
public:
  void insert(int val) { 
    auto ret = vals.insert(val);
    if (ret.second)
      order.push_back(ret.first);
  }
  MySetIterator begin() { return {order.begin()}; }
  MySetIterator end() { return {order.end()}; }    
};

int main() {
  MySet my_set;

  my_set.insert(5);
  my_set.insert(3);
  my_set.insert(9);
  my_set.insert(1);
  my_set.insert(5);
  my_set.insert(5);
  for (int val : my_set)
      std::cout << val << " ";
}

- Chris Drew

Answer 2

另一个可能的解决方案是使用boost::multi_index。

#include <iostream>

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>

namespace boost_mi = boost::multi_index;

typedef boost::multi_index_container<
    int,
    boost_mi::indexed_by<
        boost_mi::random_access<>, // preserves insertion order
        boost_mi::ordered_unique<boost_mi::identity<int> > // removes duplicates
    >
> MySet;

int main()
{
    MySet my_set;

    my_set.push_back(5);
    my_set.push_back(3);
    my_set.push_back(9);
    my_set.push_back(1);
    my_set.push_back(5);
    my_set.push_back(5);

    for (auto val : my_set) {
        std::cout << val << std::endl;
    }

    return 0;
}

- Igor Abdrakhimov