3

正如问题所说，我需要以这种方式使用 std::map 。

std::map<std::pair<int, int>, int*> m;

int* a_ptr = new int;
*a_ptr = 15;
m[std::make_pair(1, 2)] = a_ptr;
std::cout << *m[std::make_pair(2, 1)] << std::endl; //should output 15

现在，在我的实际实现中，所有的键和值实际上都是指针。我应该如何解决这个问题？

我想到了两个想法。

  1. 一个是我应该写一个函数，每次我m[]用来访问或写入地图时，我还应该m.find()检查另一对组合并按照它行事。

  2. 其他是使用带有自定义哈希的 std::unordered_map ，这 在切换元素位置时以某种方式没有区别。pair（我不知道该怎么做，如果我将两个指针相乘或相加，结果将不相等。如果这是要走的路，需要一些帮助。）

如果您能想到更好的方法，我会很高兴听到它，否则我在第二条中说明了我需要帮助的内容。（我认为效率更高，第一个看起来不太好）

谢谢。

4

4 回答 4

7

你能简单地确保这些对总是按相同的顺序排列吗？使用辅助函数，例如：

std::pair<int,int> my_make_pair(int a, int b) 
{
    if ( a < b ) return std::pair<int,int>(a,b);
    else return std::pair<int,int>(b,a);
}

并始终使用它来访问地图：

m[my_make_pair(1,2)] = a_ptr;
std::cout << m[my_make_pair(2, 1)] << std::endl;
于 2013-03-14T21:05:10.833 回答
3

只需使用自定义比较器

[](std::pair<int, int> const& lhs, std::pair<int, int> const& rhs) {
   int lhs_min = std::min(lhs.first, lhs.second);
   int lhs_max = std::max(lhs.first, lhs.second);
   int rhs_min = std::min(rhs.first, rhs.second);
   int rhs_max = std::max(rhs.first, rhs.second);

   return lhs_min < rhs_min || (!(rhs_min < lhs_min) && lhs_max < rhs_max)
}

这是如何运作的？

前几行确定性地对一对中的 2 个元素进行排序；也就是说，您可以按任意顺序提供它们，并且lhs_min&lhs_max将是相同的。然后，我们对结果使用标准等效技术。所有整数副本都将由编译器优化并且min/max将被内联。

请注意，我使用 C++11 的 lambdas 是为了方便输入，但后来发现没有很好的方法可以将它们用作 a 的比较器std::map，因此您必须正确编写一个仿函数。

于 2013-03-14T21:09:59.843 回答
3 
template<typename T, typename PairCmp = std::less<std::pair<T,T>> >
struct symmetric_pair_sort {
  bool operator()( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    if (left.second<left.first) {
      return (*this)(std::make_pair( left.second, left.first ), right );
    }
    if (right.second<right.first) {
      return (*this)(left, std::make_pair( right.second, right.first ) );
    }
    return PairCmp()(left, right);
  }
};

// or, the far bulkier yet more efficient:
template<typename T, typename PairCmp = std::less<std::pair<T&, T&>> >
struct symmetric_pair_sort {
  template<bool left_reversed, bool right_reversed>
  bool Helper( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    std::pair<T&, T&> left_ordered( left_reversed?left.first:left.second, left_reversed?left.second:left.first );
    std::pair<T&, T&> right_ordered( right_reversed?right.first:right.second, right_reversed?right.second:right.first );
    return PairCmp()( left_ordered, right_ordered );
  }
  bool operator()( std::pair<T,T> const& left, std::pair<T,T> const& right ) const {
    if (left.second<left.first) {
      if (right.second<right.first) {
        return Helper<true, true>(left, right);
      } else {
        return Helper<true, false>(left, right);
      }
    } else {
      if (right.second<right.first) {
        return Helper<false, true>(left, right);
      } else {
        return Helper<false, false>(left, right);
      }
  }
};

std::map<std::pair<int, int>, int*, symmetric_pair_sort<int> > m;
于 2013-03-14T21:09:39.937 回答
1

另一种解决方案是使用std::set<int>而不是std::pair<int,int>. 集合存储有序的数据，因此无需订购您的配对，因此准确地满足您的要求。

另一方面，使用明确排序对的比较包装器的其他答案可能更实用。

于 2013-03-14T21:10:13.650 回答