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

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::v开发者_如何学运维ector<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 take a const_iterator, but std::find() requires one. I could cast away the const-ness of the iterator returned by std::find() when feeding it to std::vector::erase(), but Effective C++ taught me to regard const_cast with suspicion.

Is there another way to do this? I can't believe that something as common as removing an element from a vector should require type gymnastics. :)

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

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

Also, you're not technically supposed to prefix names with an underscore, as this is reserved for implementations. (it will generally work in practice)

Aside from my direct modification of the code, here's an idea:

Instead of a member function _iterator_for_node which

• has const issues
• is uselessly tightly bound to a particular container type (inducing a typename template resolution mess)
• does nothing more than std::find and throw an exception if not found

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

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 iterator type (including non-STL, input stream iterators, forward only, const, reverse iterators... you name it) and it doesn't require explicit distinction between const/non const versions :)

With it,

a working version of your code sample 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)); }
};

Note the code reduction. Always the good sign

Cheers

There seems to be quite some confusion between const elements, and const iterators in your code.

Without looking in to the use case, I propose the following 'fix' to make things compile:

#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);
}