CODEWITHSUNDEEP
c++stlset
lee
lee

Reputation: 87

I want use set to remove duplicate element and keep the order when they insert

I want use set to remove duplicate elements and keep their order by the same time. So I try to change the compare parameter to let they sort with the order they are inserted.

#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);
}

The expression from the IDE is :invaild operator <

Upvotes: 3

Views: 662

Answers (2)

Igor Abdrakhimov
Igor Abdrakhimov

Reputation: 118

Other possible solution is to use 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;
}

Upvotes: 3

Chris Drew
Chris Drew

Reputation: 15334

std::set relies on the comparator to maintain strict weak ordering and ensure each value is unique. You can't have a std::set sort in the order they are inserted.

One possible solution is to have two containers, a std::set to contain the unique elements and a std::vector index to keep the order they were inserted. The vector could perhaps contain iterators into the set.

It might be convenient to encapsulate the two containers in your own class with its own iterator. Here is a bare-bones implementation:

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

Upvotes: 3

Related Questions