c++ - 我如何在 C++ STL 映射(或集合)中使用 compare()(不是 operator < ()) 函数作为比较器

Question

首先，请原谅我糟糕的英语。

---

我知道如何使用 about operator <() 和 operator()

但是，我认为这在某些情况下效率不高

例如有这样一个容器

const int c_DataSize = 10;

struct SA
{
    int Data[c_DataSize];

    SA(const int Data_[c_DataSize])
    {
        memcpy(Data, Data_, c_DataSize*sizeof(int));
    }

    bool operator < (const SA& sa_) const
    {
        for(int i=0; i<c_DataSize; ++i)
        {
            if(Data[i] < sa_.Data[i])
                return true;
            else if(Data[i] > sa_.Data[i])
                return false;
        }

        return false;
    }
};

set<SA> Container;

并且，两个像这样初始化的变量

int data1[c_DataSize] = {0,0,0,0,0,0,0,0,0,1}; 
int data2[c_DataSize] = {0,0,0,0,0,0,0,0,0,0}; 

SA a1(data1);
SA a2(data2);

并且，当将这些变量插入到容器中时容器在每次插入时使用“operator <”一次或多次。像这样，

// this is pseudocode
if(data1 < data2)        // (1)
    // data1 < data2
else if(data2 < data1)   // (2) inefficient ( do not need to compare Data[0]~Data[8] )
    // data1 > data2
else
    // data1 == data2

在这种情况下，我认为第二个操作(2)是低效的

因为 0 ~ 8 数据已经 checkin (1)。

所以，我想像这样为比较器使用另一个函数，

const int c_DataSize = 10;

// this is better comparator for this structure ( I think )
// like std::string::compare()
int compare(const SA& lhs_, const SA& rhs_) const
{
    for (int i = 0; i<c_DataSize; ++i)
    {
        if (lhs_.Data[i] < rhs_.Data[i])
            return -1;
        else if (lhs_.Data[i] > rhs_.Data[i])
            return 1;
    }   
    return 0;
}

这个函数可以通过一次执行来检查比较。像这样，

// this is pseudocode
switch(compare(data1, data2))
{
    case -1:
        // data1 < data2
        break;
    case 0:
        // data1 == data2
        break;
    case 1:
        // data1 > data2
        break;
}

我的第一个问题是
我如何使用比较器函数，如 SA::compare()
或者
是否有另一种有效的比较方法(在这种情况下)
或者
我的想法不对吗？

第二个问题是
std::set 是否有效？ (我检查过这没有使用 compare() 函数)
如果不是
还有其他有效的比较方法吗？

在这种情况下(c_DataSize == 10)
我不需要 compare() 函数。
但是，c_DataSize 将大于 100
每天将插入 100000000(或更多)条数据。
所以，我想知道最快的插入方式。

---

非常感谢您回答我的问题。

-------------------------------------- 添加_1 ---------- ------------------------------

这是另一个完整的代码。 (VS2013 版本)(检查运算符(operator)调用计数)

---

#include "stdafx.h"
#include <iostream>
#include <set>

using namespace std;

using TData = __int32;

enum EData
{
    Value1,
    Value2,
    Max
};

struct SData
{
    TData Datas[EData::Max];

    SData()
    {
    }
    SData(const SData& Data_)
    {
        memcpy(Datas, Data_.Datas, Max*sizeof(TData));
    }

    bool operator < (const SData& Data_) const
    {
        cout << "comp" << endl;

        for (int i = 0; i < EData::Max; ++i)
        {
            if (Datas[i] < Data_.Datas[i])
                return true;
            else if (Datas[i] > Data_.Datas[i])
                return false;
        }

        return false;
    }
};

set<SData> Container;

int _tmain(int argc, _TCHAR* argv[])
{
    SData Data;

    Data.Datas[EData::Value1] = 0;
    Data.Datas[EData::Value2] = 0;
    Container.emplace(Data);    // (a)

#if 1
    Data.Datas[EData::Value2] = 1;
    Container.emplace(Data);    // (b1)  called operator < () two times
#else
    Data.Datas[EData::Value2] = -1;
    Container.emplace(Data);    // (b2)  called operator < () one time
#endif

    return 0;
}

---

输出案例发布!!(b1)

comp
comp

输出案例发布!!(b2)

comp

Answer 1

不用担心STL的效率。 std::set 使用 R-B 树，不需要 operation(2)。这是STL R-B树的insert函数的一部分:

while (__x != 0) {
    __y = __x;
    __comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
    __x = __comp ? _S_left(__x) : _S_right(__x);
    }

你可以看到只有一个比较。

至于你的程序，用operator<()就可以了。

对于您添加的问题:

只有当集合在插入前只有一个元素时才会出现这样的输出。这是一种特殊情况，应忽略。