"partial" iterator?

[Hicham Mouline]

Hello,

I have a std::map<std::string, boost::shared_ptr<my_type_t>>.
I often lookup based on the key (std::string)

I have a use case where I want to iterate over all the map except for keys
that begin with "RF".

I could iterate and check if iterator->first.find("RF")==0, then ignore it.

typedef std::map<std::string, boost::shared_ptr<my_type_t>> my_container_t;
my_container_t my_container;
for (my_container_t::const_iterator i=my_container.begin();
i!=my_container.end(); ++i)
if (i->first.first.find("RF")!=0)
//proceed

Is there a better way ? perhaps a smarter iterator that knows to jump over
the RF... entries?

rds,

 

[SG]

Is there a better way ? perhaps a smarter iterator that knows to jump over
the RF... entries?

I don't know if it's "better" but you could check out the filter
iterator template from the Boost Iterator library:

http://www.boost.org/doc/libs/1_44_0/libs/iterator/doc/index.html#specialized-adaptors

Cheers!
sg

 

[Marcel Müller]

I don't know if it's "better" but you could check out the filter
iterator template from the Boost Iterator library:

Depending on how many entries are to be removed from the iteration
another approach might be considerable.

Since map is a sorted container, you might look for lower_bound of "RF"
and once your iterator hits the returned iterator jump to the
lower_bound of "RG". (This assumes that there is nothing in between
"RF*" and "RG" in the sort order.)
This will not even iterate over the unwanted elements, instead you have
two O(log(n)) lookups instead. This is cheap if many elements are to be
skipped.


Marcel

 

[Hicham Mouline]

I don't know if it's "better" but you could check out the filter
iterator template from the Boost Iterator library:

http://www.boost.org/doc/libs/1_44_0/libs/iterator/doc/index.html#specialized-adaptors

Cheers!
sg

great, that is exactly what I need.

after I manually implemented the predicate myself, I encountered a piece of
code that required the std::distance(begin, i).
For that, I had to reimplement the code to do std::distance taking into
account of the unwanted RFs.
with this filter adaptor, it seems I won't have to.

rds,

 

[Pavel]

Hello,

I have a std::map<std::string, boost::shared_ptr<my_type_t>>.
I often lookup based on the key (std::string)

I have a use case where I want to iterate over all the map except for keys
that begin with "RF".

I could iterate and check if iterator->first.find("RF")==0, then ignore it.

typedef std::map<std::string, boost::shared_ptr<my_type_t>> my_container_t;
my_container_t my_container;
for (my_container_t::const_iterator i=my_container.begin();
i!=my_container.end(); ++i)
if (i->first.first.find("RF")!=0)
//proceed

Is there a better way ? perhaps a smarter iterator that knows to jump over
the RF... entries?

rds,

It all depends on your definition of "better". If you are just looking
at saving some typing and clearer code, SG's suggestion seems to be very
good.

If you are concerned with the performance of you use case and it is
important enough for you to sacrifice some memory (and you have
relatively large share of elements starting with "RF"), I would think of
adding a couple of pointers to value_type to your mapped_type and
joining your map values whose keys don't start with 'RF' into an
intrusive list. (For code simplicity, I would probably make them void*
although many here would probably disapprove).

Less involving and taking less memory but slightly slower would be to
change the comparator to pile all "RF" strings at the end of the map --
unless your task requires the natural order for another purpose.

Hope this will help

-Pavel

 

[Marc]

I don't know if it's "better" but you could check out the filter
iterator template from the Boost Iterator library:

[...]
great, that is exactly what I need.

after I manually implemented the predicate myself, I encountered a piece of
code that required the std::distance(begin, i).
For that, I had to reimplement the code to do std::distance taking into
account of the unwanted RFs.
with this filter adaptor, it seems I won't have to.

Hello,

Isn't std::count_if basically equivalent to std::distance on the
filtered iterator, in your case? Not that it matters, once you have
introduced the filtered iterator.