Re: [patch] No allocation for empty unordered containers

[François Dumont <frs dot dumont at gmail dot com>]

On 04/08/2014 13:55, Jonathan Wakely wrote:
> If we don't make it noexcept then I see no point in avoiding
> allocation.
>
> (And if the functors and allocator can throw then the noexcept might
> have to be condition.)
>
> So please make sure we get that change as well during stage 1.

Hi

    I know why move constructor must be noexcept but why default must 
be too ?

    If it is the only goal then easier and most natural approach is the 
small attached patch. No yet fully tested so not a proposal yet. 
Drawback is of course that we do not have only Standard constructors.

    I can think of another solution using the rehash policy. We could 
store in it the user hint and use it as soon as an element is inserted. 
This way constructor with hint would simply prepare the rehash policy 
and not allocate anything. But it is an additional std::size_t to store 
in the memory footprint of the container and implementing it will tell 
us if it is feasible.

François

Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 213643)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -1250,6 +1250,8 @@
       typedef std::size_t 				__hash_code;
       typedef _Hash_node<_Value, true>			__node_type;
 
+      _Hash_code_base() = default;
+
       _Hash_code_base(const _ExtractKey& __ex,
 		      const _H1& __h1, const _H2& __h2,
 		      const _Default_ranged_hash&)
@@ -1694,6 +1696,8 @@
 					__hash_code, __hash_cached::value>;
 
   protected:
+    _Hashtable_base() = default;
+
     _Hashtable_base(const _ExtractKey& __ex, const _H1& __h1, const _H2& __h2,
 		    const _Hash& __hash, const _Equal& __eq)
     : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
@@ -1906,6 +1910,7 @@
 	__alloc_rebind<__node_alloc_type, __bucket_type>;
       using __bucket_alloc_traits = std::allocator_traits<__bucket_alloc_type>;
 
+      _Hashtable_alloc() = default;
       _Hashtable_alloc(const _Hashtable_alloc&) = default;
       _Hashtable_alloc(_Hashtable_alloc&&) = default;
 
Index: include/bits/hashtable.h
===================================================================
--- include/bits/hashtable.h	(revision 213643)
+++ include/bits/hashtable.h	(working copy)
@@ -310,10 +310,10 @@
 				   const_local_iterator;
 
     private:
-      __bucket_type*		_M_buckets;
-      size_type			_M_bucket_count;
+      __bucket_type*		_M_buckets = &_M_single_bucket;
+      size_type			_M_bucket_count = 1;
       __node_base		_M_before_begin;
-      size_type			_M_element_count;
+      size_type			_M_element_count = 0;
       _RehashPolicy		_M_rehash_policy;
 
       // A single bucket used when only need for 1 bucket. Especially
@@ -322,7 +322,7 @@
       // qualified.
       // Note that we can't leave hashtable with 0 bucket without adding
       // numerous checks in the code to avoid 0 modulus.
-      __bucket_type		_M_single_bucket;
+      __bucket_type		_M_single_bucket = nullptr;
 
       bool
       _M_uses_single_bucket(__bucket_type* __bkts) const
@@ -384,6 +384,8 @@
 
     public:
       // Constructor, destructor, assignment, swap
+      _Hashtable() = default;
+
       _Hashtable(size_type __bucket_hint,
 		 const _H1&, const _H2&, const _Hash&,
 		 const _Equal&, const _ExtractKey&,
@@ -412,7 +414,7 @@
       { }
 
       explicit
-      _Hashtable(size_type __n = 10,
+      _Hashtable(size_type __n,
 		 const _H1& __hf = _H1(),
 		 const key_equal& __eql = key_equal(),
 		 const allocator_type& __a = allocator_type())
Index: include/bits/unordered_map.h
===================================================================
--- include/bits/unordered_map.h	(revision 213643)
+++ include/bits/unordered_map.h	(working copy)
@@ -128,15 +128,18 @@
 
       //construct/destroy/copy
 
+      /// Default constructor.
+      unordered_map() = default;
+
       /**
-       *  @brief  Default constructor creates no elements.
-       *  @param __n  Initial number of buckets.
+       *  @brief  Constructor with bucket reservation, creates no elements.
+       *  @param __n  Initial number of buckets hint.
        *  @param __hf  A hash functor.
        *  @param __eql  A key equality functor.
        *  @param __a  An allocator object.
        */
       explicit
-      unordered_map(size_type __n = 10,
+      unordered_map(size_type __n,
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
@@ -840,15 +843,18 @@
 
       //construct/destroy/copy
 
+      /// Default constructor.
+      unordered_multimap() = default;
+
       /**
-       *  @brief  Default constructor creates no elements.
-       *  @param __n  Initial number of buckets.
+       *  @brief  Constructor with bucket reservation, creates no elements.
+       *  @param __n  Initial number of buckets hint.
        *  @param __hf  A hash functor.
        *  @param __eql  A key equality functor.
        *  @param __a  An allocator object.
        */
       explicit
-      unordered_multimap(size_type __n = 10,
+      unordered_multimap(size_type __n,
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())
Index: include/bits/unordered_set.h
===================================================================
--- include/bits/unordered_set.h	(revision 213643)
+++ include/bits/unordered_set.h	(working copy)
@@ -121,15 +121,19 @@
       //@}
 
       // construct/destroy/copy
+
+      /// Default constructor.
+      unordered_set() = default;
+
       /**
-       *  @brief  Default constructor creates no elements.
-       *  @param __n  Initial number of buckets.
+       *  @brief  Constructor with bucket reservation, creates no elements.
+       *  @param __n  Initial number of buckets hint.
        *  @param __hf  A hash functor.
        *  @param __eql  A key equality functor.
        *  @param __a  An allocator object.
        */
       explicit
-      unordered_set(size_type __n = 10,
+      unordered_set(size_type __n,
 		    const hasher& __hf = hasher(),
 		    const key_equal& __eql = key_equal(),
 		    const allocator_type& __a = allocator_type())
@@ -756,15 +760,19 @@
       //@}
 
       // construct/destroy/copy
+
+      /// Default constructor.
+      unordered_multiset() = default;
+
       /**
-       *  @brief  Default constructor creates no elements.
-       *  @param __n  Initial number of buckets.
+       *  @brief  Constructor with bucket reservation, creates no elements.
+       *  @param __n  Initial number of buckets hint.
        *  @param __hf  A hash functor.
        *  @param __eql  A key equality functor.
        *  @param __a  An allocator object.
        */
       explicit
-      unordered_multiset(size_type __n = 10,
+      unordered_multiset(size_type __n,
 			 const hasher& __hf = hasher(),
 			 const key_equal& __eql = key_equal(),
 			 const allocator_type& __a = allocator_type())