我应该使用哪种STL来完成这项任务？

Question

我需要一个必须添加/删除一些结构的队列,例如:

struct MyObject
{
  int offset;
  BYTE status, data1, data2;
  double beatPos;

  enum Status
  {
    isOff = 8,
    isOn = 9,
  };
}   

当我.Add()是一个元素时,这个队列必须把元素放在正确的位置,因为这个beatPos值必须从下面(队列的顶部,即我要弹出的下一个元素)到上面(最后一个元素)排序我将从中提取).

我看到有std :: priority_queue,但我不确定我是否可以选择哪个是排序字段.

此外,一旦我在列表中添加了一些结构,我想删除第一个元素(例如)beatPos=1,567(例如,可能位于列表中间;不一定在开头).

有线索吗？

Answer 1

你想要的是一个std::multiset.它采用比较模板参数,默认std::less为容器要存储的类型,但您可以指定不同的比较器.为此,我们可以创建一个lambda,它将比较两个MyObjects并根据beatPos成员返回哪个对象应该具有更高的优先级

auto my_compare = [](const MyObject & lhs, const MyObject & rhs)
                    {
                        return lhs.beatPos < rhs.beatPos;
                    }

然后我们可以使用它

std::multiset<MyObject, decltype(my_compare)> data(my_compare);

这将为您提供一个有序容器,可以存储多个具有相同对象的容器,beatPos并允许您访问容器的中间位置.

Answer 2

您可以使用std::multiset用户定义的比较器.例如:

bool MyObjectComp(const MyObject& lhs, const MyObject& rhs) {
    return lhs.beatPos < rhs.beatPos;
}

typedef std::set<MyObject, MyObjectComp> MyObjectSet;

现在,内部的排序MyObjectSet总是从最低到最高beatPos.您可以使用lower_bound()和搜索upper_bound(),并且可以使用获得最小值begin().

请注意,由于double值的性质(IEEE浮点),精确比较可能不起作用,因此您不一定会说,mySet.find(0.5)但您可以说mySet.upper_bound(0.49999).

也可以使用相同的用户定义比较器priority_queue,但该容器不支持按值搜索元素,这是您的要求之一.