Questions regarding hash map implementation

[TheToaster]

Not sure if this goes in General or Beginners, but here goes. I am currently reading Professional C++, 4th Edition by Marc Gregoire. In one chapter, the author goes through a custom implementation of a hash map. Here is the declaration of the hash_map template:

template <typename Key, typename T, typename KeyEqual = std::equal_to<>, typename Hash = MyCustomHash::hash<key>>
class hash_map
{
   public:
      using key_type = Key;
      using mapped_type = T;
      using value_type = std::pair<const Key, T>;
      using HASH_MAP = hash_map<Key, T, KeyEqual, Hash>;

      //some code omitted for brevity
   
      //Copy ctor and move ctor
      hash_map(const HASH_MAP& src) = default;
      hash_map(HASH_MAP&& src) noexcept = default

      //Copy assignment/move assignment are defined! Why?
      HASH_MAP& operator=(const HASH_MAP& rhs) {...}
      HASH_MAP& operator=(HASH_MAP&& rhs) noexcept {...}

      void insert(const value_type& x); //Uses list::push_back()
      void erase(const key_type& k); //Uses list::erase()
   
      //Some member functions are omitted for brevity

   private:
      using ListType = std::list<value_type>;
      std::vector<ListType> mBuckets;
      size_t mSize = 0;
      KeyEqual mEqual;
      Hash mHash;
}

I have only posted the relevent parts of the code and I used some type aliases to simplify it. Here are my two questions:

1.) How come the author decided to default the copy ctor/move ctor, but chose to define the copy/move assignment operators? Why is it necessary to define them? Can't they be defaulted as well, since there are no pointers in this class that would need a custom assignment operator?

2.) Why is the type for mBuckets a vector of a list instead of a vector of vectors? Actually, the author has a footnote here explaining why, but I don't quite understand his reasoning:

Because of the const Key in the pair<const Key, T> elements stored in the list, you cannot use a vector instead of a list in this case

Why can't you use a vector in that case? Why is it allowed for lists and not vectors? Does it have something to do with vector reallocations and if so, could someone elaborate why it wouldn't work for vectors and how it would work for lists?

[ne555]

> I have only posted the relevent parts of the code
I would like to see the operator= implementation.

> but chose to define the copy/move assignment operators?
your elements are of the type pair<const Key, T>
you can't modify constant values, so can't end up doing a = b; at element level
so the default assignment operator is deleted and, if you want to provide one, you need to define your own.

> Why is the type for mBuckets a vector of a list instead of a vector of vectors?
reallocations are not the problem, the problem is with .erase()
if you have a vector and remove an element, you'll need to shift all the elements one position to the left.
but your elements are constant, so that can't be done.
a list will just adjust some pointers, so there is no issue.


Edit:
> Not sure if this goes in General or Beginners
put it wherever you want but don't double post
http://www.cplusplus.com/forum/beginner/266718/

[TheToaster]

ne555 wrote:

I would like to see the operator= implementation.

Here is the implementation of the operator= and the custom swap function:

template <typename Key, typename T, typename KeyEqual, typename Hash>
void hash_map<Key, T, KeyEqual, Hash>::swap(
    hash_map<Key, T, KeyEqual, Hash>& other) noexcept
{
    using std::swap;

    swap(mBuckets, other.mBuckets);
    swap(mSize, other.mSize);
    swap(mEqual, other.mEqual);
    swap(mHash, other.mHash);
}

//The following swap function just forwards to the previous member function:
template <typename Key, typename T, typename KeyEqual, typename Hash>
void swap(hash_map<Key, T, KeyEqual, Hash>& first,
                 hash_map<Key, T, KeyEqual, Hash>& second)
{
   first.swap(second);
}

//Assignment operators
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>&
   hash_map<Key, T, KeyEqual, Hash>::operator=(
      const hash_map<Key, T, KeyEqual, Hash>& rhs)
{
   if (this == &rhs) return *this;
   
   auto copy = rhs;
   swap(copy);
   return *this;
}

//Move assignment
template <typename Key, typename T, typename KeyEqual, typename Hash>
hash_map<Key, T, KeyEqual, Hash>&
   hash_map<Key, T, KeyEqual, Hash>::operator=(
      const hash_map<Key, T, KeyEqual, Hash>&& rhs) noexcept
{
   swap(rhs);
   return *this;
}