仅使用键作为比较器来使两个映射相交

发布于 2024-08-10 05:18:48 字数 267 浏览 3 评论 0原文

我有两个地图，我想获得仅使用键作为比较器的两个地图的交集，同时对常见元素的值（例如+/-）进行简单的数学运算

：

map<int, double> m1,m2;
m1[1] = 1.1;
m1[2] = 2.2

m2[2] = 0.1;
m2[4] = 3.3;

交集后我将得到 m3如果我使用减法运算符，它将有对 : (2, 2.1) 。

使用算法库来实现这一点的有效方法是什么？

谢谢。

原文

I have two maps and I would like to get map which is intersection of two using only key as a comparator and in the same time do simple math operation on values of common elements such as +/-

for example :

map<int, double> m1,m2;
m1[1] = 1.1;
m1[2] = 2.2

m2[2] = 0.1;
m2[4] = 3.3;

after intersection i will get m3 which will have pair : (2, 2.1) if I use subtraction operator.

What would be the efficient way to do it using algorithm library?

Thank you.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

海拔太高太耀眼 2024-08-17 05:18:48

我们想在这个函数中执行什么操作？

迭代映射
将具有相同键的值组合起来
将元素添加到映射

然后我们必须考虑除了 std::map 之外还有哪些其他容器适合此模型。您是否想要包含多重映射并使用相同的键组合所有元素（假设不是）？映射不必排序，因此哈希映射也应该可以工作。不幸的是，STL 概念中不存在包含映射和散列映射但不包含多重映射的概念。因此，让我们组成一个：唯一对关联容器。我们的函数应该适用于这两种类型。

template <typename UPAC, // UPAC models Unique Pair Associative Container
          typename BF>   // BF models Binary Function on UPAC::value_type
