Ладно, давайте приготовимся испачкать руки:)
Я буду использовать std::mismatch и std::transform
Прежде всего, некоторые типы:
typedef std::map<int, double> input_map;
typedef input_map::const_reference const_reference;
typedef input_map::const_iterator const_iterator;
typedef std::pair<const_iterator,const_iterator> const_pair;
typedef std::map<int, std::pair<double,double> > result_map;
Затем предикаты
bool less(const_reference lhs, const_reference rhs)
{
return lhs.first < rhs.first;
}
result_map::value_type pack(const_reference lhs, const_reference rhs)
{
assert(lhs.first == rhs.first);
return std::make_pair(lhs.first, std::make_pair(lhs.second, rhs.second));
}
Теперь главное:
result_map func(input_map const& m1, input_map const& m2)
{
if (m1.empty() || m2.empty()) { return result_map(); }
// mismatch unfortunately only checks one range
// god do I hate those algorithms sometimes...
if (*(--m1.end()) < *(--m2.end()) { return func(m2, m1); }
const_pair current = std::make_pair(m1.begin(), m2.begin()),
end = std::make_pair(m1.end(), m2.end());
result_map result;
// Infamous middle loop, the check is middle-way in the loop
while(true)
{
const_pair next = std::mismatch(p.first, end.first, p.second, less);
std::transform(current.first, next.first, current.second,
std::inserter(result, result.begin()), pack);
// If any of the iterators reached the end, then the loop will stop
if (next.first == end.first || next.second == end.second) { break; }
// Advance the lesser "next"
if (less(*next.first, *next.second)) { ++next.first; }
else { ++next.second; }
current = next;
}
return result;
}
Я считаю это решение довольно элегантным ... несмотря на настройку awkard, так как нам нужно убедиться,диапазон заканчивается быстрее, чем второй из-за mismatch ...
Обратите внимание, что продвижение действительно глупо, мы могли бы делать это специально, пока у нас не будет *next.first.key == *next.second.key, но это усложнит цикл.
Я действительно не нахожу это лучше, чем созданный вручную цикл, хотя ... подумайте:
result_map func2(input_map const& lhs, input_map const& rhs)
{
result_map result;
for (const_iterator lit = lhs.begin(), lend = lhs.end(),
rit = rhs.begin(), rend = rhs.end();
lit != lend && rit != rend;)
{
if (lit->first < rit->first) { ++lit; }
else if (rit->first < lit->first) { ++rit; }
else
{
result[lit->first] = std::make_pair(lit->second, rit->second);
++lit, ++rit;
}
}
return result;
}
Это гораздо более компактно, возможно, более эффективно ... иногда функции, которые вы ищете, не являютсяВ общем достаточно, чтобы быть в STL:)