C++具有类键和类值的 STL 映射容器

Question

所以假设我有一个像这样的类：

class Point
{
   private:
      int x, y;
   public:
      void setX(int arg_x) { x = arg_x; }
      void sety(int arg_y) { y = arg_y; }
      int getX() const { return x; }
      int gety() const { return y; }
};

现在我想要一个像这样的地图：

map<Point, Point> m;

但我需要第三个参数。我在cplusplus中读到第三个参数是比较某些东西，但我不明白那东西是什么。谁能为我解释一下吗？

Answer 1

如果您不需要单独的比较函数，您可以使用这样的方法扩展您的类。

class Point
{
   private:
      int x, y;
   public:

      bool operator<( const Point& other) const
      {
          if ( x == other.x )
          {
              return y < other.y;
          }

          return x < other.x;
      }
};

默认情况下，stl 映射通过某种排序概念对其中的所有元素进行排序。在这种情况下，使用该运算符。有时您无法控制 Point 类，或者您可能希望在两个不同的地图中使用它，每个地图都定义自己的顺序。例如，一张地图可能首先按 x 对点进行排序，而另一张地图可能首先按 y 排序。因此，如果比较运算符独立于 Point 类，可能会有所帮助。你可以做这样的事情。

class Point
{
   public:
      int x, y;
};


struct PointComparer
{
    bool operator()( const Point& first , const Point& second) const
    {
        if ( first.x == second.x )
        {
            return first.y < second.y;
        }

        return first.x < second.x;
    }
};

map<Point, Point , PointComparer> m;

Answer 2

您需要定义 Point 项目的排序。

这可以通过不同的方式完成：

为 Point 重载 运算符 <

您可以提供 < 运算符的重载，其原型为：

bool operator < (const Point & p_lhs, const Point & p_rhs) ;

例如，对于我的测试，我使用了以下一种：

bool operator < (const Point & p_lhs, const Point & p_rhs)
{
    if(p_lhs.getX() < p_rhs.getX()) { return true ; }
    if(p_lhs.getX() > p_rhs.getX()) { return false ; }
    return (p_lhs.getY() < p_rhs.getY()) ;
}

这是最简单的方法，但它在语义上假设上面定义的顺序是正确的默认顺序。

提供函子

如果您不愿意提供 < 运算符，或者想要拥有多个映射，每个映射都有自己的顺序，那么您的解决方案是为映射提供一个函子。这是为映射定义的第三个模板参数：

template < class Key, class T, class Compare = less<Key>,
       class Allocator = allocator<pair<const Key,T> > > class map;

函子必须具有以下签名：

struct MyCompareFunctor
{
    bool operator() (const Point & p_lhs, const Point & p_rhs)
    {
       // the code for comparison
    }
} ;

因此，对于我的测试，我只编写了以下内容：

struct MyCompare
{
    bool operator() (const Point & p_lhs, const Point & p_rhs)
    {
        if(p_lhs.getX() > p_rhs.getX()) { return true ; }
        if(p_lhs.getX() < p_rhs.getX()) { return false ; }
        return (p_lhs.getY() > p_rhs.getY()) ;
    }
} ;

并在我的映射中使用了它：

std::map<Point, Point, MyCompare> map ;

Et voilà...

专门化 std::less 为 Point

我认为这样做没有意义，但知道总是好的：您可以专门化 std::less > 适合您的模板结构Point 类

#include <functional>

namespace std
{
    template<>
    struct less<Point> : binary_function <Point,Point,bool>
    {
        bool operator() (const Point & p_lhs, const Point & p_rhs)
        {
            if(p_lhs.getX() < p_rhs.getX()) { return true ; }
            if(p_lhs.getX() > p_rhs.getX()) { return false ; }
            return (p_lhs.getY() < p_rhs.getY()) ;
        }
    } ;
}

至少就地图而言，这与重载运算符 < 具有相同的效果。

至于上面的运算符 < 解决方案，从语义上来说，该解决方案假设上面定义的顺序对于 std:less 而言是正确的默认顺序。

请注意，默认的 std::less 实现调用 is 模板化类型的运算符 <。一个给出与另一个不同的结果可能被视为语义错误。

Answer 3

当您使用用户定义的类作为 std::map 中的键时，为了确定元素在容器中的位置，地图需要 Comparison 类：该类接受两个键类型参数并返回 bool。

它基本上是一个比较函子/函数，用于比较两个键值。

Answer 4

您不需要第三个参数，只需要 operator== 和 operator<

bool operator<(const Point& other) const{
      if ( x == other.x )
          return y < other.y;
      return x < other.x;
}
bool operator==(const Point& other) const{
      return x == other.x && y == other.y;
}

Answer 5

我认为上面的代码对 @parapura rajkumar 的解决方案进行了一些升级。

class Point{

    private:
        int x, y;

    public:
        bool operator<( const Point& other) const{
            return ((x < other.x) || (y < other.y));
        }
};

Answer 6

你所说的第三个参数在STL中被称为“比较器”。
对于默认类型作为键，您不需要提供一个作为编译器
为你做这项工作。
但是对于您定义的类型，您必须提供它，否则编译器将如何维护
地图/集合等中的排序顺序。