UPAC combine_upacs(const UPAC& c1, const UPAC& c2, BF func) {
  UPAC result;
  typename UPAC::const_iterator it1 = c1.begin();
  while (it1 != c1.end()) {
    typename UPAC::const_iterator it2 = c2.find(it1->first);
    if (it2 != c2.end())
      result.insert(make_pair(it1->first, func(it1->second,it2->second));
    ++it1;
  }
  return result;
}

现在，如果您担心 std::map 上的 merge_upacs 的运行时间，您可能希望利用映射已排序的事实，并迭代 c1 和 c2。但这是解决问题的最通用的代码。

What operations do we want to perform in this function?

iterate through the maps
combine values that have the same key
add elements to a map

Then we have to consider what other containers besides std::map fit this model. Do you want to include multimaps and combine all elements with the same key (let's assume not)? The map doesn't have to be sorted, so hashmaps should work, too. Unfortunately, there is no STL concept that include maps and hashmaps but not multimaps. So let's make one up: Unique Pair Associative Container. Our function should work on both types.

template <typename UPAC, // UPAC models Unique Pair Associative Container
          typename BF>   // BF models Binary Function on UPAC::value_type
UPAC combine_upacs(const UPAC& c1, const UPAC& c2, BF func) {
  UPAC result;
  typename UPAC::const_iterator it1 = c1.begin();
  while (it1 != c1.end()) {
    typename UPAC::const_iterator it2 = c2.find(it1->first);
    if (it2 != c2.end())
      result.insert(make_pair(it1->first, func(it1->second,it2->second));
    ++it1;
  }
  return result;
}

Now, if you are concerned about the running time of combine_upacs on std::map, you may want to take advantage of the fact that maps are sorted, and iterate through both c1 and c2. But this is the most general code that solves the problem.

回复收藏 0 原文

夏至、离别 2024-08-17 05:18:48

你可以分两步完成。第一个是找到交集，可以使用 set_intersection 算法来完成。第二步将使用 transform 算法使用提供的函子进行数学运算。

我发现 set_intersection 不允许提供访问函子，因此在下面的代码中有一个惰性替换。我写了一个示例函子，可以为您做减法。我相信您可以轻松编写所有其他函子。您还可以编写与 set_intersection 相同的模板函数，但允许提供将取消引用迭代器的函子。

// sample functor for substruction
template<typename T1, typename T2>
struct sub
{
  // it will be better to use const references, but then you'll not be able
  // to use operator[], and should be use `find` instead 
  sub( std::map<T1, T2>& m1, std::map<T1, T2>& m2 ) : m1(m1), m2(m2) {}
  std::pair<T1,T2> operator()( const T1& index )
  { return make_pair( index, m1[index]-m2[index] ); }    
private:
  std::map<T1, T2>& m1, & m2;
};

int main()
{
 map<int, double> m1,m2;
 m1[1] = 1.1;
 m1[2] = 2.2;

 m2[2] = 0.1;
 m2[4] = 3.3;

 vector<int> v; // here we will keep intersection indexes

 // set_intersection replacement
 // should be moved to stand alone function
 map<int, double>::const_iterator begin1 = m1.begin();
 map<int, double>::const_iterator begin2 = m2.begin();
 for (; begin1 != m1.end() && begin2 != m2.end(); ) {
  if ( begin1->first < begin2->first ) ++begin1;
  else if (begin2->first < begin1->first) ++begin2;
  else v.push_back( begin1->first ), ++begin1, ++begin2;
 }

 map<int, double> m3;
 transform( v.begin(), v.end(), std::inserter(m3, m3.begin()), sub<int, double>( m1, m2 ) );
}

You could do it in two steps. First one is to find intersection, it could be done using set_intersection algorithm. Second step will be using transform algorithm to do math operations using supplied functor.

I've found that set_intersection doesn't allow to supply access functor, so in the following code there is a lazy replacement for it. I wrote a sample functor that will do subtraction for you. I believe that you can easily write all other functors. Also you can write template function that will do the same as set_intersection do, but with allowing to supply functor that will dereference iterator.

// sample functor for substruction
template<typename T1, typename T2>
struct sub
{
  // it will be better to use const references, but then you'll not be able
  // to use operator[], and should be use `find` instead 
  sub( std::map<T1, T2>& m1, std::map<T1, T2>& m2 ) : m1(m1), m2(m2) {}
  std::pair<T1,T2> operator()( const T1& index )
  { return make_pair( index, m1[index]-m2[index] ); }    
private:
  std::map<T1, T2>& m1, & m2;
};

int main()
{
 map<int, double> m1,m2;
 m1[1] = 1.1;
 m1[2] = 2.2;

 m2[2] = 0.1;
 m2[4] = 3.3;

 vector<int> v; // here we will keep intersection indexes

 // set_intersection replacement
 // should be moved to stand alone function
 map<int, double>::const_iterator begin1 = m1.begin();
 map<int, double>::const_iterator begin2 = m2.begin();
 for (; begin1 != m1.end() && begin2 != m2.end(); ) {
  if ( begin1->first < begin2->first ) ++begin1;
  else if (begin2->first < begin1->first) ++begin2;
  else v.push_back( begin1->first ), ++begin1, ++begin2;
 }

 map<int, double> m3;
 transform( v.begin(), v.end(), std::inserter(m3, m3.begin()), sub<int, double>( m1, m2 ) );
}

回复收藏 0 原文

情绪失控 2024-08-17 05:18:48

我不知道执行此操作的标准算法，但编写一个很简单。这适用于有序和无序地图。

  template <class MapT, typename OperationT>
  void intersect_maps(const MapT &map1, const MapT &map2, MapT &target, OperationT op) {
  const MapT *m1, *m2;
  // Pick the smaller map to iterate over
  if (map1.size() < map2.size()) {
    m1 = &map1;
    m2 = &map2;
  } else {
    m1 = &map2;
    m2 = &map1;
  }
  typename MapT::const_iterator it_end = m1->end();
  for (typename MapT::const_iterator it = m1->begin(); it != it_end; ++it) {
    typename MapT::const_iterator pos = m2->find(it->first);
    if (pos != m2->end()) {
      if (m1 == &map1) {
        target.insert(typename MapT::value_type(it->first, op(it->second, pos->second)));
      } else {
        // we swapped the inputs so we need to swap the operands
        target.insert(typename MapT::value_type(it->first, op(pos->second, it->second)));
      }
    }
  }
}

double sub(double v1, double v2) {
  return v1 - v2;
}

// And use it.    
m1[1] = 1.1;
m1[2] = 2.2;

m2[2] = 0.1;
m2[4] = 3.3;

intersect_maps(m1, m2, m3, sub);

I don't know of a standard algorithm to do this, but it is simple to write one. This will work for both ordered and un-ordered maps.

  template <class MapT, typename OperationT>
  void intersect_maps(const MapT &map1, const MapT &map2, MapT &target, OperationT op) {
  const MapT *m1, *m2;
  // Pick the smaller map to iterate over
  if (map1.size() < map2.size()) {
    m1 = &map1;
    m2 = &map2;
  } else {
    m1 = &map2;
    m2 = &map1;
  }
  typename MapT::const_iterator it_end = m1->end();
  for (typename MapT::const_iterator it = m1->begin(); it != it_end; ++it) {
    typename MapT::const_iterator pos = m2->find(it->first);
    if (pos != m2->end()) {
      if (m1 == &map1) {
        target.insert(typename MapT::value_type(it->first, op(it->second, pos->second)));
      } else {
        // we swapped the inputs so we need to swap the operands
        target.insert(typename MapT::value_type(it->first, op(pos->second, it->second)));
      }
    }
  }
}

double sub(double v1, double v2) {
  return v1 - v2;
}

// And use it.    
m1[1] = 1.1;
m1[2] = 2.2;

m2[2] = 0.1;
m2[4] = 3.3;

intersect_maps(m1, m2, m3, sub);

回复收藏 0 原文

~没有更多了~