进行排序，并从两个不同字段

Question

确定唯一性的容器

假设我已经定义的类型如

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

我想保持这些在使他们通过Item::y排序的容器中，并确保每个条目具有唯一的Item::x。我需要能够添加项目并删除顶部项目（即具有最小值y的项目）。

换句话说，什么可以做这件事：

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; 

这将理想产量：

1 0.6 
3 0.6 
2 1.1 
0 6.1 

起初我是用std::set<Item>与确保item_1.y < item_2.y一个比较函数，但是这不允许当item_1.y == item_2.y但item_1.x != item_2.x时要添加的项目。

有什么建议吗？谢谢。

更新

我决定看看Boost多指数看，因为我有可用的推动作用。我几乎有一个解决方案（使用下面华金的回答）：

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

这个程序的输出是：

1 0.6 
3 0.6 
2 1.1 
0 3.2 

这是我想要什么差不多。请注意，插入x = 0的项目不会替换具有该索引的容器中的前一个项目。另外，除此之外，删除并返回容器中顶部项目的最佳方法是什么？请问这样的事情就够了：

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

你想两个容器：一个确保唯一的x，另提供订购的y然后x。

一个boostmulti_index容器可以两者同时进行，但可能是矫枉过正。

已使用set或unordered_set的x值，并丢弃已存在的东西。

有元件的set通过y有序然后x（std::tie(y,x)<std::tie(o.y,o.x)是最简单的&最安全的C++ 11的方式），或一个由multiset有序y，维持秩序。我喜欢set s到multiset s ^我自己，但是这可能只是性格缺陷。

Answer 2

相反，别人怎么说，我不认为使用Boost.MultiIndex的矫枉过正：这恰恰是一种的lib是专为的情况。

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;