A container that sorts and determines uniqueness from two different fields

Question

Suppose I've defined a type such as

struct Item
{
    Item(int i, float j) : x(i), y(j) {}
    int x;
    float y;
};

I would like to keep these in a container that keeps them sorted by Item::y, and ensures that each entry has a unique Item::x. I need to be able to add items and remove the top item (i.e., the item with the smallest y value).

In other words, something that can do this:

Container<Item> my_container;
my_container.insert(Item(0, 3.2));
my_container.insert(Item(2, 1.1));
my_container.insert(Item(0, 0.2));
my_container.insert(Item(1, 0.6));
my_container.insert(Item(3, 0.6));
my_container.insert(Item(0, 6.1));

for (auto &i : my_container)
  std::cout << i.x << " " << i.y << std::endl;

This would ideally yield:

1 0.6
3 0.6
2 1.1
0 6.1

At first I was using std::set<Item> with a comparison function that ensured item_1.y < item_2.y, but this disallows an item to be added when item_1.y == item_2.y but item_1.x != item_2.x.

Any suggestions? Thank you.

Update

I decided to look into Boost Multi-Index seeing as I have Boost available. I nearly have a solution (using Joaquín's answer below):

#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>

using namespace boost::multi_index;

struct Item
{
    Item(int i, float j) : x(i), y(j) {}
    int x;
    float y;
};

typedef multi_index_container<
  Item,
  indexed_by<
    ordered_non_unique<member<Item,float,&Item::y> >,
    ordered_unique<member<Item,int,&Item::x> >
  >
> my_container_t;

int main()
{
  my_container_t mc;
  mc.insert(Item(0, 3.2));
  mc.insert(Item(2, 1.1));
  mc.insert(Item(0, 0.2));
  mc.insert(Item(1, 0.6));
  mc.insert(Item(3, 0.6));
  mc.insert(Item(0, 6.1));

  const my_container_t::nth_index<0>::type& y_index = mc.get<0>();
  // Print
  for (auto &i : y_index)
    std::cout << i.x << " " << i.y << std::endl;

  return 0;
}

This program's output is:

1 0.6
3 0.6
2 1.1
0 3.2

which is almost what I want. Note that inserting items with x = 0 did not replace the previous item in the container with that index. Also, as an aside, what is the best way to remove and return the top item in the container. Would something like this suffice:

Item pop(my_container_t &mc)
{
  my_container_t::nth_index<0>::type& container = mc.get<0>();
  auto item = *container.begin();
  container.erase(container.begin());
  return item;
}

Answer 1

Contrary to what others say, I don't consider using Boost.MultiIndex overkill: this is precisely the kind of situations the lib is designed for.

using namespace boost::multi_index;

typedef multi_index_container<
    Item,
    indexed_by<
        ordered_non_unique<member<Item,float,&Item::y> >,
        ordered_unique<member<Item,int,&Item::x> >
    >
> my_container_t;

Answer 2

You want two containers: one ensures uniqueness of x, the other to provide ordering on y then x.

A boost multi_index container could do both at once, but may be overkill.

Have a set or unordered_set of x values in use, and discard things that are already there.

Have a set of elements ordered by y then x (std::tie(y,x)<std::tie(o.y,o.x) is the easiest&safest C++11 way), or a multiset ordered by y, to maintain order. I prefer sets to multisets myself, but that is probably just a character flaw.