How can I avoid using const_cast with std :: vector :: erase () in C ++?

Question

I have a class like this:

template<class T> class AdjacencyList { public: void delete_node(const T&); protected: const typename std::vector<T>::const_iterator _iterator_for_node( const std::vector<T>&, const T& ); }; template<class T> void AdjacencyList<T>::delete_node(const T& node) { _nodes.erase(_iterator_for_node(_nodes, node)); } template<class T> const typename std::vector<T>::const_iterator AdjacencyList<T>::_iterator_for_node( const std::vector<T>& list, const T& node ) { typename std::vector<T>::const_iterator iter = std::find(list.begin(), list.end(), node); if (iter != list.end()) return iter; throw NoSuchNodeException(); } 

Apparently std::vector::erase() cannot accept const_iterator , but std::find() requires it. I could discard the const -ness of the iterator returned by std::find() when it was loaded into std::vector::erase() , but Efficient C ++ taught me to consider const_cast suspicious.

Is there any other way to do this? I can’t believe that something in common, like removing an element from a vector, should require a type of gymnastics. :)

Answer 1

Besides my direct code modification , here is an idea:

Instead of the _iterator_for_node member _iterator_for_node , which

• has communication problems
• uselessly closely associated with a specific type of container (causing confusion over the resolution of the template template)
• does nothing but std :: find and throws an exception if not found

I suggest creating the following static (global / spatial) function:

 template<class It, class T> It checked_find(It begin, It end, const T& node) { It iter = std::find(begin, end, node); if (iter != end) return iter; throw NoSuchNodeException(); } 

It will work with any type of iterator (including non-STL, input stream iterators, forward only, const, reverse iterators ... you name it), and this does not require a clear distinction between const / non const :)

With his help

the working version of your sample code would just read

 template<class T> class AdjacencyList { std::vector<T> _nodes; public: void delete_node(const T& node) { _nodes.erase(checked_find(_nodes.begin(), _nodes.end(), node)); } }; 

Pay attention to the code abbreviation. Always a good sign

Greetings

Answer 2

I suggest you change or overload the _iterator_for_node() function to accept a non-constant link to the list. The reason std::find returns a const_iterator , because the list itself is const , and therefore begin() and end() return const_iterator s.

As an aside, const_cast<> does not actually convert const_iterator to iterator , since 'const' is just part of the name, not a CV qualifier.

Also, you technically do not need prefix names with underscores, as this is reserved for implementations. (usually it will work in practice)

Answer 3

There seems to be some confusion between constant elements and constant iterators in your code.

Without resorting to a use case, I suggest the following “fix” for compilation:

 #include <algorithm> #include <vector> #include <iostream> using namespace std; struct NoSuchNodeException {}; template<class T> class AdjacencyList { std::vector<T> _nodes; public: void delete_node(const T&); protected: typename std::vector<T>::iterator _iterator_for_node(std::vector<T>&, const T&); typename std::vector<T>::const_iterator _iterator_for_node(const std::vector<T>&, const T&) const; }; template<class T> void AdjacencyList<T>::delete_node(const T& node) { _nodes.erase(_iterator_for_node(_nodes, node)); } template<class T> typename std::vector<T>::iterator AdjacencyList<T>::_iterator_for_node(std::vector<T>& list, const T& node) { typename std::vector<T>::iterator iter = std::find(list.begin(), list.end(), node); if (iter != list.end()) return iter; throw NoSuchNodeException(); } template<class T> typename std::vector<T>::const_iterator AdjacencyList<T>::_iterator_for_node(const std::vector<T>& list, const T& node) const { typename std::vector<T>::const_iterator iter = std::find(list.begin(), list.end(), node); if (iter != list.end()) return iter; throw NoSuchNodeException(); } int main() { AdjacencyList<int> test; test.delete_node(5); }