C++使用多个元素对数据进行双重排序

Question

我有多个数据条目包含以下信息:id_number name1 date name2

可以将它放入这样的结构中:

struct entry {
  int id_number;
  string name1;
  int date;
  string name2;
}

在我的数据中,我有很多这样的条目,我想排序.首先,我想基于name1按字母顺序排序,然后按日期排序.但是,按日期排序是按字母顺序排序的子集,例如,如果我有两个具有相同名称的条目1,那么我想按日期对这些条目进行排序.此外,当我排序时,我希望条目的元素保持在一起,因此所有四个值都在一起.

我的问题如下:

1)我应该使用什么类型的数据结构来保存这些数据,这样当我按任何一个数据排序时,我可以将四个元素的集合保持在一起？

2)进行这种排序的最快方法是什么(就编写代码的时间而言).理想情况下,我想使用类似于algorithms.h中的排序,因为它已经内置.

3)STL是否有一些内置的数据结构可以有效地处理我所描述的双重排序？

Answer 1

你拥有的结构很好,除了你可能想要添加一个重载operator<进行比较.在这里,我正在进行"按名称比较,然后按日期"比较:

// Add this as a member function to `entry`.
bool operator<(entry const &other) const {
    if (name1 < other.name1)
        return true;
    if (name1 > other.name1)
        return false;

    // otherwise name1 == other.name1
    // so we now fall through to use the next comparator.

    if (date < other.date)
        return true;
    return false;
}

[编辑:所需要的是"严格的弱排序".如果你想详细了解它的意义和可能的替代方案,Dave Abrahams写了一篇关于C++的详细文章.

在上面的例子中,我们首先比较两者的name1字段.如果a<b,那么我们立即返回true.否则,我们检查a>b,如果是,我们返回false.在这一点上,我们已经消除了a<b和a>b,因此我们判断a==b,在这种情况下,我们测试的日期-如果a<b,我们返回true.否则,我们返回false - 日期相等,或者b>a,其中任何一个意味着测试为a<bfalse.如果排序需要排序(没有双关语),那么它是哪种情况,它可以通过交换参数再次调用该函数.名字仍然相同,所以它仍然会到达日期 - 如果我们弄错了,日期是相等的.如果我们在交换日期得到真实,那么从第二个日期开始的实际上更大.]

在operator<您的结构定义定义了默认使用的顺序.当/如果需要,您可以指定要使用的排序的另一个订单:

struct byid { 
    bool operator<(entry const &a, entry const &b) { 
        return a.id_number < b.id_number;
    }
};

std::vector<entry> entries;

// sort by name, then date
std::sort(entries.begin(), entries.end());

// sort by ID
std::sort(entries.begin(), entries.end(), byid());