reference_flat_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) 2017 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_REFERENCE_FLAT_MULTIMAP_BASE__
00032 #define __ETL_REFERENCE_FLAT_MULTIMAP_BASE__
00033 
00034 #include <stddef.h>
00035 
00036 #include "platform.h "
00037 #include "exception.h "
00038 #include "error_handler.h "
00039 #include "debug_count.h "
00040 #include "vector.h "
00041 
00042 #undef ETL_FILE
00043 #define ETL_FILE "31"
00044 
00045 namespace etl
00046 {
00047   //***************************************************************************
00048   ///\ingroup reference_flat_multimap
00049   /// Exception base for reference_flat_multimaps
00050   //***************************************************************************
00051   class flat_multimap_exception : public exception
00052   {
00053   public:
00054 
00055     flat_multimap_exception(string_type reason_, string_type file_name_, numeric_type line_number_)
00056       : exception(reason_, file_name_, line_number_)
00057     {
00058     }
00059   };
00060 
00061   //***************************************************************************
00062   ///\ingroup reference_flat_multimap
00063   /// Vector full exception.
00064   //***************************************************************************
00065   class flat_multimap_full : public flat_multimap_exception
00066   {
00067   public:
00068 
00069     flat_multimap_full(string_type file_name_, numeric_type line_number_)
00070       : flat_multimap_exception(ETL_ERROR_TEXT("flat_multimap:full", ETL_FILE"A"), file_name_, line_number_)
00071     {
00072     }
00073   };
00074 
00075   //***************************************************************************
00076   /// The base class for specifically sized reference_flat_multimaps.
00077   /// Can be used as a reference type for all reference_flat_multimaps containing a specific type.
00078   ///\ingroup reference_flat_multimap
00079   //***************************************************************************
00080   template <typename TKey, typename TMapped, typename TKeyCompare = std::less<TKey> >
00081   class ireference_flat_multimap
00082   {
00083   public:
00084 
00085     typedef std::pair<const TKey, TMapped> value_type;
00086 
00087   protected:
00088 
00089     typedef etl::ivector<value_type*>  lookup_t ;
00090 
00091   public:
00092 
00093     typedef TKey              key_type;
00094     typedef TMapped           mapped_type;
00095     typedef TKeyCompare       key_compare;
00096     typedef value_type&       reference;
00097     typedef const value_type& const_reference;
00098     typedef value_type*       pointer;
00099     typedef const value_type* const_pointer;
00100     typedef size_t            size_type;
00101 
00102     //*************************************************************************
00103     class iterator : public std::iterator<std::bidirectional_iterator_tag, value_type>
00104     {
00105     public:
00106 
00107       friend class ireference_flat_multimap;
00108 
00109       iterator()
00110       {
00111       }
00112 
00113       iterator(typename lookup_t::iterator ilookup_)
00114         : ilookup(ilookup_)
00115       {
00116       }
00117 
00118       iterator(const iterator& other)
00119         : ilookup(other.ilookup)
00120       {
00121       }
00122 
00123       iterator& operator =(const iterator& other)
00124       {
00125         ilookup = other.ilookup;
00126         return *this;
00127       }
00128 
00129       iterator& operator ++()
00130       {
00131         ++ilookup;
00132         return *this;
00133       }
00134 
00135       iterator operator ++(int)
00136       {
00137         iterator temp(*this);
00138         ++ilookup;
00139         return temp;
00140       }
00141 
00142       iterator& operator --()
00143       {
00144         --ilookup;
00145         return *this;
00146       }
00147 
00148       iterator operator --(int)
00149       {
00150         iterator temp(*this);
00151         --ilookup;
00152         return temp;
00153       }
00154 
00155       reference operator *()
00156       {
00157         return *(*ilookup);
00158       }
00159 
00160       const_reference operator *() const
00161       {
00162         return *(*ilookup);
00163       }
00164 
00165       pointer operator &()
00166       {
00167         return etl::addressof(*(*ilookup));
00168       }
00169 
00170       const_pointer operator &() const
00171       {
00172         return &(*(*ilookup));
00173       }
00174 
00175       pointer operator ->()
00176       {
00177         return etl::addressof(*(*ilookup));
00178       }
00179 
00180       const_pointer operator ->() const
00181       {
00182         return etl::addressof(*(*ilookup));
00183       }
00184 
00185       friend bool operator == (const iterator& lhs, const iterator& rhs)
00186       {
00187         return lhs.ilookup == rhs.ilookup;
00188       }
00189 
00190       friend bool operator != (const iterator& lhs, const iterator& rhs)
00191       {
00192         return !(lhs == rhs);
00193       }
00194 
00195     private:
00196 
00197       typename lookup_t::iterator ilookup;
00198     };
00199 
00200     //*************************************************************************
00201     class const_iterator : public std::iterator<std::bidirectional_iterator_tag, const value_type>
00202     {
00203     public:
00204 
00205       friend class ireference_flat_multimap;
00206 
00207       const_iterator()
00208       {
00209       }
00210 
00211       const_iterator(typename lookup_t::const_iterator ilookup_)
00212         : ilookup(ilookup_)
00213       {
00214       }
00215 
00216       const_iterator(const iterator& other)
00217         : ilookup(other.ilookup)
00218       {
00219       }
00220 
00221       const_iterator(const const_iterator& other)
00222         : ilookup(other.ilookup)
00223       {
00224       }
00225 
00226       const_iterator& operator =(const iterator& other)
00227       {
00228         ilookup = other.ilookup;
00229         return *this;
00230       }
00231 
00232       const_iterator& operator =(const const_iterator& other)
00233       {
00234         ilookup = other.ilookup;
00235         return *this;
00236       }
00237 
00238       const_iterator& operator ++()
00239       {
00240         ++ilookup;
00241         return *this;
00242       }
00243 
00244       const_iterator operator ++(int)
00245       {
00246         const_iterator temp(*this);
00247         ++ilookup;
00248         return temp;
00249       }
00250 
00251       const_iterator& operator --()
00252       {
00253         --ilookup;
00254         return *this;
00255       }
00256 
00257       const_iterator operator --(int)
00258       {
00259         const_iterator temp(*this);
00260         --ilookup;
00261         return temp;
00262       }
00263 
00264       const_reference operator *() const
00265       {
00266         return *(*ilookup);
00267       }
00268 
00269       const_pointer operator &() const
00270       {
00271         return etl::addressof(*(*ilookup));
00272       }
00273 
00274       const_pointer operator ->() const
00275       {
00276         return etl::addressof(*(*ilookup));
00277       }
00278 
00279       friend bool operator == (const const_iterator& lhs, const const_iterator& rhs)
00280       {
00281         return lhs.ilookup == rhs.ilookup;
00282       }
00283 
00284       friend bool operator != (const const_iterator& lhs, const const_iterator& rhs)
00285       {
00286         return !(lhs == rhs);
00287       }
00288 
00289     private:
00290 
00291       typename lookup_t::const_iterator ilookup;
00292     };
00293 
00294     typedef std::reverse_iterator<iterator>       reverse_iterator;
00295     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00296     typedef typename std::iterator_traits<iterator>::difference_type difference_type;
00297 
00298   protected:
00299 
00300     typedef typename etl::parameter_type<TKey>::type key_parameter_t;
00301 
00302   private:
00303 
00304     //*********************************************************************
00305     /// How to compare elements and keys.
00306     //*********************************************************************
00307     class compare
00308     {
00309     public:
00310 
00311       bool operator ()(const value_type& element, key_type key) const
00312       {
00313         return key_compare()(element.first, key);
00314       }
00315 
00316       bool operator ()(key_type key, const value_type& element) const
00317       {
00318         return key_compare()(key, element.first);
00319       }
00320     };
00321 
00322   public:
00323 
00324     //*********************************************************************
00325     /// Returns an iterator to the beginning of the reference_flat_multimap.
00326     ///\return An iterator to the beginning of the reference_flat_multimap.
00327     //*********************************************************************
00328     iterator begin()
00329     {
00330       return iterator(lookup.begin());
00331     }
00332 
00333     //*********************************************************************
00334     /// Returns a const_iterator to the beginning of the reference_flat_multimap.
00335     ///\return A const iterator to the beginning of the reference_flat_multimap.
00336     //*********************************************************************
00337     const_iterator begin() const
00338     {
00339       return const_iterator(lookup.begin());
00340     }
00341 
00342     //*********************************************************************
00343     /// Returns an iterator to the end of the reference_flat_multimap.
00344     ///\return An iterator to the end of the reference_flat_multimap.
00345     //*********************************************************************
00346     iterator end()
00347     {
00348       return iterator(lookup.end());
00349     }
00350 
00351     //*********************************************************************
00352     /// Returns a const_iterator to the end of the reference_flat_multimap.
00353     ///\return A const iterator to the end of the reference_flat_multimap.
00354     //*********************************************************************
00355     const_iterator end() const
00356     {
00357       return const_iterator(lookup.end());
00358     }
00359 
00360     //*********************************************************************
00361     /// Returns a const_iterator to the beginning of the reference_flat_multimap.
00362     ///\return A const iterator to the beginning of the reference_flat_multimap.
00363     //*********************************************************************
00364     const_iterator cbegin() const
00365     {
00366       return const_iterator(lookup.cbegin());
00367     }
00368 
00369     //*********************************************************************
00370     /// Returns a const_iterator to the end of the reference_flat_multimap.
00371     ///\return A const iterator to the end of the reference_flat_multimap.
00372     //*********************************************************************
00373     const_iterator cend() const
00374     {
00375       return const_iterator(lookup.cend());
00376     }
00377 
00378     //*********************************************************************
00379     /// Returns an reverse iterator to the reverse beginning of the reference_flat_multimap.
00380     ///\return Iterator to the reverse beginning of the reference_flat_multimap.
00381     //*********************************************************************
00382     reverse_iterator rbegin()
00383     {
00384       return reverse_iterator(lookup.rbegin());
00385     }
00386 
00387     //*********************************************************************
00388     /// Returns a const reverse iterator to the reverse beginning of the reference_flat_multimap.
00389     ///\return Const iterator to the reverse beginning of the reference_flat_multimap.
00390     //*********************************************************************
00391     const_reverse_iterator rbegin() const
00392     {
00393       return const_reverse_iterator(lookup.rbegin());
00394     }
00395 
00396     //*********************************************************************
00397     /// Returns a reverse iterator to the end + 1 of the reference_flat_multimap.
00398     ///\return Reverse iterator to the end + 1 of the reference_flat_multimap.
00399     //*********************************************************************
00400     reverse_iterator rend()
00401     {
00402       return reverse_iterator(lookup.rend());
00403     }
00404 
00405     //*********************************************************************
00406     /// Returns a const reverse iterator to the end + 1 of the reference_flat_multimap.
00407     ///\return Const reverse iterator to the end + 1 of the reference_flat_multimap.
00408     //*********************************************************************
00409     const_reverse_iterator rend() const
00410     {
00411       return const_reverse_iterator(lookup.rend());
00412     }
00413 
00414     //*********************************************************************
00415     /// Returns a const reverse iterator to the reverse beginning of the reference_flat_multimap.
00416     ///\return Const reverse iterator to the reverse beginning of the reference_flat_multimap.
00417     //*********************************************************************
00418     const_reverse_iterator crbegin() const
00419     {
00420       return const_reverse_iterator(lookup.crbegin());
00421     }
00422 
00423     //*********************************************************************
00424     /// Returns a const reverse iterator to the end + 1 of the reference_flat_multimap.
00425     ///\return Const reverse iterator to the end + 1 of the reference_flat_multimap.
00426     //*********************************************************************
00427     const_reverse_iterator crend() const
00428     {
00429       return const_reverse_iterator(lookup.crend());
00430     }
00431 
00432     //*********************************************************************
00433     /// Assigns values to the reference_flat_multimap.
00434     /// If asserts or exceptions are enabled, emits reference_flat_multimap_full if the reference_flat_multimap does not have enough free space.
00435     /// If asserts or exceptions are enabled, emits reference_flat_multimap_iterator if the iterators are reversed.
00436     ///\param first The iterator to the first element.
00437     ///\param last  The iterator to the last element + 1.
00438     //*********************************************************************
00439     template <typename TIterator>
00440     void assign(TIterator first, TIterator last)
00441     {
00442 #if defined(ETL_DEBUG)
00443       difference_type d = std::distance(first, last);
00444       ETL_ASSERT(d <= difference_type(capacity()), ETL_ERROR(flat_multimap_full));
00445 #endif
00446 
00447       clear();
00448 
00449       while (first != last)
00450       {
00451         insert(*first++);
00452       }
00453     }
00454 
00455     //*********************************************************************
00456     /// Inserts a value to the reference_flat_multimap.
00457     /// If asserts or exceptions are enabled, emits reference_flat_multimap_full if the reference_flat_multimap is already full.
00458     ///\param value    The value to insert.
00459     //*********************************************************************
00460     std::pair<iterator, bool> insert(value_type& value)
00461     {
00462       ETL_ASSERT(!lookup.full(), ETL_ERROR(flat_multimap_full));
00463 
00464       std::pair<iterator, bool> result(end(), false);
00465 
00466       iterator i_element = lower_bound(value.first);
00467 
00468       return insert_at(i_element, value);
00469     }
00470 
00471     //*********************************************************************
00472     /// Inserts a value to the flast_multi.
00473     /// If asserts or exceptions are enabled, emits flat_map_full if the flat_map is already full.
00474     ///\param position The position to insert at.
00475     ///\param value    The value to insert.
00476     //*********************************************************************
00477     iterator insert(iterator position, const value_type& value)
00478     {
00479       return insert(value).first;
00480     }
00481 
00482     //*********************************************************************
00483     /// Inserts a range of values to the reference_flat_multimap.
00484     /// If asserts or exceptions are enabled, emits reference_flat_multimap_full if the reference_flat_multimap does not have enough free space.
00485     ///\param position The position to insert at.
00486     ///\param first    The first element to add.
00487     ///\param last     The last + 1 element to add.
00488     //*********************************************************************
00489     template <class TIterator>
00490     void insert(TIterator first, TIterator last)
00491     {
00492       while (first != last)
00493       {
00494         insert(*first++);
00495       }
00496     }
00497 
00498     //*********************************************************************
00499     /// Erases an element.
00500     ///\param key The key to erase.
00501     ///\return The number of elements erased. 0 or 1.
00502     //*********************************************************************
00503     size_t erase(key_parameter_t key)
00504     {
00505       std::pair<iterator, iterator> range = equal_range(key);
00506 
00507       if (range.first == end())
00508       {
00509         return 0;
00510       }
00511       else
00512       {
00513         size_t d = std::distance(range.first, range.second);
00514         erase(range.first, range.second);
00515         return d;
00516       }
00517     }
00518 
00519     //*********************************************************************
00520     /// Erases an element.
00521     ///\param i_element Iterator to the element.
00522     //*********************************************************************
00523     void erase(iterator i_element)
00524     {
00525       lookup.erase(i_element.ilookup);
00526     }
00527 
00528     //*********************************************************************
00529     /// Erases a range of elements.
00530     /// The range includes all the elements between first and last, including the
00531     /// element pointed by first, but not the one pointed by last.
00532     ///\param first Iterator to the first element.
00533     ///\param last  Iterator to the last element.
00534     //*********************************************************************
00535     void erase(iterator first, iterator last)
00536     {
00537       lookup.erase(first.ilookup, last.ilookup);
00538     }
00539 
00540     //*************************************************************************
00541     /// Clears the reference_flat_multimap.
00542     //*************************************************************************
00543     void clear()
00544     {
00545       erase(begin(), end());
00546     }
00547 
00548     //*********************************************************************
00549     /// Finds an element.
00550     ///\param key The key to search for.
00551     ///\return An iterator pointing to the element or end() if not found.
00552     //*********************************************************************
00553     iterator find(key_parameter_t key)
00554     {
00555       iterator itr = lower_bound(key);
00556 
00557       if (itr != end())
00558       {
00559         if (!key_compare()(itr->first, key) && !key_compare()(key, itr->first))
00560         {
00561           return itr;
00562         }
00563         else
00564         {
00565           return end();
00566         }
00567       }
00568 
00569       return end();
00570     }
00571 
00572     //*********************************************************************
00573     /// Finds an element.
00574     ///\param key The key to search for.
00575     ///\return An iterator pointing to the element or end() if not found.
00576     //*********************************************************************
00577     const_iterator find(key_parameter_t key) const
00578     {
00579       const_iterator itr = lower_bound(key);
00580 
00581       if (itr != end())
00582       {
00583         if (!key_compare()(itr->first, key) && !key_compare()(key, itr->first))
00584         {
00585           return itr;
00586         }
00587         else
00588         {
00589           return end();
00590         }
00591       }
00592 
00593       return end();
00594     }
00595 
00596     //*********************************************************************
00597     /// Counts an element.
00598     ///\param key The key to search for.
00599     ///\return 1 if the key exists, otherwise 0.
00600     //*********************************************************************
00601     size_t count(key_parameter_t key) const
00602     {
00603       std::pair<const_iterator, const_iterator> range = equal_range(key);
00604 
00605       return std::distance(range.first, range.second);
00606     }
00607 
00608     //*********************************************************************
00609     /// Finds the lower bound of a key
00610     ///\param key The key to search for.
00611     ///\return An iterator.
00612     //*********************************************************************
00613     iterator lower_bound(key_parameter_t key)
00614     {
00615       return std::lower_bound(begin(), end(), key, compare());
00616     }
00617 
00618     //*********************************************************************
00619     /// Finds the lower bound of a key
00620     ///\param key The key to search for.
00621     ///\return An iterator.
00622     //*********************************************************************
00623     const_iterator lower_bound(key_parameter_t key) const
00624     {
00625       return std::lower_bound(cbegin(), cend(), key, compare());
00626     }
00627 
00628     //*********************************************************************
00629     /// Finds the upper bound of a key
00630     ///\param key The key to search for.
00631     ///\return An iterator.
00632     //*********************************************************************
00633     iterator upper_bound(key_parameter_t key)
00634     {
00635       return std::upper_bound(begin(), end(), key, compare());
00636     }
00637 
00638     //*********************************************************************
00639     /// Finds the upper bound of a key
00640     ///\param key The key to search for.
00641     ///\return An iterator.
00642     //*********************************************************************
00643     const_iterator upper_bound(key_parameter_t key) const
00644     {
00645       return std::upper_bound(begin(), end(), key, compare());
00646     }
00647 
00648     //*********************************************************************
00649     /// Finds the range of equal elements of a key
00650     ///\param key The key to search for.
00651     ///\return An iterator pair.
00652     //*********************************************************************
00653     std::pair<iterator, iterator> equal_range(key_parameter_t key)
00654     {
00655       iterator i_lower = std::lower_bound(begin(), end(), key, compare());
00656 
00657       return std::make_pair(i_lower, std::upper_bound(i_lower, end(), key, compare()));
00658     }
00659 
00660     //*********************************************************************
00661     /// Finds the range of equal elements of a key
00662     ///\param key The key to search for.
00663     ///\return An iterator pair.
00664     //*********************************************************************
00665     std::pair<const_iterator, const_iterator> equal_range(key_parameter_t key) const
00666     {
00667       const_iterator i_lower = std::lower_bound(cbegin(), cend(), key, compare());
00668 
00669       return std::make_pair(i_lower, std::upper_bound(i_lower, cend(), key, compare()));
00670     }
00671 
00672     //*************************************************************************
00673     /// Gets the current size of the flat_multiset.
00674     ///\return The current size of the flat_multiset.
00675     //*************************************************************************
00676     size_type size() const
00677     {
00678       return lookup.size();
00679     }
00680 
00681     //*************************************************************************
00682     /// Checks the 'empty' state of the flat_multiset.
00683     ///\return <b>true</b> if empty.
00684     //*************************************************************************
00685     bool empty() const
00686     {
00687       return lookup.empty();
00688     }
00689 
00690     //*************************************************************************
00691     /// Checks the 'full' state of the flat_multiset.
00692     ///\return <b>true</b> if full.
00693     //*************************************************************************
00694     bool full() const
00695     {
00696       return lookup.full();
00697     }
00698 
00699     //*************************************************************************
00700     /// Returns the capacity of the flat_multiset.
00701     ///\return The capacity of the flat_multiset.
00702     //*************************************************************************
00703     size_type capacity() const
00704     {
00705       return lookup.capacity();
00706     }
00707 
00708     //*************************************************************************
00709     /// Returns the maximum possible size of the flat_multiset.
00710     ///\return The maximum size of the flat_multiset.
00711     //*************************************************************************
00712     size_type max_size() const
00713     {
00714       return lookup.max_size();
00715     }
00716 
00717     //*************************************************************************
00718     /// Returns the remaining capacity.
00719     ///\return The remaining capacity.
00720     //*************************************************************************
00721     size_t available() const
00722     {
00723       return lookup.available();
00724     }
00725 
00726   protected:
00727 
00728     //*********************************************************************
00729     /// Constructor.
00730     //*********************************************************************
00731     ireference_flat_multimap(lookup_t & lookup_)
00732       : lookup(lookup_)
00733     {
00734     }
00735 
00736     //*********************************************************************
00737     /// Inserts a value to the reference_flat_multimap.
00738     ///\param i_element The place to insert.
00739     ///\param value     The value to insert.
00740     //*********************************************************************
00741     std::pair<iterator, bool> insert_at(iterator i_element, value_type& value)
00742     {
00743       std::pair<iterator, bool> result(end(), false);
00744 
00745       if (i_element == end())
00746       {
00747         // At the end.
00748         lookup.push_back(&value);
00749         result.first = --end();
00750         result.second = true;
00751       }
00752       else
00753       {
00754         // Not at the end.
00755         lookup.insert(i_element.ilookup, &value);
00756         result.first = i_element;
00757         result.second = true;
00758       }
00759 
00760       return result;
00761     }
00762 
00763   private:
00764 
00765     // Disable copy construction and assignment.
00766     ireference_flat_multimap(const ireference_flat_multimap&);
00767     ireference_flat_multimap& operator = (const ireference_flat_multimap&);
00768 
00769     lookup_t&  lookup;
00770   };
00771 
00772   //***************************************************************************
00773   /// Equal operator.
00774   ///\param lhs Reference to the first reference_flat_multimap.
00775   ///\param rhs Reference to the second reference_flat_multimap.
00776   ///\return <b>true</b> if the arrays are equal, otherwise <b>false</b>
00777   ///\ingroup reference_flat_multimap
00778   //***************************************************************************
00779   template <typename TKey, typename TMapped, typename TKeyCompare>
00780   bool operator ==(const etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare>& rhs)
00781   {
00782     return (lhs.size() == rhs.size()) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
00783   }
00784 
00785   //***************************************************************************
00786   /// Not equal operator.
00787   ///\param lhs Reference to the first reference_flat_multimap.
00788   ///\param rhs Reference to the second reference_flat_multimap.
00789   ///\return <b>true</b> if the arrays are not equal, otherwise <b>false</b>
00790   ///\ingroup reference_flat_multimap
00791   //***************************************************************************
00792   template <typename TKey, typename TMapped, typename TKeyCompare>
00793   bool operator !=(const etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare>& lhs, const etl::ireference_flat_multimap<TKey, TMapped, TKeyCompare>& rhs)
00794   {
00795     return !(lhs == rhs);
00796   }
00797 
00798   template <typename TKey, typename TValue, const size_t MAX_SIZE_, typename TCompare = std::less<TKey> >
00799   //***************************************************************************
00800   /// A reference_flat_multimap implementation that uses a fixed size buffer.
00801   ///\tparam TKey     The key type.
00802   ///\tparam TValue   The value type.
00803   ///\tparam TCompare The type to compare keys. Default = std::less<TKey>
00804   ///\tparam MAX_SIZE_ The maximum number of elements that can be stored.
00805   ///\ingroup reference_flat_multimap
00806   //***************************************************************************
00807   class reference_flat_multimap : public ireference_flat_multimap<TKey, TValue, TCompare>
00808   {
00809   public:
00810 
00811     static const size_t MAX_SIZE = MAX_SIZE_;
00812 
00813     //*************************************************************************
00814     /// Constructor.
00815     //*************************************************************************
00816     reference_flat_multimap()
00817       : ireference_flat_multimap<TKey, TValue, TCompare>(lookup)
00818     {
00819     }
00820 
00821     //*************************************************************************
00822     /// Copy constructor.
00823     //*************************************************************************
00824     reference_flat_multimap(const reference_flat_multimap& other)
00825       : ireference_flat_multimap<TKey, TValue, TCompare>(lookup)
00826     {
00827       ireference_flat_multimap<TKey, TValue, TCompare>::assign(other.cbegin(), other.cend());
00828     }
00829 
00830     //*************************************************************************
00831     /// Constructor, from an iterator range.
00832     ///\tparam TIterator The iterator type.
00833     ///\param first The iterator to the first element.
00834     ///\param last  The iterator to the last element + 1.
00835     //*************************************************************************
00836     template <typename TIterator>
00837     reference_flat_multimap(TIterator first, TIterator last)
00838       : ireference_flat_multimap<TKey, TValue, TCompare>(lookup)
00839     {
00840       ireference_flat_multimap<TKey, TValue, TCompare>::assign(first, last);
00841     }
00842 
00843     //*************************************************************************
00844     /// Destructor.
00845     //*************************************************************************
00846     ~reference_flat_multimap()
00847     {
00848       ireference_flat_multimap<TKey, TValue, TCompare>::clear();
00849     }
00850 
00851   private:
00852 
00853     typedef typename ireference_flat_multimap<TKey, TValue, TCompare>::value_type node_t;
00854 
00855     // The vector that stores pointers to the nodes.
00856     etl::vector<node_t*, MAX_SIZE>  lookup;
00857   };
00858 }
00859 
00860 #undef ETL_FILE
00861 
00862 #endif
00863