unordered_multimap.h

00001 ///\file
00002 
00003 /******************************************************************************
00004 The MIT License(MIT)
00005 
00006 Embedded Template Library.
00007 https://github.com/ETLCPP/etl
00008 http://www.etlcpp.com
00009 
00010 Copyright(c) 2016 jwellbelove
00011 
00012 Permission is hereby granted, free of charge, to any person obtaining a copy
00013 of this software and associated documentation files(the "Software"), to deal
00014 in the Software without restriction, including without limitation the rights
00015 to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
00016 copies of the Software, and to permit persons to whom the Software is
00017 furnished to do so, subject to the following conditions :
00018 
00019 The above copyright notice and this permission notice shall be included in all
00020 copies or substantial portions of the Software.
00021 
00022 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
00023 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
00024 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
00025 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
00026 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
00027 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
00028 SOFTWARE.
00029 ******************************************************************************/
00030 
00031 #ifndef __ETL_UNORDERED_MULTIMAP__
00032 #define __ETL_UNORDERED_MULTIMAP__
00033 
00034 #include <stddef.h>
00035 #include <iterator>
00036 #include <functional>
00037 #include <algorithm>
00038 #include <functional>
00039 #include <utility>
00040 
00041 #include "platform.h "
00042 #include "container.h "
00043 #include "pool.h "
00044 #include "vector.h "
00045 #include "intrusive_forward_list.h "
00046 #include "hash.h "
00047 #include "type_traits.h "
00048 #include "parameter_type.h "
00049 #include "nullptr.h "
00050 #include "pool.h "
00051 #include "error_handler.h "
00052 #include "exception.h "
00053 #include "debug_count.h "
00054 
00055 #undef ETL_FILE
00056 #define ETL_FILE "25"
00057 
00058 //*****************************************************************************
00059 ///\defgroup unordered_multimap unordered_multimap
00060 /// A unordered_multimap with the capacity defined at compile time.
00061 ///\ingroup containers
00062 //*****************************************************************************
00063 
00064 namespace etl
00065 {
00066   //***************************************************************************
00067   /// Exception for the unordered_multimap.
00068   ///\ingroup unordered_multimap
00069   //***************************************************************************
00070   class unordered_multimap_exception : public etl::exception
00071   {
00072   public:
00073 
00074     unordered_multimap_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00075       : etl::exception(reason_, file_name_, line_number_)
00076     {
00077     }
00078   };
00079 
00080   //***************************************************************************
00081   /// Full exception for the unordered_multimap.
00082   ///\ingroup unordered_multimap
00083   //***************************************************************************
00084   class unordered_multimap_full : public etl::unordered_multimap_exception
00085   {
00086   public:
00087 
00088     unordered_multimap_full(string_type file_name_, numeric_type line_number_)
00089       : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:full", ETL_FILE"A"), file_name_, line_number_)
00090     {
00091     }
00092   };
00093 
00094   //***************************************************************************
00095   /// Out of range exception for the unordered_multimap.
00096   ///\ingroup unordered_multimap
00097   //***************************************************************************
00098   class unordered_multimap_out_of_range : public etl::unordered_multimap_exception
00099   {
00100   public:
00101 
00102     unordered_multimap_out_of_range(string_type file_name_, numeric_type line_number_)
00103       : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:range", ETL_FILE"B"), file_name_, line_number_)
00104     {}
00105   };
00106 
00107   //***************************************************************************
00108   /// Iterator exception for the unordered_multimap.
00109   ///\ingroup unordered_multimap
00110   //***************************************************************************
00111   class unordered_multimap_iterator : public etl::unordered_multimap_exception
00112   {
00113   public:
00114 
00115     unordered_multimap_iterator(string_type file_name_, numeric_type line_number_)
00116       : etl::unordered_multimap_exception(ETL_ERROR_TEXT("unordered_multimap:iterator", ETL_FILE"C"), file_name_, line_number_)
00117     {
00118     }
00119   };
00120 
00121   //***************************************************************************
00122   /// The base class for specifically sized unordered_multimap.
00123   /// Can be used as a reference type for all unordered_multimap containing a specific type.
00124   ///\ingroup unordered_multimap
00125   //***************************************************************************
00126   template <typename TKey, typename T, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
00127   class iunordered_multimap
00128   {
00129   public:
00130 
00131     typedef std::pair<const TKey, T> value_type;
00132 
00133     typedef TKey              key_type;
00134     typedef T                 mapped_type;
00135     typedef THash             hasher;
00136     typedef TKeyEqual         key_equal;
00137     typedef value_type&       reference;
00138     typedef const value_type& const_reference;
00139     typedef value_type*       pointer;
00140     typedef const value_type* const_pointer;
00141     typedef size_t            size_type;
00142 
00143 
00144     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00145 
00146     typedef etl::forward_link<0>  link_t ; // Default link.
00147 
00148     struct node_t : public link_t  // The nodes that store the elements.
00149     {
00150       node_t(const value_type& key_value_pair_)
00151         : key_value_pair(key_value_pair_)
00152       {
00153       }
00154 
00155       value_type key_value_pair;
00156     };
00157 
00158   private:
00159 
00160     typedef etl::intrusive_forward_list<node_t, link_t> bucket_t;
00161     typedef etl::ipool pool_t;
00162 
00163   public:
00164 
00165     // Local iterators iterate over one bucket.
00166     typedef typename bucket_t::iterator       local_iterator;
00167     typedef typename bucket_t::const_iterator local_const_iterator;
00168 
00169     //*********************************************************************
00170     class iterator : public std::iterator<std::forward_iterator_tag, T>
00171     {
00172     public:
00173 
00174       typedef typename iunordered_multimap::value_type      value_type;
00175       typedef typename iunordered_multimap::key_type        key_type;
00176       typedef typename iunordered_multimap::mapped_type     mapped_type;
00177       typedef typename iunordered_multimap::hasher          hasher;
00178       typedef typename iunordered_multimap::key_equal       key_equal;
00179       typedef typename iunordered_multimap::reference       reference;
00180       typedef typename iunordered_multimap::const_reference const_reference;
00181       typedef typename iunordered_multimap::pointer         pointer;
00182       typedef typename iunordered_multimap::const_pointer   const_pointer;
00183       typedef typename iunordered_multimap::size_type       size_type;
00184 
00185       friend class iunordered_multimap;
00186 
00187       //*********************************
00188       iterator()
00189       {
00190       }
00191 
00192       //*********************************
00193       iterator(const iterator& other)
00194         : pbuckets_end(other.pbuckets_end),
00195         pbucket(other.pbucket),
00196         inode(other.inode)
00197       {
00198       }
00199 
00200       //*********************************
00201       iterator& operator ++()
00202       {
00203         ++inode;
00204 
00205         // The end of this node list?
00206         if (inode == pbucket->end())
00207         {
00208           // Search for the next non-empty bucket.
00209           ++pbucket;
00210           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00211           {
00212             ++pbucket;
00213           }
00214 
00215           // If not past the end, get the first node in the bucket.
00216           if (pbucket != pbuckets_end)
00217           {
00218             inode = pbucket->begin();
00219           }
00220         }
00221 
00222         return *this;
00223       }
00224 
00225       //*********************************
00226       iterator operator ++(int)
00227       {
00228         iterator temp(*this);
00229         operator++();
00230         return temp;
00231       }
00232 
00233       //*********************************
00234       iterator operator =(const iterator& other)
00235       {
00236         pbuckets_end = other.pbuckets_end;
00237         pbucket = other.pbucket;
00238         inode = other.inode;
00239         return *this;
00240       }
00241 
00242       //*********************************
00243       std::pair<const TKey, T> operator *()
00244       {
00245         return inode->key_value_pair;
00246       }
00247 
00248       //*********************************
00249       const_reference operator *() const
00250       {
00251         return inode->key_value_pair;
00252       }
00253 
00254       //*********************************
00255       pointer operator &()
00256       {
00257         return &(inode->key_value_pair);
00258       }
00259 
00260       //*********************************
00261       const_pointer operator &() const
00262       {
00263         return &(inode->key_value_pair);
00264       }
00265 
00266       //*********************************
00267       pointer operator ->()
00268       {
00269         return &(inode->key_value_pair);
00270       }
00271 
00272       //*********************************
00273       const_pointer operator ->() const
00274       {
00275         return &(inode->key_value_pair);
00276       }
00277 
00278       //*********************************
00279       friend bool operator == (const iterator& lhs, const iterator& rhs)
00280       {
00281         return lhs.compare(rhs);
00282       }
00283 
00284       //*********************************
00285       friend bool operator != (const iterator& lhs, const iterator& rhs)
00286       {
00287         return !(lhs == rhs);
00288       }
00289 
00290     private:
00291 
00292       //*********************************
00293       iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00294         : pbuckets_end(pbuckets_end_),
00295           pbucket(pbucket_),
00296           inode(inode_)
00297       {
00298       }
00299 
00300       //*********************************
00301       bool compare(const iterator& rhs) const
00302       {
00303         return rhs.inode == inode;
00304       }
00305 
00306       //*********************************
00307       bucket_t& get_bucket()
00308       {
00309         return *pbucket;
00310       }
00311 
00312       //*********************************
00313       bucket_t*& get_bucket_list_iterator()
00314       {
00315         return pbucket;
00316       }
00317 
00318       //*********************************
00319       local_iterator get_local_iterator()
00320       {
00321         return inode;
00322       }
00323 
00324       bucket_t* pbuckets_end;
00325       bucket_t* pbucket;
00326       local_iterator       inode;
00327     };
00328 
00329     //*********************************************************************
00330     class const_iterator : public std::iterator<std::forward_iterator_tag, const T>
00331     {
00332     public:
00333 
00334       typedef typename iunordered_multimap::value_type      value_type;
00335       typedef typename iunordered_multimap::key_type        key_type;
00336       typedef typename iunordered_multimap::mapped_type     mapped_type;
00337       typedef typename iunordered_multimap::hasher          hasher;
00338       typedef typename iunordered_multimap::key_equal       key_equal;
00339       typedef typename iunordered_multimap::reference       reference;
00340       typedef typename iunordered_multimap::const_reference const_reference;
00341       typedef typename iunordered_multimap::pointer         pointer;
00342       typedef typename iunordered_multimap::const_pointer   const_pointer;
00343       typedef typename iunordered_multimap::size_type       size_type;
00344 
00345       friend class iunordered_multimap;
00346       friend class iterator;
00347 
00348       //*********************************
00349       const_iterator()
00350       {
00351       }
00352 
00353       //*********************************
00354       const_iterator(const typename iunordered_multimap::iterator& other)
00355         : pbuckets_end(other.pbuckets_end),
00356         pbucket(other.pbucket),
00357         inode(other.inode)
00358       {
00359       }
00360 
00361       //*********************************
00362       const_iterator(const const_iterator& other)
00363         : pbuckets_end(other.pbuckets_end),
00364         pbucket(other.pbucket),
00365         inode(other.inode)
00366       {
00367       }
00368 
00369       //*********************************
00370       const_iterator& operator ++()
00371       {
00372         ++inode;
00373 
00374         // The end of this node list?
00375         if (inode == pbucket->end())
00376         {
00377           // Search for the next non-empty bucket.
00378 
00379           ++pbucket;
00380           while ((pbucket != pbuckets_end) && (pbucket->empty()))
00381           {
00382             ++pbucket;
00383           }
00384 
00385           // If not past the end, get the first node in the bucket.
00386           if (pbucket != pbuckets_end)
00387           {
00388             inode = pbucket->begin();
00389           }
00390         }
00391 
00392         return *this;
00393       }
00394 
00395       //*********************************
00396       const_iterator operator ++(int)
00397       {
00398         const_iterator temp(*this);
00399         operator++();
00400         return temp;
00401       }
00402 
00403       //*********************************
00404       const_iterator operator =(const const_iterator& other)
00405       {
00406         pbuckets_end = other.pbuckets_end;
00407         pbucket = other.pbucket;
00408         inode = other.inode;
00409         return *this;
00410       }
00411 
00412       //*********************************
00413       const_reference operator *() const
00414       {
00415         return inode->key_value_pair;
00416       }
00417 
00418       //*********************************
00419       const_pointer operator &() const
00420       {
00421         return &(inode->key_value_pair);
00422       }
00423 
00424       //*********************************
00425       const_pointer operator ->() const
00426       {
00427         return &(inode->key_value_pair);
00428       }
00429 
00430       //*********************************
00431       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00432       {
00433         return lhs.compare(rhs);
00434       }
00435 
00436       //*********************************
00437       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00438       {
00439         return !(lhs == rhs);
00440       }
00441 
00442     private:
00443 
00444       //*********************************
00445       const_iterator(bucket_t* pbuckets_end_, bucket_t* pbucket_, local_iterator inode_)
00446         : pbuckets_end(pbuckets_end_),
00447           pbucket(pbucket_),
00448           inode(inode_)
00449       {
00450       }
00451 
00452       //*********************************
00453       bool compare(const const_iterator& rhs) const
00454       {
00455         return rhs.inode == inode;
00456       }
00457 
00458       //*********************************
00459       bucket_t& get_bucket()
00460       {
00461         return *pbucket;
00462       }
00463 
00464       //*********************************
00465       bucket_t*& get_bucket_list_iterator()
00466       {
00467         return pbucket;
00468       }
00469 
00470       //*********************************
00471       local_iterator get_local_iterator()
00472       {
00473         return inode;
00474       }
00475 
00476       bucket_t* pbuckets_end;
00477       bucket_t* pbucket;
00478       local_iterator       inode;
00479     };
00480 
00481     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00482 
00483     //*********************************************************************
00484     /// Returns an iterator to the beginning of the unordered_multimap.
00485     ///\return An iterator to the beginning of the unordered_multimap.
00486     //*********************************************************************
00487     iterator begin()
00488     {
00489       return iterator((pbuckets + number_of_buckets), first, first->begin());
00490     }
00491 
00492     //*********************************************************************
00493     /// Returns a const_iterator to the beginning of the unordered_multimap.
00494     ///\return A const iterator to the beginning of the unordered_multimap.
00495     //*********************************************************************
00496     const_iterator begin() const
00497     {
00498       return const_iterator((pbuckets + number_of_buckets), first, first->begin());
00499     }
00500 
00501     //*********************************************************************
00502     /// Returns a const_iterator to the beginning of the unordered_multimap.
00503     ///\return A const iterator to the beginning of the unordered_multimap.
00504     //*********************************************************************
00505     const_iterator cbegin() const
00506     {
00507       return const_iterator((pbuckets + number_of_buckets), first, first->begin());
00508     }
00509 
00510     //*********************************************************************
00511     /// Returns an iterator to the beginning of the unordered_multimap bucket.
00512     ///\return An iterator to the beginning of the unordered_multimap bucket.
00513     //*********************************************************************
00514     local_iterator begin(size_t i)
00515     {
00516       return pbuckets[i].begin();
00517     }
00518 
00519     //*********************************************************************
00520     /// Returns a const_iterator to the beginning of the unordered_multimap bucket.
00521     ///\return A const iterator to the beginning of the unordered_multimap bucket.
00522     //*********************************************************************
00523     local_const_iterator begin(size_t i) const
00524     {
00525       return pbuckets[i].cbegin();
00526     }
00527 
00528     //*********************************************************************
00529     /// Returns a const_iterator to the beginning of the unordered_multimap bucket.
00530     ///\return A const iterator to the beginning of the unordered_multimap bucket.
00531     //*********************************************************************
00532     local_const_iterator cbegin(size_t i) const
00533     {
00534       return pbuckets[i].cbegin();
00535     }
00536 
00537     //*********************************************************************
00538     /// Returns an iterator to the end of the unordered_multimap.
00539     ///\return An iterator to the end of the unordered_multimap.
00540     //*********************************************************************
00541     iterator end()
00542     {
00543       return iterator((pbuckets + number_of_buckets), last, last->end());
00544     }
00545 
00546     //*********************************************************************
00547     /// Returns a const_iterator to the end of the unordered_multimap.
00548     ///\return A const iterator to the end of the unordered_multimap.
00549     //*********************************************************************
00550     const_iterator end() const
00551     {
00552       return const_iterator((pbuckets + number_of_buckets), last, last->end());
00553     }
00554 
00555     //*********************************************************************
00556     /// Returns a const_iterator to the end of the unordered_multimap.
00557     ///\return A const iterator to the end of the unordered_multimap.
00558     //*********************************************************************
00559     const_iterator cend() const
00560     {
00561       return const_iterator((pbuckets + number_of_buckets), last, last->end());
00562     }
00563 
00564     //*********************************************************************
00565     /// Returns an iterator to the end of the unordered_multimap bucket.
00566     ///\return An iterator to the end of the unordered_multimap bucket.
00567     //*********************************************************************
00568     local_iterator end(size_t i)
00569     {
00570       return pbuckets[i].end();
00571     }
00572 
00573     //*********************************************************************
00574     /// Returns a const_iterator to the end of the unordered_multimap bucket.
00575     ///\return A const iterator to the end of the unordered_multimap bucket.
00576     //*********************************************************************
00577     local_const_iterator end(size_t i) const
00578     {
00579       return pbuckets[i].cend();
00580     }
00581 
00582     //*********************************************************************
00583     /// Returns a const_iterator to the end of the unordered_multimap bucket.
00584     ///\return A const iterator to the end of the unordered_multimap bucket.
00585     //*********************************************************************
00586     local_const_iterator cend(size_t i) const
00587     {
00588       return pbuckets[i].cend();
00589     }
00590 
00591     //*********************************************************************
00592     /// Returns the bucket index for the key.
00593     ///\return The bucket index for the key.
00594     //*********************************************************************
00595     size_type get_bucket_index(key_parameter_t key) const
00596     {
00597       return key_hash_function(key) % number_of_buckets;
00598     }
00599 
00600     //*********************************************************************
00601     /// Returns the size of the bucket key.
00602     ///\return The bucket size of the bucket key.
00603     //*********************************************************************
00604     size_type bucket_size(key_parameter_t key) const
00605     {
00606       size_t index = bucket(key);
00607 
00608       return std::distance(pbuckets[index].begin(), pbuckets[index].end());
00609     }
00610 
00611     //*********************************************************************
00612     /// Returns the maximum number of the buckets the container can hold.
00613     ///\return The maximum number of the buckets the container can hold.
00614     //*********************************************************************
00615     size_type max_bucket_count() const
00616     {
00617       return number_of_buckets;
00618     }
00619 
00620     //*********************************************************************
00621     /// Returns the number of the buckets the container holds.
00622     ///\return The number of the buckets the container holds.
00623     //*********************************************************************
00624     size_type bucket_count() const
00625     {
00626       return number_of_buckets;
00627     }
00628 
00629     //*********************************************************************
00630     /// Assigns values to the unordered_multimap.
00631     /// If asserts or exceptions are enabled, emits unordered_multimap_full if the unordered_multimap does not have enough free space.
00632     /// If asserts or exceptions are enabled, emits unordered_multimap_iterator if the iterators are reversed.
00633     ///\param first The iterator to the first element.
00634     ///\param last  The iterator to the last element + 1.
00635     //*********************************************************************
00636     template <typename TIterator>
00637     void assign(TIterator first_, TIterator last_)
00638     {
00639 #if defined(ETL_DEBUG)
00640       difference_type d = std::distance(first_, last_);
00641       ETL_ASSERT(d >= 0, ETL_ERROR(unordered_multimap_iterator));
00642       ETL_ASSERT(size_t(d) <= max_size(), ETL_ERROR(unordered_multimap_full));
00643 #endif
00644 
00645       clear();
00646 
00647       while (first_ != last_)
00648       {
00649         insert(*first_++);
00650       }
00651     }
00652 
00653     //*********************************************************************
00654     /// Inserts a value to the unordered_multimap.
00655     /// If asserts or exceptions are enabled, emits unordered_multimap_full if the unordered_multimap is already full.
00656     ///\param value The value to insert.
00657     //*********************************************************************
00658     iterator insert(const value_type& key_value_pair)
00659     {
00660       iterator result = end();
00661 
00662       ETL_ASSERT(!full(), ETL_ERROR(unordered_multimap_full));
00663 
00664       const key_type&    key = key_value_pair.first;
00665       const mapped_type& mapped = key_value_pair.second;
00666 
00667       // Get the hash index.
00668       size_t index = get_bucket_index(key);
00669 
00670       // Get the bucket & bucket iterator.
00671       bucket_t* pbucket = pbuckets + index;
00672       bucket_t& bucket = *pbucket;
00673 
00674       // The first one in the bucket?
00675       if (bucket.empty())
00676       {
00677         // Get a new node.
00678         node_t& node = *pnodepool->allocate<node_t>();
00679         ::new (&node.key_value_pair) value_type(key_value_pair);
00680         ++construct_count;
00681 
00682         // Just add the pointer to the bucket;
00683         bucket.insert_after(bucket.before_begin(), node);
00684 
00685         result = iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
00686 
00687         adjust_first_last_markers(pbucket);
00688       }
00689       else
00690       {
00691         // Step though the bucket looking for a place to insert.
00692         local_iterator inode_previous = bucket.before_begin();
00693         local_iterator inode = bucket.begin();
00694 
00695         while (inode != bucket.end())
00696         {
00697           // Do we already have this key?
00698           if (inode->key_value_pair.first == key)
00699           {
00700             break;
00701           }
00702 
00703           ++inode_previous;
00704           ++inode;
00705         }
00706 
00707         // Get a new node.
00708         node_t& node = *pnodepool->allocate<node_t>();
00709         ::new (&node.key_value_pair) value_type(key_value_pair);
00710         ++construct_count;
00711 
00712         // Add the node to the end of the bucket;
00713         bucket.insert_after(inode_previous, node);
00714         ++inode_previous;
00715 
00716         result = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
00717       }
00718 
00719       return result;
00720     }
00721 
00722     //*********************************************************************
00723     /// Inserts a value to the unordered_multimap.
00724     /// If asserts or exceptions are enabled, emits unordered_multimap_full if the unordered_multimap is already full.
00725     ///\param position The position to insert at.
00726     ///\param value    The value to insert.
00727     //*********************************************************************
00728     iterator insert(const_iterator position, const value_type& key_value_pair)
00729     {
00730       return insert(key_value_pair);
00731     }
00732 
00733     //*********************************************************************
00734     /// Inserts a range of values to the unordered_multimap.
00735     /// If asserts or exceptions are enabled, emits unordered_multimap_full if the unordered_multimap does not have enough free space.
00736     ///\param position The position to insert at.
00737     ///\param first    The first element to add.
00738     ///\param last     The last + 1 element to add.
00739     //*********************************************************************
00740     template <class TIterator>
00741     void insert(TIterator first_, TIterator last_)
00742     {
00743       while (first_ != last_)
00744       {
00745         insert(*first_++);
00746       }
00747     }
00748 
00749     //*********************************************************************
00750     /// Erases an element.
00751     ///\param key The key to erase.
00752     ///\return The number of elements erased.
00753     //*********************************************************************
00754     size_t erase(key_parameter_t key)
00755     {
00756       size_t n = 0;
00757       size_t bucket_id = get_bucket_index(key);
00758 
00759       bucket_t& bucket = pbuckets[bucket_id];
00760 
00761       local_iterator iprevious = bucket.before_begin();
00762       local_iterator icurrent = bucket.begin();
00763 
00764       while (icurrent != bucket.end())
00765       {
00766         if (icurrent->key_value_pair.first == key)
00767         {
00768           bucket.erase_after(iprevious);          // Unlink from the bucket.
00769           icurrent->key_value_pair.~value_type(); // Destroy the value.
00770           pnodepool->release(&*icurrent);         // Release it back to the pool.
00771           ++n;
00772           icurrent = iprevious;
00773           --construct_count;
00774         }
00775         else
00776         {
00777           ++iprevious;
00778         }
00779 
00780         ++icurrent;
00781       }
00782 
00783       return n;
00784     }
00785 
00786     //*********************************************************************
00787     /// Erases an element.
00788     ///\param ielement Iterator to the element.
00789     //*********************************************************************
00790     iterator erase(const_iterator ielement)
00791     {
00792       // Make a note of the next one.
00793       iterator inext((pbuckets + number_of_buckets), ielement.get_bucket_list_iterator(), ielement.get_local_iterator());
00794       ++inext;
00795 
00796       bucket_t&      bucket = ielement.get_bucket();
00797       local_iterator iprevious = bucket.before_begin();
00798       local_iterator icurrent = ielement.get_local_iterator();
00799 
00800       // Find the node previous to the one we're interested in.
00801       while (iprevious->etl_next != &*icurrent)
00802       {
00803         ++iprevious;
00804       }
00805 
00806       bucket.erase_after(iprevious);          // Unlink from the bucket.
00807       icurrent->key_value_pair.~value_type(); // Destroy the value.
00808       pnodepool->release(&*icurrent);         // Release it back to the pool.
00809       --construct_count;
00810 
00811       return inext;
00812     }
00813 
00814     //*********************************************************************
00815     /// Erases a range of elements.
00816     /// The range includes all the elements between first and last, including the
00817     /// element pointed by first, but not the one pointed to by last.
00818     ///\param first Iterator to the first element.
00819     ///\param last  Iterator to the last element.
00820     //*********************************************************************
00821     iterator erase(const_iterator first_, const_iterator last_)
00822     {
00823       // Make a note of the last.
00824       iterator result((pbuckets + number_of_buckets), last_.get_bucket_list_iterator(), last_.get_local_iterator());
00825 
00826       // Get the starting point.
00827       bucket_t*      pbucket   = first_.get_bucket_list_iterator();
00828       local_iterator iprevious = pbucket->before_begin();
00829       local_iterator icurrent  = first_.get_local_iterator();
00830       local_iterator iend      = last_.get_local_iterator(); // Note: May not be in the same bucket as icurrent.
00831 
00832                                                        // Find the node previous to the first one.
00833       while (iprevious->etl_next != &*icurrent)
00834       {
00835         ++iprevious;
00836       }
00837 
00838       while (icurrent != iend)
00839       {
00840 
00841         local_iterator inext = pbucket->erase_after(iprevious); // Unlink from the bucket.
00842         icurrent->key_value_pair.~value_type(); // Destroy the value.
00843         pnodepool->release(&*icurrent);         // Release it back to the pool.
00844         --construct_count;
00845 
00846         icurrent = inext;
00847 
00848         // Are we there yet?
00849         if (icurrent != iend)
00850         {
00851           // At the end of this bucket?
00852           if ((icurrent == pbucket->end()))
00853           {
00854             // Find the next non-empty one.
00855             do
00856             {
00857               ++pbucket;
00858             } while (pbucket->empty());
00859 
00860             iprevious = pbucket->before_begin();
00861             icurrent = pbucket->begin();
00862           }
00863         }
00864       }
00865 
00866       return result;
00867     }
00868 
00869     //*************************************************************************
00870     /// Clears the unordered_multimap.
00871     //*************************************************************************
00872     void clear()
00873     {
00874       initialise();
00875     }
00876 
00877     //*********************************************************************
00878     /// Counts an element.
00879     ///\param key The key to search for.
00880     ///\return 1 if the key exists, otherwise 0.
00881     //*********************************************************************
00882     size_t count(key_parameter_t key) const
00883     {
00884       size_t n = 0;
00885       const_iterator f = find(key);
00886       const_iterator l = f;
00887 
00888       if (l != end())
00889       {
00890         ++l;
00891         ++n;
00892 
00893         while ((l != end()) && (key == l->first))
00894         {
00895           ++l;
00896           ++n;
00897         }
00898       }
00899 
00900       return n;
00901     }
00902 
00903     //*********************************************************************
00904     /// Finds an element.
00905     ///\param key The key to search for.
00906     ///\return An iterator to the element if the key exists, otherwise end().
00907     //*********************************************************************
00908     iterator find(key_parameter_t key)
00909     {
00910       size_t index = get_bucket_index(key);
00911 
00912       bucket_t* pbucket = pbuckets + index;
00913       bucket_t& bucket = *pbucket;
00914 
00915       // Is the bucket not empty?
00916       if (!bucket.empty())
00917       {
00918         // Step though the list until we find the end or an equivalent key.
00919         local_iterator inode = bucket.begin();
00920         local_iterator iend = bucket.end();
00921 
00922         while (inode != iend)
00923         {
00924           // Do we have this one?
00925           if (key_equal_function(key, inode->key_value_pair.first))
00926           {
00927             return iterator((pbuckets + number_of_buckets), pbucket, inode);
00928           }
00929 
00930           ++inode;
00931         }
00932       }
00933 
00934       return end();
00935     }
00936 
00937     //*********************************************************************
00938     /// Finds an element.
00939     ///\param key The key to search for.
00940     ///\return An iterator to the element if the key exists, otherwise end().
00941     //*********************************************************************
00942     const_iterator find(key_parameter_t key) const
00943     {
00944       size_t index = get_bucket_index(key);
00945 
00946       bucket_t* pbucket = pbuckets + index;
00947       bucket_t& bucket = *pbucket;
00948 
00949       // Is the bucket not empty?
00950       if (!bucket.empty())
00951       {
00952         // Step though the list until we find the end or an equivalent key.
00953         local_iterator inode = bucket.begin();
00954         local_iterator iend = bucket.end();
00955 
00956         while (inode != iend)
00957         {
00958           // Do we have this one?
00959           if (key_equal_function(key, inode->key_value_pair.first))
00960           {
00961             return const_iterator((pbuckets + number_of_buckets), pbucket, inode);
00962           }
00963 
00964           ++inode;
00965         }
00966       }
00967 
00968       return end();
00969     }
00970 
00971     //*********************************************************************
00972     /// Returns a range containing all elements with key key in the container.
00973     /// The range is defined by two iterators, the first pointing to the first
00974     /// element of the wanted range and the second pointing past the last
00975     /// element of the range.
00976     ///\param key The key to search for.
00977     ///\return An iterator pair to the range of elements if the key exists, otherwise end().
00978     //*********************************************************************
00979     std::pair<iterator, iterator> equal_range(key_parameter_t key)
00980     {
00981       iterator f = find(key);
00982       iterator l = f;
00983 
00984       if (l != end())
00985       {
00986         ++l;
00987 
00988         while ((l != end()) && (key == l->first))
00989         {
00990           ++l;
00991         }
00992       }
00993 
00994       return std::pair<iterator, iterator>(f, l);
00995     }
00996 
00997     //*********************************************************************
00998     /// Returns a range containing all elements with key key in the container.
00999     /// The range is defined by two iterators, the first pointing to the first
01000     /// element of the wanted range and the second pointing past the last
01001     /// element of the range.
01002     ///\param key The key to search for.
01003     ///\return A const iterator pair to the range of elements if the key exists, otherwise end().
01004     //*********************************************************************
01005     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
01006     {
01007       const_iterator f = find(key);
01008       const_iterator l = f;
01009 
01010       if (l != end())
01011       {
01012         ++l;
01013 
01014         while ((l != end()) && (key == l->first))
01015         {
01016           ++l;
01017         }
01018       }
01019 
01020       return std::pair<const_iterator, const_iterator>(f, l);
01021     }
01022 
01023     //*************************************************************************
01024     /// Gets the size of the unordered_multimap.
01025     //*************************************************************************
01026     size_type size() const
01027     {
01028       return pnodepool->size();
01029     }
01030 
01031     //*************************************************************************
01032     /// Gets the maximum possible size of the unordered_multimap.
01033     //*************************************************************************
01034     size_type max_size() const
01035     {
01036       return pnodepool->max_size();
01037     }
01038 
01039     //*************************************************************************
01040     /// Checks to see if the unordered_multimap is empty.
01041     //*************************************************************************
01042     bool empty() const
01043     {
01044       return pnodepool->empty();
01045     }
01046 
01047     //*************************************************************************
01048     /// Checks to see if the unordered_multimap is full.
01049     //*************************************************************************
01050     bool full() const
01051     {
01052       return pnodepool->full();
01053     }
01054 
01055     //*************************************************************************
01056     /// Returns the remaining capacity.
01057     ///\return The remaining capacity.
01058     //*************************************************************************
01059     size_t available() const
01060     {
01061       return pnodepool->available();
01062     }
01063 
01064     //*************************************************************************
01065     /// Returns the load factor = size / bucket_count.
01066     ///\return The load factor = size / bucket_count.
01067     //*************************************************************************
01068     float load_factor() const
01069     {
01070       return static_cast<float>(size()) / static_cast<float>(bucket_count());
01071     }
01072 
01073     //*************************************************************************
01074     /// Returns the function that hashes the keys.
01075     ///\return The function that hashes the keys..
01076     //*************************************************************************
01077     hasher hash_function() const
01078     {
01079       return key_hash_function;
01080     }
01081 
01082     //*************************************************************************
01083     /// Returns the function that compares the keys.
01084     ///\return The function that compares the keys..
01085     //*************************************************************************
01086     key_equal key_eq() const
01087     {
01088       return key_equal_function;
01089     }
01090 
01091     //*************************************************************************
01092     /// Assignment operator.
01093     //*************************************************************************
01094     iunordered_multimap& operator = (const iunordered_multimap& rhs)
01095     {
01096       // Skip if doing self assignment
01097       if (this != &rhs)
01098       {
01099         assign(rhs.cbegin(), rhs.cend());
01100       }
01101 
01102       return *this;
01103     }
01104 
01105   protected:
01106 
01107     //*********************************************************************
01108     /// Constructor.
01109     //*********************************************************************
01110     iunordered_multimap(pool_t& node_pool_, bucket_t* pbuckets_, size_t number_of_buckets_)
01111       : pnodepool(&node_pool_),
01112         pbuckets(pbuckets_),
01113         number_of_buckets(number_of_buckets_)
01114     {
01115     }
01116 
01117     //*********************************************************************
01118     /// Initialise the unordered_multimap.
01119     //*********************************************************************
01120     void initialise()
01121     {
01122       if (!empty())
01123       {
01124         // For each bucket...
01125         for (size_t i = 0; i < number_of_buckets; ++i)
01126         {
01127           bucket_t& bucket = pbuckets[i];
01128 
01129           if (!bucket.empty())
01130           {
01131             // For each item in the bucket...
01132             local_iterator it = bucket.begin();
01133 
01134             while (it != bucket.end())
01135             {
01136               // Destroy the value contents.
01137               it->key_value_pair.~value_type();
01138               ++it;
01139               --construct_count;
01140             }
01141 
01142             // Now it's safe to clear the bucket.
01143             bucket.clear();
01144           }
01145         }
01146 
01147         // Now it's safe to clear the entire pool in one go.
01148         pnodepool->release_all();
01149       }
01150 
01151       first = pbuckets;
01152       last = first;
01153     }
01154 
01155   private:
01156 
01157     //*********************************************************************
01158     /// Adjust the first and last markers according to the new entry.
01159     //*********************************************************************
01160     void adjust_first_last_markers(bucket_t* pbucket)
01161     {
01162       if (pbucket < first)
01163       {
01164         first = pbucket;
01165       }
01166       else if (pbucket > last)
01167       {
01168         last = pbucket;
01169       }
01170     }
01171 
01172     // Disable copy construction.
01173     iunordered_multimap(const iunordered_multimap&);
01174 
01175     /// The pool of data nodes used in the list.
01176     pool_t* pnodepool;
01177 
01178     /// The bucket list.
01179     bucket_t* pbuckets;
01180 
01181     /// The number of buckets.
01182     const size_t number_of_buckets;
01183 
01184     /// The first and last iterators to buckets with values.
01185     bucket_t* first;
01186     bucket_t* last;
01187 
01188     /// The function that creates the hashes.
01189     hasher key_hash_function;
01190 
01191     /// The function that compares the keys for equality.
01192     key_equal key_equal_function;
01193 
01194     /// For library debugging purposes only.
01195     etl::debug_count construct_count;
01196   };
01197 
01198   //***************************************************************************
01199   /// Equal operator.
01200   ///\param lhs Reference to the first unordered_multimap.
01201   ///\param rhs Reference to the second unordered_multimap.
01202   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
01203   ///\ingroup unordered_multimap
01204   //***************************************************************************
01205   template <typename TKey, typename TMapped, typename TKeyCompare>
01206   bool operator ==(const etl::iunordered_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_multimap<TKey, TMapped, TKeyCompare>& rhs)
01207   {
01208     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
01209   }
01210 
01211   //***************************************************************************
01212   /// Not equal operator.
01213   ///\param lhs Reference to the first unordered_multimap.
01214   ///\param rhs Reference to the second unordered_multimap.
01215   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
01216   ///\ingroup unordered_multimap
01217   //***************************************************************************
01218   template <typename TKey, typename TMapped, typename TKeyCompare>
01219   bool operator !=(const etl::iunordered_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::iunordered_multimap<TKey, TMapped, TKeyCompare>& rhs)
01220   {
01221     return !(lhs == rhs);
01222   }
01223 
01224   //*************************************************************************
01225   /// A templated unordered_multimap implementation that uses a fixed size buffer.
01226   //*************************************************************************
01227   template <typename TKey, typename TValue, const size_t MAX_SIZE_, const size_t MAX_BUCKETS_ = MAX_SIZE_, typename THash = etl::hash<TKey>, typename TKeyEqual = std::equal_to<TKey> >
01228   class unordered_multimap : public etl::iunordered_multimap<TKey, TValue, THash, TKeyEqual>
01229   {
01230   private:
01231 
01232     typedef etl::iunordered_multimap<TKey, TValue, THash, TKeyEqual>  base ;
01233 
01234   public:
01235 
01236     static const size_t MAX_SIZE    = MAX_SIZE_;
01237     static const size_t MAX_BUCKETS = MAX_BUCKETS_;
01238 
01239     //*************************************************************************
01240     /// Default constructor.
01241     //*************************************************************************
01242     unordered_multimap()
01243       : base (node_pool, buckets, MAX_BUCKETS)
01244     {
01245       base::initialise();
01246     }
01247 
01248     //*************************************************************************
01249     /// Copy constructor.
01250     //*************************************************************************
01251     unordered_multimap(const unordered_multimap& other)
01252       : base (node_pool, buckets, MAX_BUCKETS)
01253     {
01254       base::assign(other.cbegin(), other.cend());
01255     }
01256 
01257     //*************************************************************************
01258     /// Constructor, from an iterator range.
01259     ///\tparam TIterator The iterator type.
01260     ///\param first The iterator to the first element.
01261     ///\param last  The iterator to the last element + 1.
01262     //*************************************************************************
01263     template <typename TIterator>
01264     unordered_multimap(TIterator first_, TIterator last_)
01265       : base (node_pool, buckets, MAX_BUCKETS)
01266     {
01267       base::assign(first_, last_);
01268     }
01269 
01270     //*************************************************************************
01271     /// Destructor.
01272     //*************************************************************************
01273     ~unordered_multimap()
01274     {
01275       base::initialise();
01276     }
01277 
01278     //*************************************************************************
01279     /// Assignment operator.
01280     //*************************************************************************
01281     unordered_multimap& operator = (const unordered_multimap& rhs)
01282     {
01283       // Skip if doing self assignment
01284       if (this != &rhs)
01285       {
01286         base::assign(rhs.cbegin(), rhs.cend());
01287       }
01288 
01289       return *this;
01290     }
01291 
01292   private:
01293 
01294     /// The pool of nodes used for the unordered_multimap.
01295     etl::pool<typename base::node_t, MAX_SIZE>  node_pool;
01296 
01297     /// The buckets of node lists.
01298     etl::intrusive_forward_list<typename base::node_t>  buckets[MAX_BUCKETS_];
01299   };
01300 }
01301 
01302 #undef ETL_FILE
01303 
01304 #endif
01305