STL 映射和集合中的排序顺序

Question

用户定义的对象在map和set中是如何排序的？ 据我所知，映射/集合是排序关联容器：插入的元素根据其保存的键进行排序。

但map和set内部使用operator >来对它们的元素进行排序。

从 SGI 站点，我有以下示例：

struct ltstr
{
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) < 0;
    }
};

int main()
{
    map<const char*, int, ltstr> months;

    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;

    cout << "june -> " << months["june"] << endl;

    map<const char*, int, ltstr>::iterator cur  = months.find("june");
    map<const char*, int, ltstr>::iterator prev = cur;
    map<const char*, int, ltstr>::iterator next = cur;

    ++next;
    --prev;

    cout << "Previous (in alphabetical order) is " << (*prev).first << endl;
    cout << "Next (in alphabetical order) is " << (*next).first << endl;
}

在上面的示例中，值是如何排序的？

编辑：代码从注释中移出：

typedef map <string, int> Mint ;

int main() 
{
    string Name ;
    int Marks;
    Mint Grade;
    for (int i = 0; i<4; i++) 
    {
        cin>> Name ; 
        cin >> Marks; 
        Grade [Name] = Marks ; 
    } 
    Mint :: iterator iter; 
    for( iter = Grade.begin(); iter != Grade.end(); iter++)
        cout<< (*iter).first<<“ \t ” <<(*iter).second<<“\n” ; 
    return 0; 

} 

值将如何排序？

Answer 1

std::map 使用函子对元素进行排序。默认情况下是 std::less 使用运算符<。在您的示例中，有一个用户定义的函子 ltstr ，它将有助于根据元素的键按字母顺序对元素进行排序。

Answer 2

首先，默认情况下使用 operator<，而不是 operator>。在您的情况下，您在创建地图对象时通过传递第三个模板参数来传递自定义比较函数。在将每个元素插入到映射时，此比较函子用于确定映射中对象的相对顺序，即用于比较键。例如，当您执行 months["february"] = 28; 时，map 会比较键“january”和“february”。由于我们正在进行字符串比较，因此该比较返回一个大于 0 的值。该值用于确定键“february”相对于“january”的位置。