31#ifndef ETL_UNORDERED_MULTISET_INCLUDED
32#define ETL_UNORDERED_MULTISET_INCLUDED
126 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
162 return (
lhs.key ==
rhs.key);
178 typedef typename bucket_t::iterator local_iterator;
179 typedef typename bucket_t::const_iterator const_local_iterator;
206 : pbuckets_end(
other.pbuckets_end)
207 , pbucket(
other.pbucket)
218 if (inode == pbucket->end())
222 while ((pbucket != pbuckets_end) && (pbucket->empty()))
228 if (pbucket != pbuckets_end)
230 inode = pbucket->begin();
248 pbuckets_end =
other.pbuckets_end;
249 pbucket =
other.pbucket;
263 return &(inode->key);
269 return &(inode->key);
297 return rhs.inode == inode;
307 bucket_t*& get_bucket_list_iterator()
313 local_iterator get_local_iterator()
320 local_iterator inode;
348 : pbuckets_end(
other.pbuckets_end)
349 , pbucket(
other.pbucket)
356 : pbuckets_end(
other.pbuckets_end)
357 , pbucket(
other.pbucket)
368 if (inode == pbucket->end())
373 while ((pbucket != pbuckets_end) && (pbucket->empty()))
379 if (pbucket != pbuckets_end)
381 inode = pbucket->begin();
399 pbuckets_end =
other.pbuckets_end;
400 pbucket =
other.pbucket;
414 return &(inode->key);
420 return &(inode->key);
448 return rhs.inode == inode;
458 bucket_t*& get_bucket_list_iterator()
464 local_iterator get_local_iterator()
471 local_iterator inode;
474 typedef typename etl::iterator_traits<iterator>::difference_type difference_type;
482 return iterator((pbuckets + number_of_buckets), first, first->begin());
491 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
500 return const_iterator((pbuckets + number_of_buckets), first, first->begin());
509 return pbuckets[
i].begin();
516 const_local_iterator
begin(
size_t i)
const
518 return pbuckets[
i].cbegin();
527 return pbuckets[
i].cbegin();
536 return iterator((pbuckets + number_of_buckets), last, last->end());
545 return const_iterator((pbuckets + number_of_buckets), last, last->end());
554 return const_iterator((pbuckets + number_of_buckets), last, last->end());
563 return pbuckets[
i].end();
570 const_local_iterator
end(
size_t i)
const
572 return pbuckets[
i].cend();
579 const_local_iterator
cend(
size_t i)
const
581 return pbuckets[
i].cend();
590 return key_hash_function(key) % number_of_buckets;
601 return key_hash_function(key) % number_of_buckets;
611 size_t index =
bucket(key);
613 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
624 size_t index =
bucket(key);
626 return etl::distance(pbuckets[index].
begin(), pbuckets[index].
end());
636 return number_of_buckets;
645 return number_of_buckets;
655 template <
typename TIterator>
658#if ETL_IS_DEBUG_BUILD
680 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
688 bucket_t* pbucket = pbuckets + index;
698 ETL_INCREMENT_DEBUG_COUNT;
702 adjust_first_last_markers_after_insert(&
bucket);
704 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->begin());
705 result.second =
true;
711 local_iterator inode =
bucket.begin();
713 while (inode !=
bucket.end())
716 if (key_equal_function(inode->key, key))
729 ETL_INCREMENT_DEBUG_COUNT;
733 adjust_first_last_markers_after_insert(&
bucket);
737 result.second =
true;
750 ETL_OR_STD::pair<iterator, bool>
insert(
const K& key)
752 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
760 bucket_t* pbucket = pbuckets + index;
761 bucket_t&
bucket = *pbucket;
767 node_t*
node = allocate_data_node();
769 ::new (&
node->key) value_type(key);
770 ETL_INCREMENT_DEBUG_COUNT;
774 adjust_first_last_markers_after_insert(&
bucket);
776 result.first =
iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
777 result.second = true;
783 local_iterator inode =
bucket.begin();
785 while (inode !=
bucket.end())
788 if (key_equal_function(inode->key, key))
798 node_t* node = allocate_data_node();
800 ::new (&node->key) value_type(key);
801 ETL_INCREMENT_DEBUG_COUNT;
804 bucket.insert_after(inode_previous, *node);
805 adjust_first_last_markers_after_insert(&bucket);
808 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
809 result.second = true;
822 ETL_OR_STD::pair<iterator, bool>
insert(rvalue_reference key)
824 ETL_OR_STD::pair<iterator, bool> result(
end(),
false);
832 bucket_t* pbucket = pbuckets + index;
833 bucket_t& bucket = *pbucket;
839 node_t* node = allocate_data_node();
841 ::new (&node->key) value_type(
etl::move(key));
842 ETL_INCREMENT_DEBUG_COUNT;
845 bucket.insert_after(bucket.before_begin(), *node);
846 adjust_first_last_markers_after_insert(&bucket);
848 result.first = iterator((pbuckets + number_of_buckets), pbucket, pbucket->
begin());
849 result.second = true;
854 local_iterator inode_previous = bucket.before_begin();
855 local_iterator inode = bucket.begin();
857 while (inode != bucket.end())
860 if (key_equal_function(inode->key, key))
870 node_t* node = allocate_data_node();
872 ::new (&node->key) value_type(
etl::move(key));
873 ETL_INCREMENT_DEBUG_COUNT;
876 bucket.insert_after(inode_previous, *node);
877 adjust_first_last_markers_after_insert(&bucket);
880 result.first = iterator((pbuckets + number_of_buckets), pbucket, inode_previous);
881 result.second = true;
906 template <
class TIterator>
933 if (key_equal_function(
icurrent->key, key))
957 size_t erase(
const K& key)
969 if (key_equal_function(
icurrent->key, key))
1031 local_iterator
iprevious = pbucket->before_begin();
1033 local_iterator
iend =
last_.get_local_iterator();
1059 }
while (pbucket->empty());
1094 while ((
l !=
end()) && key_equal_function(key, *
l))
1111 size_t count(
const K& key)
const
1114 const_iterator
f =
find(key);
1115 const_iterator
l =
f;
1122 while ((
l !=
end()) && key_equal_function(key, *
l))
1142 bucket_t* pbucket = pbuckets + index;
1149 local_iterator inode =
bucket.begin();
1152 while (inode !=
iend)
1155 if (key_equal_function(key, inode->key))
1157 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1178 bucket_t* pbucket = pbuckets + index;
1179 bucket_t&
bucket = *pbucket;
1185 local_iterator inode =
bucket.begin();
1188 while (inode !=
iend)
1191 if (key_equal_function(key, inode->key))
1193 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1213 bucket_t* pbucket = pbuckets + index;
1220 local_iterator inode =
bucket.begin();
1223 while (inode !=
iend)
1226 if (key_equal_function(key, inode->key))
1228 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1245 const_iterator
find(
const K& key)
const
1249 bucket_t* pbucket = pbuckets + index;
1250 bucket_t&
bucket = *pbucket;
1256 local_iterator inode =
bucket.begin();
1259 while (inode !=
iend)
1262 if (key_equal_function(key, inode->key))
1264 return iterator((pbuckets + number_of_buckets), pbucket, inode);
1292 while ((
l !=
end()) && key_equal_function(key, *
l))
1298 return ETL_OR_STD::pair<iterator, iterator>(
f,
l);
1311 ETL_OR_STD::pair<iterator, iterator>
equal_range(
const K& key)
1320 while ((
l !=
end()) && key_equal_function(key, *
l))
1326 return ETL_OR_STD::pair<iterator, iterator>(f, l);
1347 while ((
l !=
end()) && key_equal_function(key, *
l))
1353 return ETL_OR_STD::pair<const_iterator, const_iterator>(
f,
l);
1366 ETL_OR_STD::pair<const_iterator, const_iterator>
equal_range(
const K& key)
const
1368 const_iterator
f =
find(key);
1369 const_iterator
l =
f;
1375 while ((
l !=
end()) && key_equal_function(key, *
l))
1381 return ETL_OR_STD::pair<const_iterator, const_iterator>(f, l);
1390 return pnodepool->
size();
1414 return pnodepool->
empty();
1422 return pnodepool->
full();
1449 return key_hash_function;
1458 return key_equal_function;
1469 key_hash_function =
rhs.hash_function();
1470 key_equal_function =
rhs.key_eq();
1487 key_hash_function =
rhs.hash_function();
1488 key_equal_function =
rhs.key_eq();
1489 move(
rhs.begin(),
rhs.end());
1539 for (
size_t i = 0
UL;
i < number_of_buckets; ++
i)
1546 local_iterator it =
bucket.begin();
1548 while (it !=
bucket.end())
1551 it->key.~value_type();
1553 ETL_DECREMENT_DEBUG_COUNT;
1590 node_t* allocate_data_node()
1592 node_t* (
etl::ipool::*func)() = &etl::ipool::allocate<node_t>;
1593 return (pnodepool->*func)();
1599 void adjust_first_last_markers_after_insert(bucket_t* pbucket)
1608 if (pbucket < first)
1612 else if (pbucket > last)
1622 void adjust_first_last_markers_after_erase(bucket_t* pbucket)
1631 if (pbucket == first)
1634 while (first->empty())
1639 else if (pbucket == last)
1643 bucket_t* pend = last;
1647 while (pbucket != pend)
1649 if (!pbucket->empty())
1663 local_iterator delete_data_node(local_iterator iprevious, local_iterator icurrent, bucket_t& bucket)
1665 local_iterator inext = bucket.erase_after(iprevious);
1666 icurrent->key.~value_type();
1667 pnodepool->
release(&*icurrent);
1668 adjust_first_last_markers_after_erase(&bucket);
1669 ETL_DECREMENT_DEBUG_COUNT;
1684 const size_t number_of_buckets;
1691 hasher key_hash_function;
1694 key_equal key_equal_function;
1697 ETL_DECLARE_DEBUG_COUNT;
1702#if defined(ETL_POLYMORPHIC_UNORDERED_MULTISET) || defined(ETL_POLYMORPHIC_CONTAINERS)
1722 template <
typename TKey,
typename THash,
typename TKeyEqual>
1776 template <
typename TKey,
typename THash,
typename TKeyEqual>
1786 template <
typename TKey, const
size_t MAX_SIZE_,
size_t MAX_BUCKETS_ = MAX_SIZE_,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey> >
1795 static ETL_CONSTANT
size_t MAX_SIZE =
MAX_SIZE_;
1803 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1811 :
base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1826 : base(node_pool, buckets, MAX_BUCKETS,
other.hash_function(),
other.key_eq())
1842 template <
typename TIterator>
1844 :
base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1849#if ETL_HAS_INITIALIZER_LIST
1854 : base(node_pool, buckets, MAX_BUCKETS, hash, equal)
1856 base::assign(
init.begin(),
init.end());
1873 base::operator =(
rhs);
1884 base::operator =(etl::move(
rhs));
1896 typename base::bucket_t buckets[MAX_BUCKETS_];
1902#if ETL_USING_CPP17 && ETL_HAS_INITIALIZER_LIST
1903 template <
typename... T>
1904 unordered_multiset(T...) -> unordered_multiset<
etl::nth_type_t<0, T...>,
sizeof...(T)>;
1910#if ETL_USING_CPP11 && ETL_HAS_INITIALIZER_LIST
1911 template <
typename TKey,
typename THash = etl::hash<TKey>,
typename TKeyEqual = etl::equal_to<TKey>,
typename... T>
1912 constexpr auto make_unordered_multiset(T&&... keys) ->
etl::unordered_multiset<TKey,
sizeof...(T),
sizeof...(T), THash, TKeyEqual>
Definition unordered_multiset.h:325
Definition unordered_multiset.h:183
A templated unordered_multiset implementation that uses a fixed size buffer.
Definition unordered_multiset.h:1788
unordered_multiset(const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Default constructor.
Definition unordered_multiset.h:1802
~unordered_multiset()
Destructor.
Definition unordered_multiset.h:1863
unordered_multiset(const unordered_multiset &other)
Copy constructor.
Definition unordered_multiset.h:1810
unordered_multiset(TIterator first_, TIterator last_, const THash &hash=THash(), const TKeyEqual &equal=TKeyEqual())
Definition unordered_multiset.h:1843
ETL_CONSTEXPR14 bool operator==(const etl::expected< TValue, TError > &lhs, const etl::expected< TValue2, TError2 > &rhs)
Equivalence operators.
Definition expected.h:968
ETL_NODISCARD ETL_CONSTEXPR14 bool is_permutation(TIterator1 begin1, TIterator1 end1, TIterator2 begin2)
Definition algorithm.h:1739
#define ETL_ASSERT(b, e)
Definition error_handler.h:356
Definition exception.h:47
size_t size() const
Returns the number of allocated items in the pool.
Definition ipool.h:301
bool empty() const
Definition ipool.h:310
void release_all()
Release all objects in the pool.
Definition ipool.h:248
bool full() const
Definition ipool.h:319
size_t max_size() const
Returns the maximum number of items in the pool.
Definition ipool.h:269
void release(const void *const p_object)
Definition ipool.h:239
size_t available() const
Returns the number of free items in the pool.
Definition ipool.h:293
~iunordered_multiset()
Destructor.
Definition unordered_multiset.h:1709
ETL_OR_STD::pair< iterator, bool > insert(const_reference key)
Definition unordered_multiset.h:678
size_t available() const
Definition unordered_multiset.h:1429
const_iterator cend() const
Definition unordered_multiset.h:552
iunordered_multiset & operator=(const iunordered_multiset &rhs)
Assignment operator.
Definition unordered_multiset.h:1464
const_iterator begin() const
Definition unordered_multiset.h:489
size_t erase(key_parameter_t key)
Definition unordered_multiset.h:921
void initialise()
Initialise the unordered_multiset.
Definition unordered_multiset.h:1534
iterator end()
Definition unordered_multiset.h:534
size_type max_size() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1396
iterator insert(const_iterator, const_reference key)
Definition unordered_multiset.h:894
const_local_iterator end(size_t i) const
Definition unordered_multiset.h:570
size_type get_bucket_index(key_parameter_t key) const
Definition unordered_multiset.h:588
ETL_OR_STD::pair< const_iterator, const_iterator > equal_range(key_parameter_t key) const
Definition unordered_multiset.h:1338
const_iterator find(key_parameter_t key) const
Definition unordered_multiset.h:1209
local_iterator begin(size_t i)
Definition unordered_multiset.h:507
void assign(TIterator first_, TIterator last_)
Definition unordered_multiset.h:656
const_iterator cbegin() const
Definition unordered_multiset.h:498
iunordered_multiset(pool_t &node_pool_, bucket_t *pbuckets_, size_t number_of_buckets_, hasher key_hash_function_, key_equal key_equal_function_)
Constructor.
Definition unordered_multiset.h:1520
const_iterator end() const
Definition unordered_multiset.h:543
size_type bucket_size(key_parameter_t key) const
Definition unordered_multiset.h:609
void insert(TIterator first_, TIterator last_)
Definition unordered_multiset.h:907
void clear()
Clears the unordered_multiset.
Definition unordered_multiset.h:1073
const_local_iterator cend(size_t i) const
Definition unordered_multiset.h:579
bool contains(key_parameter_t key) const
Check if the unordered_multiset contains the key.
Definition unordered_multiset.h:1499
iterator erase(const_iterator first_, const_iterator last_)
Definition unordered_multiset.h:1019
const_local_iterator cbegin(size_t i) const
Definition unordered_multiset.h:525
iterator find(key_parameter_t key)
Definition unordered_multiset.h:1138
iterator begin()
Definition unordered_multiset.h:480
iterator erase(const_iterator ielement)
Definition unordered_multiset.h:991
key_equal key_eq() const
Definition unordered_multiset.h:1456
local_iterator end(size_t i)
Definition unordered_multiset.h:561
const_local_iterator begin(size_t i) const
Definition unordered_multiset.h:516
size_type max_bucket_count() const
Definition unordered_multiset.h:634
size_type size() const
Gets the size of the unordered_multiset.
Definition unordered_multiset.h:1388
hasher hash_function() const
Definition unordered_multiset.h:1447
size_type bucket_count() const
Definition unordered_multiset.h:643
size_type capacity() const
Gets the maximum possible size of the unordered_multiset.
Definition unordered_multiset.h:1404
size_t count(key_parameter_t key) const
Definition unordered_multiset.h:1083
bool full() const
Checks to see if the unordered_multiset is full.
Definition unordered_multiset.h:1420
float load_factor() const
Definition unordered_multiset.h:1438
ETL_OR_STD::pair< iterator, iterator > equal_range(key_parameter_t key)
Definition unordered_multiset.h:1283
bool empty() const
Checks to see if the unordered_multiset is empty.
Definition unordered_multiset.h:1412
Definition unordered_multiset.h:128
Definition unordered_multiset.h:71
Definition unordered_multiset.h:85
Definition unordered_multiset.h:112
Definition unordered_multiset.h:99
bitset_ext
Definition absolute.h:38
A forward link.
Definition intrusive_links.h:88
iterator
Definition iterator.h:399
Definition unordered_multiset.h:151
pair holds two objects of arbitrary type
Definition utility.h:164
T1 first
first is a copy of the first object
Definition utility.h:168
T2 second
second is a copy of the second object
Definition utility.h:169