I want to use set to remove the duplicate element and keep the order on insert
I want to use set to remove duplicate items and keep their order at the same time. So I am trying to change the comparison parameter to sort them in the order it specified.
#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);
}
Expression from IDE: invaild operator <
source to share
std::set
relies on a comparator to maintain strong weak ordering and ensure that each value is unique. You cannot have a sort std::set
in the order they were inserted.
One possible solution is to have two containers std::set
to hold unique items and an index std::vector
to preserve the order in which they were inserted. Perhaps a vector can contain iterators to a set.
It might be convenient to encapsulate the two containers in your own class with its own iterator. Below is the 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 << " ";
}
source to share
Another 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;
}
source to share