no viable conversion from returned value of type const_iterator to iterator

Question

Inspired by Antony's Williams "C++ Concurrency in Action" I wanted to take a closed look at his thread safe hash map. I copied its code and added some output operators and this is what I came up with:

#include <boost/thread/shared_mutex.hpp>
#include <functional>
#include <list>
#include <mutex>
#include <iostream>

template <typename Key, typename Value, typename Hash = std::hash<Key>>
class thread_safe_hashmap
{
private:
  class bucket_type
  {
  public:
    typedef std::pair<Key, Value> bucket_value;
    typedef std::list<bucket_value> bucket_data;
    typedef typename bucket_data::iterator bucket_iterator;

    bucket_data data;
    mutable boost::shared_mutex mutex;

    bucket_iterator find_entry_for(const Key& key) const
    {
      return std::find_if(data.begin(), data.end(),
                          [&](const bucket_value& item) { return item.first == key; });
    }

  public:
    void add_or_update_mapping(Key const& key, Value const& value)
    {
      std::unique_lock<boost::shared_mutex> lock(mutex);
      bucket_iterator found_entry = find_entry_for(key);
      if (found_entry == data.end())
      {
        data.push_back(bucket_value(key, value));
      }
      else
      {
        found_entry->second = value;
      }
    }
  };

  std::vector<std::unique_ptr<bucket_type>> buckets;
  Hash hasher;

  bucket_type& get_bucket(Key const& key) const
  {
    std::size_t const bucket_index = hasher(key) % buckets.size();
    return *buckets[bucket_index];
  }

  template <typename Key2, typename Value2>
  friend std::ostream& operator<<(std::ostream& os, const thread_safe_hashmap<Key2, Value2>& map);

public:
  thread_safe_hashmap(unsigned num_buckets = 19, Hash const& hasher_ = Hash())
      : buckets(num_buckets), hasher(hasher_)
  {
    for (unsigned i = 0; i < num_buckets; ++i)
    {
      buckets[i].reset(new bucket_type);
    }
  }

  thread_safe_hashmap(thread_safe_hashmap const& other) = delete;
  thread_safe_hashmap& operator=(thread_safe_hashmap const& other) = delete;

  void add_or_update_mapping(Key const& key, Value const& value)
  {
    get_bucket(key).add_or_update_mapping(key, value);
  }
};

template <typename First, typename Second>
std::ostream& operator<<(std::ostream& os, const std::pair<First, Second>& p)
{
  os << p.first << ' ' << p.second << '\n';
  return os;
}

template <typename Key, typename Value>
std::ostream& operator<<(std::ostream& os, const thread_safe_hashmap<Key, Value>& map)
{
  for (unsigned i = 0; i < map.buckets.size(); ++i)
  {
    for (const auto el : map.buckets[i]->data) os << el << ' ';
    os << '\n';
  }

  return os;
}


int main()
{
  thread_safe_hashmap<std::string, std::string> map;
  map.add_or_update_mapping("key1", "value1");  // problematic line
  std::cout << map;
}

The marked line is causing problems on both gcc and clang:

clang++  -Wall -std=c++14 main2.cpp -lboost_system -o main
main2.cpp:24:14: error: no viable conversion from returned value of type 'std::_List_const_iterator<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >' to function
      return type 'bucket_iterator' (aka '_List_iterator<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >')
      return std::find_if(data.begin(), data.end(),
             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main2.cpp:32:37: note: in instantiation of member function 'thread_safe_hashmap<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char>, std::hash<string> >::bucket_type::find_entry_for'
      requested here
      bucket_iterator found_entry = find_entry_for(key);
                                    ^
main2.cpp:71:21: note: in instantiation of member function 'thread_safe_hashmap<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char>, std::hash<string>
      >::bucket_type::add_or_update_mapping' requested here
    get_bucket(key).add_or_update_mapping(key, value);
                    ^
main2.cpp:98:7: note: in instantiation of member function 'thread_safe_hashmap<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char>, std::hash<string> >::add_or_update_mapping'
      requested here
  map.add_or_update_mapping("key1", "value1");
      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_list.h:125:12: note: candidate constructor (the implicit copy constructor) not viable: no known conversion from
      'std::_List_const_iterator<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >' to 'const std::_List_iterator<std::pair<std::__cxx11::basic_string<char>,
      std::__cxx11::basic_string<char> > > &' for 1st argument
    struct _List_iterator
           ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.3.1/../../../../include/c++/5.3.1/bits/stl_list.h:125:12: note: candidate constructor (the implicit move constructor) not viable: no known conversion from
      'std::_List_const_iterator<std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > >' to 'std::_List_iterator<std::pair<std::__cxx11::basic_string<char>,
      std::__cxx11::basic_string<char> > > &&' for 1st argument
1 error generated.

melpon's online demo

What am I missing here?

Answer 1

This is the expected behavior. In find_entry_for you're trying to return const_iterator, which doesn't match the return type iterator.

find_entry_for is const member function, for data.begin(), data will be const std::list<bucket_value>, begin() called on it will return const_iterator. And std::find_if will return the same type with the type of the parameter iterator, i.e. const_iterator, which could not be implicitly converted to the return type of find_entry_for, i.e. bucket_iterator (std::list::iterator).

Because the returned iterator might be used to change the value it points to, you could

1. Change find_entry_for to non-const member function. (Or add it as new overloading function, change the original const member function's return type to const_iterator.)

2. Try to convert const_iterator to iterator before returns.

Answer 2

bucket_iterator is defined the following way

typedef typename bucket_data::iterator bucket_iterator;

That is it is not a constant iterator.

However in member function find_entry_for

bucket_iterator find_entry_for(const Key& key) const
{
  return std::find_if(data.begin(), data.end(),
                      [&](const bucket_value& item) { return item.first == key; });
}

standard algorithm std::find_if uses the constant iterator because this member function is declared with qualifier const and there are used overloaded functions begin and end for the constant data member data.

So you need to define the constant iterator in the class and use it as the return type of the function.

For example

typedef typename bucket_data::const_iterator const_bucket_iterator;