Casting STL's const_iterator to iterator

[Nick Overdijk]

How would I cast a const_iterator to a normal iterator? For example:

template <typename T1, typename T2>
typename multimap<T1, T2>::iterator &get_indexed_it(const
multimap<T1, T2> &container, const T1 &key, size_t index = 0) const
throw (out_of_range) {
size_t count = container.count(key);

if (count != 0 && count-1 >= index) {
typename multimap<T1, T2>::const_iterator it =
container.find(key);
while (index--) it++;
return const_cast<typename multimap<T1, T2>::iterator&>
(it);
} else {
throw out_of_range((string)"get_indexed_it->"+"Element
" + key + "doesn't exist!");
}
}

MinGW GCC on compiling says:
D:\MyDocs\Code\SSSParser\sss.hpp|155|error: invalid const_cast from type
`std::_Rb_tree_const_iterator<std:air<const std::string, sss::node> >'
to type `std::_Rb_tree_iterator<std:air<const std::string, sss::node> >&'|

I'm guessing this is because const_iterator isn't the same as const
iterator, how else would I accomplish this?

Thanks in Advance,

 

[Nick Overdijk]

How would I cast a const_iterator to a normal iterator? For example:

template <typename T1, typename T2>
typename multimap<T1, T2>::iterator &get_indexed_it(const
multimap<T1, T2> &container, const T1 &key, size_t index = 0) const
throw (out_of_range) {
size_t count = container.count(key);

if (count != 0 && count-1 >= index) {
typename multimap<T1, T2>::const_iterator it =
container.find(key);
while (index--) it++;
return const_cast<typename multimap<T1, T2>::iterator&>
(it);
} else {
throw out_of_range((string)"get_indexed_it->"+"Element "
+ key + "doesn't exist!");
}
}

MinGW GCC on compiling says:
D:\MyDocs\Code\SSSParser\sss.hpp|155|error: invalid const_cast from type


I'm guessing this is because const_iterator isn't the same as const
iterator, how else would I accomplish this?

Thanks in Advance,

Err, sorry guys. It's explained here:
http://www.ddj.com/cpp/184401406

"Observe that there is no way to get from a const_iterator to an
iterator or from a const_reverse_iterator to a reverse_iterator. This is
important, because it means that if you have a const_iterator or a
const_reverse_iterator, you’ll find it difficult to use those iterators
with some container member functions."

I'm guessing if that guys says so, it kinda is. xD

 

[joshuamaurice]

How would I cast a const_iterator to a normal iterator?

You don't.

The function you posted, it appears that it's a member function of
some class, judging from the const modifier on the function, but I
don't see any member accesses of the this object. This is odd.

Also, the function breaks const correctness.
typename multimap<T1, T2>::iterator&
get_indexed_it(
const multimap<T1, T2> &container,
const T1 &key, size_t index = 0
) const throw (out_of_range) {
You take in a reference to const container, but you return a non-const
iterator. This would allow someone to inadvertently change the
container when given only a pointer to const, aka break const
correctness. std::multimap is well designed. It follows const
correctness. Thus the compiler will catch all cases of breaking const
correctness (unless silenced with a cast). You should consider this
warning as something you should be concerned about instead of trying
to find ways around it.

Finally, there may be some way around it, like calculating the
difference between begin and end of your const_iterator, casting away
constness from the container, getting a pointer to begin, and
increment the difference. (Aka slow and expensive and costly.)
Otherwise, I think because of the opaque nature of the types, there's
no portable way to do what you want (without the expensive overhead of
iterating from begin), at least I think. I could be wrong on that
specific point.

 

[Nick Overdijk]

You don't.

The function you posted, it appears that it's a member function of
some class, judging from the const modifier on the function, but I
don't see any member accesses of the this object. This is odd.

Yes, member of a function, but indeed no need for it. xD Thanks for
that. I'll place it outside the class.

Also, the function breaks const correctness.
typename multimap<T1, T2>::iterator&
get_indexed_it(
const multimap<T1, T2> &container,
const T1 &key, size_t index = 0
) const throw (out_of_range) {
You take in a reference to const container, but you return a non-const
iterator. This would allow someone to inadvertently change the
container when given only a pointer to const, aka break const
correctness. std::multimap is well designed. It follows const
correctness. Thus the compiler will catch all cases of breaking const
correctness (unless silenced with a cast). You should consider this
warning as something you should be concerned about instead of trying
to find ways around it.

Yes, but it's a private function, sorry for not mentioning it. I have
another function that works like that, but I'll place it outside the
function to. Nevertheless, it also returns a non-const reference to an
element of an element of a multimap, I use it like this:

template <typename T1, typename T2>
T2& get_indexed(const multimap<T1, T2> &container, const T1
&key, size_t index = 0) const throw (out_of_range) {
size_t count = container.count(key);

if (count != 0 && count-1 >= index) {
typename multimap<T1, T2>::const_iterator it =
container.find(key);
while (index--) it++;
return const_cast<T2&>(it->second);
} else {
throw out_of_range((string)"get_indexed->"+"Element " +
key + "doesn't exist!");
}
}

const node &node::getChild(const string &name, size_t index) const throw
(out_of_range) {
return get_indexed<string, node>(children, name, index);
}

node &node::getChild(const string &name, size_t index) throw
(out_of_range) {
return get_indexed<string, node>(children, name, index);
}

These two are public functions. This way getChild can be called on const
objects as well. There's probably a better way to do this, but I could
only come up with this one. get_indexed needed to be const for the
getChild() const to work. And in get_indexed IS const (as in, doesn't
alter the object), but that didn't allowed getChild() non-const to work,
so this was my workaround. xD

Finally, there may be some way around it, like calculating the
difference between begin and end of your const_iterator, casting away
constness from the container, getting a pointer to begin, and
increment the difference. (Aka slow and expensive and costly.)
Otherwise, I think because of the opaque nature of the types, there's
no portable way to do what you want (without the expensive overhead of
iterating from begin), at least I think. I could be wrong on that
specific point.

The article linked earlier states it depends on the iterator, if it's
random or errr.. "++ only"... can't come up with the correct word.

 

[Nick Overdijk]

The two obvious solutions for solving your problem:

template <typename T1, typename T2>
typename multimap<T1, T2>::const_iterator get_indexed_it(
const multimap<T1, T2>& container,
const T1& key,
size_t index = 0) throw (out_of_range)
{
size_t count = container.count(key);
if (count != 0 && count - 1 >= index) {
typename multimap<T1, T2>::const_iterator it = container.find(key);
while (index--)
it++;
return it;
} else {
throw out_of_range((string)"get_indexed_it->" + "Element"
+ key + "doesn't exist!");
}
}

or

template <typename T1, typename T2>
typename multimap<T1, T2>::iterator get_indexed_it(
multimap<T1, T2>& container,
const T1& key,
size_t index = 0) throw (out_of_range)
{
size_t count = container.count(key);
if (count != 0 && count - 1 >= index) {
typename multimap<T1, T2>::iterator it = container.find(key);
while (index--)
it++;
return it;
} else {
throw out_of_range((string)"get_indexed_it->" + "Element"
+ key + "doesn't exist!");
}
}

A couple of comments about your code (and the two 'solutions' above.)

a) Returning a reference (either a reference to const_iterator or a
reference to iterator,) doesn't make much sense to me; iterators are
light weight and designed to be passed around by value.

I'll do so now and in the future, thanks.

b) If T1 is not a string (or some user defined type designed to work as
a string,) your code won't compile. Why not just make it a string?

Yeah, that didn't make sense

Writing it more like this:

template <typename Container, typename T>
typename Container::iterator& get_indexed_it(Container& container, const
T& key, size_t index = 0) throw (out_of_range)
{
if (container.count(key) <= index )
throw out_of_range("get_indexed_it(Container&, const T&, size_t)");

typename Container::iterator result = container.find(key);
advance(result, index);
return result;
}

a) Allows it to be used with maps, sets and multisets, as well as
multimaps.
b) Allows it to work even if 'key' is not a string like object.
c) (arguably) better expresses the intent of the code.

