Does Boost has an utility to replace all OLD Keys with NEW one for MultiMap/Map?
Hi Guys, As of now I failed to get such an algo. I've come up with an proposed solution. Please verify: namespace Boost{ template <typename CONTAINER> void replace_key(CONTAINER& container, const typename CONTAINER::key_type& oldKey, const typename CONTAINER::key_type& newKey) { typename CONTAINER::iterator begin(container.find(oldKey)); for(;;){ if(begin != container.end()){ container.insert(typename CONTAINER::value_type(newKey, begin->second)); container.erase(begin++); begin = container.find(oldKey); } else{ return; } } } } make sense?
In the pathological case of newKey == oldKey is there a potential for infinite loop? Either protect against this with a simple compare/return or clearly warn against it in the doc. Paul Rose
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Tushar Chowdhury Sent: Thursday, May 07, 2009 4:10 AM To: boost@lists.boost.org Subject: [boost] Does Boost has an utility to replace all OLD Keys with NEWone for MultiMap/Map?
Hi Guys, As of now I failed to get such an algo. I've come up with an proposed solution. Please verify:
Confidentiality Notice: This email, including attachments, may include non-public, proprietary, confidential or legally privileged information. If you are not an intended recipient or an authorized agent of an intended recipient, you are hereby notified that any dissemination, distribution or copying of the information contained in or transmitted with this e-mail is unauthorized and strictly prohibited. If you have received this email in error, please notify the sender by replying to this message and permanently delete this e-mail, its attachments, and any copies of it immediately – you should not retain, copy or use this e-mail or any attachment for any purpose, nor disclose all or any part of the contents to any other person. Thank you.
The begin++ will leave begin either at end() or at the next equal key or at the following key. You could leave out the 2nd find() and change the if to: if(begin != container.end() && !container.key_comp(oldKey, begin->first)) Which should be a bit more efficient
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Tushar Chowdhury Sent: Thursday, May 07, 2009 4:10 AM To: boost@lists.boost.org Subject: [boost] Does Boost has an utility to replace all OLD Keys with NEWone for MultiMap/Map?
Hi Guys, As of now I failed to get such an algo. I've come up with an proposed solution. Please verify:
Confidentiality Notice: This email, including attachments, may include non-public, proprietary, confidential or legally privileged information. If you are not an intended recipient or an authorized agent of an intended recipient, you are hereby notified that any dissemination, distribution or copying of the information contained in or transmitted with this e-mail is unauthorized and strictly prohibited. If you have received this email in error, please notify the sender by replying to this message and permanently delete this e-mail, its attachments, and any copies of it immediately – you should not retain, copy or use this e-mail or any attachment for any purpose, nor disclose all or any part of the contents to any other person. Thank you.
AMDG Mathias Gaunard wrote:
Tushar Chowdhury wrote:
As of now I failed to get such an algo.
boost::assign(m.equal_range(old_key), new_key); ?
????? boost::assign is a namespace. In Christ, Steven Watanabe
Hi Paul, Steven, Mathias, Thanks a ton guys......... I really appreciate Regards, Tushar On Thu, May 7, 2009 at 8:18 PM, Steven Watanabe <watanabesj@gmail.com>wrote:
AMDG
Mathias Gaunard wrote:
Tushar Chowdhury wrote:
As of now I failed to get such an algo.
boost::assign(m.equal_range(old_key), new_key); ?
?????
boost::assign is a namespace.
In Christ, Steven Watanabe
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Steven Watanabe wrote:
AMDG
Mathias Gaunard wrote:
Tushar Chowdhury wrote:
As of now I failed to get such an algo.
boost::assign(m.equal_range(old_key), new_key); ?
?????
boost::assign is a namespace.
My bad, I meant 'fill', not 'assign'. I confused it with the assign member of containers. boost::fill being just like std::fill but taking a range instead of two iterators. It's in the accepted update to the range library that doesn't seem to be in the trunk yet. Otherwise, you'd have to write std::pair<TheMap::iterator, TheMap::iterator> r = m.equal_range(old_key); std::assign(r.first, r.second, new_key);
Mathias Gaunard wrote:
Steven Watanabe wrote:
AMDG
Mathias Gaunard wrote:
Tushar Chowdhury wrote:
As of now I failed to get such an algo.
boost::assign(m.equal_range(old_key), new_key); ?
?????
boost::assign is a namespace.
My bad, I meant 'fill', not 'assign'. I confused it with the assign member of containers.
I forgot to say that this was this a rough idea, and of course it doesn't work since map iterators are const, and since new_key is not the not the right type anyway. Sorry for the bad advice.
Tushar Chowdhury wrote:
As of now I failed to get such an algo. I've come up with an proposed solution. Please verify:
Hi Tushar, I'm not aware of anything that does this in Boost, though maybe someone who knows more about e.g. Boost.Range can suggest something. To get O((log N) + M) time-complexity (where N is the size of the container and M is the number of affected elements), rather than O(M log N), you need to do something like this: - Get the affected range using std::multimap::equal_range. - Insert new elements using the version of std::multimap::insert that takes an insertion location hint. - Erase the old elements using the version of std::multimap::erase that takes an iterator. You have the choice of either erasing the old elements individually as you go, or erasing them all at the end. I can't say which would be quicker. How about: 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); } Two snags with that: - I'm using the insert hint wrongly, I think. IIRC you need to iterate backwards to get the hint to work. - I'm not convinced that the loop termination is right. If I had elements with keys 1 and 3 and I tried to replace 1 with 2, then the end iterator returned by equal_range would point to the first element with key 3. This would be wrong as soon as a 2 element was inserted. (Does Boost.Range do anything to work around this?) Conveniently, I believe that the same fix (i.e. iterating backwards) solves both. Left as an exercise :-) (Oh, except that the erase would still erase the wrong elements in that case.) Phil.
2009/5/7 Phil Endecott <spam_from_boost_dev@chezphil.org>
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, std::back_inserter(values), 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.
On Thu, May 7, 2009 at 2:05 PM, Duncan Smith <duncanphilipnorman@gmail.com>wrote:
2009/5/7 Phil Endecott <spam_from_boost_dev@chezphil.org>
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, std::back_inserter(values), 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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
wonderful. Thanks guys. On Fri, May 8, 2009 at 10:27 AM, Tushar Chowdhury <tchowdhury80@gmail.com>wrote:
On Thu, May 7, 2009 at 2:05 PM, Duncan Smith <duncanphilipnorman@gmail.com
wrote:
2009/5/7 Phil Endecott <spam_from_boost_dev@chezphil.org>
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, std::back_inserter(values), 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. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (6)
-
Duncan Smith -
Mathias Gaunard -
Paul Rose -
Phil Endecott -
Steven Watanabe -
Tushar Chowdhury