Help! Hash map implementation confusion

[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? Perhaps the author did so as an example of how they would be defined?

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?

[JLBorges]

> How come the author decided to default the copy ctor/move ctor,
> but chose to define the copy/move assignment operators?

The value_type of the hash_map has a member of a const qualified type; it is not CopyAssignable or MoveAssignable (this is required for copy/move assignment of standard containers; so we can't default to them).

It is CopyInsertable and MoveInsertable; so we can default copy/move constructors.



> Why can't you use a vector in that case? Why is it allowed for lists and not vectors?

Vector is a ContiguousContainer https://en.cppreference.com/w/cpp/named_req/ContiguousContainer
To be able to erase an element from a vector, the elements must be MoveAssignable; all the elements after the one that is erased need to be moved. A list has no such requirement.

[TheToaster]

Why is the type requirement CopyInsertable and MoveInsertable? What is the difference between that and CopyConstructable and MoveConstructable?

Also, when you say that vector is a ContiguousContainer, you mention that the elements must be MoveAssignable because if you erase an element, you have to shift all the elements down. What about inserting elements? Wouldn't push_back() also trigger this problem because if the vector performs a reallocation, then all the elements would have to be moved to the larger, new vector?

The value_type of the hash_map has a member of a const qualified type; it is not CopyAssignable or MoveAssignable (this is required for copy/move assignment of standard containers; so we can't default to them).

But the implementation of operator= uses the copy/swap idiom to swap the elements value. How can you swap a const qualified type, as you mentioned? Here is the implementation:

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

[JLBorges]

> Why is the type requirement CopyInsertable and MoveInsertable?
> What is the difference between that and CopyConstructable and MoveConstructable?

There is no difference between the two in the vast majority of cases.
There is a difference only if the type involved supports 'uses-allocator construction' and is used in conjunction with an allocator that defines an appropriate construct member function.
For instance, std::pmr::polymorphic_allocator is such an allocator.

Here is an example of a type that is not CopyConstructable or MoveConstructable, but is CopyInsertable and MoveInsertable when used with an allocator-aware container that uses std::pmr::polymorphic_allocator
(You may want to ignore this nicety for now;
wait till you delve deeper into the innards of allocators and allocator traits.)

#include <iostream>
#include <string>
#include <memory>
#include <memory_resource>
#include <vector>

struct A
{
    // make A support 'uses-allocator copy/move construction'
    // 1. provide a member typedef allocator_type which identifies the allocator
    // 2. provide constructors which can create a copy, but accept an additional allocator object

    using allocator_type = std::pmr::polymorphic_allocator<A> ;
    A() = default ;

    A( const A& ) = delete ; // not CopyConstructible
    A( A&& ) = delete ; // not MoveConstructible

    // make it CopyInsertable and MoveInsertable with the associated allocator_type
    // uses the 'trailing-allocator convention' (allocator passed as the last constructor arg)
    // see: https://en.cppreference.com/w/cpp/memory/uses_allocator
    // (note that the allocator object is not used in this toy example)
    A( const A& that, const allocator_type& ) : str(that.str)
    { std::cout << "create a copy of A via 'uses-allocator (copy) construction'\n" ; }

    A( A&& that, const allocator_type& ) : str( std::move(that.str) )
    { std::cout << "create a copy of A via 'uses-allocator (move) construction'\n" ; }

    std::string str = "abcd" ; // for exposition
};

int main()
{
    A a, a1 ;
    // A cpy(a) ; // *** error: not CopyConstructible (deleted copy constructor)
    // A cpy2( std::move(a1) ) ; // *** error: not MoveConstructible (deleted move constructor)

    std::pmr::vector<A> vec ; // vector that uses std::pmr::polymorphic_allocator
    vec.reserve(10) ; // avoid reallocation/relocation noise

    vec.push_back(a) ; // fine: CopyInsertable
    // create a copy of A via 'uses-allocator (copy) construction'

    vec.push_back( std::move(a1) ) ; // fine: MoveInsertable
    // create a copy of A via 'uses-allocator (move) construction'
}

http://coliru.stacked-crooked.com/a/19018f9dbe963ad2


> What about inserting elements?

To be able to use insert on a vector, the elements must be MoveAssignable; elements have to be moved to make space for the one being inserted.
see 'Type requirements' in https://en.cppreference.com/w/cpp/container/vector/insert#Parameters

> Wouldn't push_back() also trigger this problem because if the vector performs a
> reallocation, then all the elements would have to be moved to the larger, new vector?

push_back has no such requirement; if reallocation is required, the elements are move-inserted (typically move constructed) into the newly allocated larger storage; and the old elements are destroyed.
see 'Type requirements' in https://en.cppreference.com/w/cpp/container/vector/push_back#Parameters


> But the implementation of operator= uses the copy/swap idiom to swap the elements value. > How can you swap a const qualified type, as you mentioned?

The swap of a standard container (vector in this case) 'does not invoke any move, copy, or swap operations on individual elements'. Its complexity is O(1).
https://en.cppreference.com/w/cpp/container/vector/swap
(Swap of a vector can be done by swapping just a few pointers and/or size_types; allocators are swapped if and only if it is required).

#include <utility>
#include <type_traits>
#include <vector>
#include <iostream>

int main()
{
    using value_type = std::pair< const int, int > ;
    std::cout << std::boolalpha << "pair is swappable? " << std::is_swappable<value_type>::value << '\n' ; // false (not swappable)
    
    value_type x{1,2}, y{3,4} ;
    using std::swap ;
    // swap(x,y) ; // *** error: not swappable
    
    std::vector<value_type> a{x,y}, b ;
    std::cout << "vector is swappable? " << std::is_swappable< std::vector<value_type> >::value << '\n' ; // true (swappable)
    swap(a,b) ; // fine
}

http://coliru.stacked-crooked.com/a/0b42109fa572ab5b