Better still would be to find some way to cleanly write the function
without having to do the search twice (once for count, and once for
find):

template <typename Container, typename T>
typename Container::iterator& get_indexed_it(
Container& container,
const T& key,
size_t index = 0) throw (out_of_range)
{
pair<typename Container::iterator, typename Container::iterator>
range = container.equal_range(key);
if (distance(range.first, range.second) <= index)
throw out_of_range("get_indexed_it(Container&, const T&, size_t)");

advance(range.first, index);
return range.first;
}

Just some thoughts.

That's some nice code man! I didn't know about those advance() and
distance() functions. Still learning the STL. Thanks a lot

 

[Nick Overdijk]

Better still would be to find some way to cleanly write the function
Hmz, that function still has a bit overhead though. I think this
function has the "littlest" overhead:

template <typename Container, typename T>
typename Container::iterator get_indexed_it2(
Container& container,
const T& key,
size_t index = 0) throw (out_of_range) {
//get the first
typename Container::iterator it = container.find(key);
//iterate over it, doing advance() and distance() in one
while (index-- && it->first==key && it != container.end()) it++;
//IF we went too far.
if (it == container.end()) throw
out_of_range("get_indexed_it(Container&, const T&, size_t)");
//else we're goooood
return it;
}

 

[Nick Overdijk]

Hmz, that function still has a bit overhead though. I think this
function has the "littlest" overhead:

template <typename Container, typename T>
typename Container::iterator get_indexed_it2(
Container& container,
const T& key,
size_t index = 0) throw (out_of_range) {
//get the first
typename Container::iterator it = container.find(key);
//iterate over it, doing advance() and distance() in one
while (index-- && it->first==key && it != container.end()) it++;
//IF we went too far.
if (it == container.end()) throw
out_of_range("get_indexed_it(Container&, const T&, size_t)");
//else we're goooood
return it;
}

Oh dear, sorry for that. Potential error on line while(...)

Should be:
while (index-- && it != container.end() && it->first==key) it++;

Missed that in the tests. ;-)