Boost logo

Boost :

Subject: Re: [boost] Does Boost has an utility to replace all OLD Keys with NEW one for MultiMap/Map?
From: Duncan Smith (duncanphilipnorman_at_[hidden])
Date: 2009-05-07 14:05:47

2009/5/7 Phil Endecott <spam_from_boost_dev_at_[hidden]>
> template <typename CONT>
> void replace_key(CONT& cont, typename CONT::key_type oldk, typenamme CONT::key_type newk)
> {
>  if (newk==oldk) return;
>  typedef typename CONT::iterator iter;
>  std::pair<iter,iter> r = cont::equal_range(oldk);
>  iter hint = cont.begin();
>  for (iter i = r.first; i != r.second; ++r) {
>    hint = cont.insert(hint,std::make_pair(newk,i->second));
>  }
>  cont.erase(r.first,r.second);
> }
As Phil mentioned, the range returned from 'equal_range()' will
expand when you do 'cont.insert()' if the oldk < newk < (the next key
larger than oldk), causing an infinite loop during insertion. Then,
both sets of keys will get erased with 'erase()'.

The easiest way to do this robustly is with temporary storage:

#include <algorithm>
#include <boost/bind.hpp>
#include <boost/ref.hpp>
#include <utility>
#include <vector>

template <typename Container>
void replace_key(Container &c, typename Container::key_type oldKey,
typename Container::key_type newKey)
  if (oldKey != newKey) {
    typedef typename Container::iterator iterator;
    typedef typename Container::value_type value_type;
    typedef typename Container::key_type key_type;
    typedef typename Container::mapped_type mapped_type;
    using ::std::make_pair;
    using ::std::vector;
    using ::boost::bind;
    using ::boost::cref;
    using ::std::transform;

    std::pair<iterator, iterator> range = c.equal_range(oldKey);
    std::vector<mapped_type> values;
    transform(range.first, range.second,
      bind(&value_type::second, _1));

    c.erase(range.first, range.second);

    transform(values.begin(), values.end(),
      std::inserter(c, c.end()),
      bind(make_pair<key_type, mapped_type>, cref(newKey), _1));

There are more efficient implementations, but this should do it.

Boost list run by bdawes at, gregod at, cpdaniel at, john at