Is there a better way to write:
for (auto i = container.begin(); i != container.end();)
{
if (condition(i))
{
i = container.erase(i);
continue;
}
++i;
}
This code does what I want, but it feels like bad style.
How can I improve it?
My container is std::map, but a generic solution would be cool.
Use erase + remove_if:
auto pred = /* lambda or something*/
container.erase(std::remove_if(container.begin(),
container.end(),
pred)
Is there a better way to...?
It is always subjective, but one way is a traits-based template function suite with a consistent interface, using tag-dispatching to choose the most optimal algorithm depending on the container type...
The interface function could look like this:
template<class Range, class Pred>
Range& erase_if(Range& range, Pred&& pred)
{
erase_if(typename detail::range_traits<std::decay_t<Range>>::idiom_type(),
range, std::forward<Pred>(pred));
return range;
}
which defers to the correct idiom for the container type...
void erase_if(erase_remove_idiom, Vector& vec, Pred pred)
{
vec.erase(std::remove_if(std::begin(vec), std::end(vec),
std::forward<Pred>(pred)),
std::end(vec));
}
template<class Maplike, class Pred>
void erase_if(equal_range_idiom, Maplike& map, Pred pred)
{
auto first = std::begin(map);
auto last = std::end(map);
while (first != last) {
auto& item = *first;
auto& key = get_key(item);
auto range = map.equal_range(key);
if (pred(key)) {
map.erase(range.first, range.second);
}
first = range.second;
}
}
template<class Maplike, class Pred>
void erase_if(map_crawl_idiom, Maplike& map, Pred pred)
{
for (auto i = map.begin(); i != map.end();)
{
i = pred(*i) ? map.erase(i) : std::next(i);
}
}
Here's the complete code and some tests.
Writing code like this always makes me feel admiration for std-library maintainers. So many corner cases...
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>
#include <unordered_set>
#include <map>
namespace detail {
// The general concept of range_traits
template<class Range>
struct range_traits
{
};
// Tag for performing erase-remove on vector-like containers
struct erase_remove_idiom {};
// Using equal-range to skip redundant comparisons in multiset-like-containers
struct equal_range_idiom {};
// Crawling through maps...
struct map_crawl_idiom {};
template<class V, class A>
struct range_traits<std::vector<V, A>> {
using idiom_type = erase_remove_idiom;
};
template<class V, class C, class A>
struct range_traits<std::multiset<V, C, A>> {
using idiom_type = equal_range_idiom;
};
template<class V, class C, class A>
struct range_traits<std::set<V, C, A>> {
using idiom_type = map_crawl_idiom;
};
template<class V, class C, class H, class A>
struct range_traits<std::unordered_set<V, C, H, A>> {
using idiom_type = map_crawl_idiom;
};
template<class V, class C, class H, class A>
struct range_traits<std::unordered_multiset<V, C, H, A>> {
using idiom_type = equal_range_idiom;
};
template<class K, class V, class C, class A>
struct range_traits<std::multimap<K, V, C, A>> {
using idiom_type = map_crawl_idiom;
};
template<class K, class V, class C, class A>
struct range_traits<std::map<K, V, C, A>> {
using idiom_type = map_crawl_idiom;
};
}
namespace detail {
template<class Vector, class Pred>
void erase_if(erase_remove_idiom, Vector& vec, Pred pred)
{
vec.erase(std::remove_if(std::begin(vec), std::end(vec),
std::forward<Pred>(pred)),
std::end(vec));
}
// Generalised key-getter for sets
template<class V>
V& get_key(V& v) {
return v;
}
// Specialised key-getter for maps
template<class K, class V>
const K& get_key(std::pair<const K, V>& p) {
return p.first;
}
template<class Maplike, class Pred>
void erase_if(equal_range_idiom, Maplike& map, Pred pred)
{
auto first = std::begin(map);
auto last = std::end(map);
while (first != last) {
auto& item = *first;
auto& key = get_key(item);
auto range = map.equal_range(key);
if (pred(key)) {
map.erase(range.first, range.second);
}
first = range.second;
}
}
template<class Maplike, class Pred>
void erase_if(map_crawl_idiom, Maplike& map, Pred pred)
{
for (auto i = map.begin(); i != map.end();)
{
i = pred(*i) ? map.erase(i) : std::next(i);
}
}
}
//
// The interface function
//
template<class Range, class Pred>
Range& erase_if(Range& range, Pred&& pred)
{
erase_if(typename detail::range_traits<std::decay_t<Range>>::idiom_type(),
range, std::forward<Pred>(pred));
return range;
}
template<class T>
struct emitter
{
void operator()(std::ostream& os, const T& t) const {
os << t;
}
};
template<class K, class V>
struct emitter<std::pair<const K, V>>
{
void operator()(std::ostream& os, const std::pair<const K, V>& p) const {
os << "(" << p.first << ", " << p.second << ")";
}
};
template<class Range>
void dump(Range& range)
{
auto sep = "";
auto e = emitter<typename std::decay_t<Range>::value_type> {};
for (auto& item : range) {
std::cout << sep;
e(std::cout, item);
sep = ", ";
}
std::cout << std::endl;
}
//
// Test on various containers
//
int main()
{
std::vector<int> some { 1,0,1,0,1,0,1,0 };
std::multiset<int> some_mset { 1,0,1,0,1,0,1,0 };
std::unordered_multiset<int> some_umset { some_mset.begin(), some_mset.end() };
std::map<int, std::string> some_map {
{ 1, "mouse" },
{ 2, "house" },
{ 3, "mouth" }
};
std::multimap<int, std::string> some_mmap(some_map.begin(), some_map.end());
some_mmap.insert(some_map.begin(), some_map.end());
std::set<int> some_set { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
auto is_one = [](auto& x) { return x == 1; };
auto is_even = [](auto&x) { return (x % 2) == 0; };
auto value_starts_with_m = [](auto& item) { return item.second.substr(0,1) == "m"; };
dump(erase_if(some, is_one));
dump(erase_if(some_mset, is_one));
dump(erase_if(some_umset, is_one));
dump(erase_if(some_map, value_starts_with_m));
dump(erase_if(some_mmap, value_starts_with_m));
dump(erase_if(some_set, is_even));
}
Expected results:
0, 0, 0, 0
0, 0, 0, 0
0, 0, 0, 0
(2, house)
(2, house), (2, house)
1, 3, 5, 7, 9
All of these questions and comments are quaint, but they don't address the original question.
What was asked is, how does one tighten up the following:
for( i = ...; some_condition( i ); ) {
if( another_condition( i ) ) {
erase( i );
continue;
}
i++;
}
And the answer is:
for( i = ...; some_condition( i ); i++ ) {
if( another_condition( i ) ) {
erase( i );
}
}
