Library of Assembled Shared Sources
 
Loading...
Searching...
No Matches
vector_map.inl
Go to the documentation of this file.
1/** @file
2 * @author Bram de Greve (bram@cocamware.com)
3 * @author Tom De Muer (tom@cocamware.com)
4 *
5 * *** BEGIN LICENSE INFORMATION ***
6 *
7 * The contents of this file are subject to the Common Public Attribution License
8 * Version 1.0 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://lass.sourceforge.net/cpal-license. The License is based on the
11 * Mozilla Public License Version 1.1 but Sections 14 and 15 have been added to cover
12 * use of software over a computer network and provide for limited attribution for
13 * the Original Developer. In addition, Exhibit A has been modified to be consistent
14 * with Exhibit B.
15 *
16 * Software distributed under the License is distributed on an "AS IS" basis, WITHOUT
17 * WARRANTY OF ANY KIND, either express or implied. See the License for the specific
18 * language governing rights and limitations under the License.
19 *
20 * The Original Code is LASS - Library of Assembled Shared Sources.
21 *
22 * The Initial Developer of the Original Code is Bram de Greve and Tom De Muer.
23 * The Original Developer is the Initial Developer.
24 *
25 * All portions of the code written by the Initial Developer are:
26 * Copyright (C) 2004-2026 the Initial Developer.
27 * All Rights Reserved.
28 *
29 * Contributor(s):
30 *
31 * Alternatively, the contents of this file may be used under the terms of the
32 * GNU General Public License Version 2 or later (the GPL), in which case the
33 * provisions of GPL are applicable instead of those above. If you wish to allow use
34 * of your version of this file only under the terms of the GPL and not to allow
35 * others to use your version of this file under the CPAL, indicate your decision by
36 * deleting the provisions above and replace them with the notice and other
37 * provisions required by the GPL License. If you do not delete the provisions above,
38 * a recipient may use your version of this file under either the CPAL or the GPL.
39 *
40 * *** END LICENSE INFORMATION ***
41 */
42
43#include "extended_iterator.h"
44
45namespace lass
46{
47namespace stde
48{
49
50template <typename K, typename T, typename C, typename A>
51vector_map<K, T, C, A>::vector_map(const key_compare& key_comp, const allocator_type& allocator):
52 data_(allocator),
53 key_comp_(key_comp)
54{
55}
56
57
58
59template <typename K, typename T, typename C, typename A>
60template <typename InputIterator>
61vector_map<K, T, C, A>::vector_map(InputIterator first, InputIterator last,
62 const key_compare& key_comp, const allocator_type& allocator):
63 data_(first, last, allocator),
64 key_comp_(key_comp)
65{
66 std::stable_sort(data_.begin(), data_.end(), value_compare(key_comp_));
67 iterator end = std::unique(data_.begin(), data_.end(),
68 [this](const value_type& a, const value_type& b) { return !key_comp_(a.first, b.first) && !key_comp_(b.first, a.first); });
69 data_.erase(end, data_.end());
70}
71
72
73
74template <typename K, typename T, typename C, typename A>
75vector_map<K, T, C, A>::vector_map(const vector_map<K, T, C, A>& other):
76 data_(other.data_),
77 key_comp_(other.key_comp_)
78{
79}
80
81
82
83template <typename K, typename T, typename C, typename A>
84vector_map<K, T, C, A>::vector_map(vector_map<K, T, C, A>&& other) noexcept:
85 data_(std::move(other.data_)),
86 key_comp_(std::move(other.key_comp_))
87{
88}
89
90
91
92template <typename K, typename T, typename C, typename A>
93vector_map<K, T, C, A>::vector_map(std::initializer_list<value_type> init,
94 const key_compare& key_comp, const allocator_type& allocator):
95 vector_map(init.begin(), init.end(), key_comp, allocator)
96{
97}
98
99
100
101template <typename K, typename T, typename C, typename A>
102vector_map<K, T, C, A>::~vector_map()
103{
104}
105
106
107
108template <typename K, typename T, typename C, typename A>
109vector_map<K, T, C, A>& vector_map<K, T, C, A>::operator=(const vector_map<K, T, C, A>& other)
110{
111 vector_map<K, T, C, A> temp(other);
112 swap(temp);
113 return *this;
114}
115
116
117
118template <typename K, typename T, typename C, typename A>
119vector_map<K, T, C, A>& vector_map<K, T, C, A>::operator=(vector_map<K, T, C, A>&& other) noexcept
120{
121 vector_map<K, T, C, A> temp(std::move(other));
122 swap(temp);
123 return *this;
124}
125
126
127
128template <typename K, typename T, typename C, typename A> inline
129typename vector_map<K, T, C, A>::iterator
130vector_map<K, T, C, A>::begin() noexcept
131{
132 return data_.begin();
133}
134
135
136
137template <typename K, typename T, typename C, typename A> inline
138typename vector_map<K, T, C, A>::const_iterator
139vector_map<K, T, C, A>::begin() const noexcept
140{
141 return data_.begin();
142}
143
144
145
146template <typename K, typename T, typename C, typename A> inline
147typename vector_map<K, T, C, A>::const_iterator
148vector_map<K, T, C, A>::cbegin() const noexcept
149{
150 return data_.cbegin();
151}
152
153
154
155template <typename K, typename T, typename C, typename A> inline
156typename vector_map<K, T, C, A>::iterator
157vector_map<K, T, C, A>::end() noexcept
158{
159 return data_.end();
160}
161
162
163
164template <typename K, typename T, typename C, typename A> inline
165typename vector_map<K, T, C, A>::const_iterator
166vector_map<K, T, C, A>::end() const noexcept
167{
168 return data_.end();
169}
170
171
172
173template <typename K, typename T, typename C, typename A> inline
174typename vector_map<K, T, C, A>::const_iterator
175vector_map<K, T, C, A>::cend() const noexcept
176{
177 return data_.cend();
178}
179
180
181
182template <typename K, typename T, typename C, typename A> inline
183typename vector_map<K, T, C, A>::reverse_iterator
184vector_map<K, T, C, A>::rbegin() noexcept
185{
186 return data_.rbegin();
187}
188
189
190
191template <typename K, typename T, typename C, typename A> inline
192typename vector_map<K, T, C, A>::const_reverse_iterator
193vector_map<K, T, C, A>::rbegin() const noexcept
194{
195 return data_.rbegin();
196}
197
198
199
200template <typename K, typename T, typename C, typename A> inline
201typename vector_map<K, T, C, A>::const_reverse_iterator
202vector_map<K, T, C, A>::crbegin() const noexcept
203{
204 return data_.crbegin();
205}
206
207
208
209template <typename K, typename T, typename C, typename A> inline
210typename vector_map<K, T, C, A>::reverse_iterator
211vector_map<K, T, C, A>::rend() noexcept
212{
213 return data_.rend();
214}
215
216
217
218template <typename K, typename T, typename C, typename A> inline
219typename vector_map<K, T, C, A>::const_reverse_iterator
220vector_map<K, T, C, A>::rend() const noexcept
221{
222 return data_.rend();
223}
224
225
226
227template <typename K, typename T, typename C, typename A> inline
228typename vector_map<K, T, C, A>::const_reverse_iterator
229vector_map<K, T, C, A>::crend() const noexcept
230{
231 return data_.crend();
232}
233
234
235
236template <typename K, typename T, typename C, typename A> inline
237bool vector_map<K, T, C, A>::empty() const noexcept
238{
239 return data_.empty();
240}
241
242
243
244template <typename K, typename T, typename C, typename A> inline
245typename vector_map<K, T, C, A>::size_type
246vector_map<K, T, C, A>::size() const noexcept
247{
248 return data_.size();
249}
250
251
252
253template <typename K, typename T, typename C, typename A> inline
254typename vector_map<K, T, C, A>::size_type
255vector_map<K, T, C, A>::max_size() const noexcept
256{
257 return data_.max_size();
258}
259
260
261
262template <typename K, typename T, typename C, typename A> inline
263typename vector_map<K, T, C, A>::mapped_type&
264vector_map<K, T, C, A>::at(const key_type& key)
265{
266 auto it = find(key);
267 if (it == end())
268 {
269 throw std::out_of_range("no such element");
270 }
271 return it->second;
272}
273
274
275
276template <typename K, typename T, typename C, typename A> inline
277const typename vector_map<K, T, C, A>::mapped_type&
278vector_map<K, T, C, A>::at(const key_type& key) const
279{
280 auto it = find(key);
281 if (it == end())
282 {
283 throw std::out_of_range("no such element");
284 }
285 return it->second;
286}
287
288
289
290template <typename K, typename T, typename C, typename A> inline
291typename vector_map<K, T, C, A>::mapped_type&
292vector_map<K, T, C, A>::operator[](const key_type& key)
293{
294 return (try_emplace(key, mapped_type()).first)->second;
295}
296
297
298
299template <typename K, typename T, typename C, typename A> inline
300typename vector_map<K, T, C, A>::mapped_type&
301vector_map<K, T, C, A>::operator[](key_type&& key)
302{
303 return (try_emplace(std::move(key), mapped_type()).first)->second;
304}
305
306
307
308template <typename K, typename T, typename C, typename A>
309std::pair<typename vector_map<K, T, C, A>::iterator, bool>
310vector_map<K, T, C, A>::insert(const value_type& x)
311{
312 iterator i = lower_bound(x.first);
313 if (i == end() || key_comp_(x.first, i->first))
314 {
315 i = data_.insert(i, x);
316 return std::make_pair(i, true);
317 }
318 return std::make_pair(i, false);
319}
320
321
322
323template <typename K, typename T, typename C, typename A>
324std::pair<typename vector_map<K, T, C, A>::iterator, bool>
325vector_map<K, T, C, A>::insert(value_type&& x)
326{
327 iterator i = lower_bound(x.first);
328 if (i == end() || key_comp_(x.first, i->first))
329 {
330 i = data_.insert(i, std::move(x));
331 return std::make_pair(i, true);
332 }
333 return std::make_pair(i, false);
334}
335
336
337
338template <typename K, typename T, typename C, typename A> inline
339typename vector_map<K, T, C, A>::iterator
340vector_map<K, T, C, A>::insert(const_iterator hint, const value_type& x)
341{
342 return is_insert_position(hint, x.first)
343 ? data_.insert(hint, x)
344 : insert(x).first;
345}
346
347
348
349template <typename K, typename T, typename C, typename A>
350template <typename InputIterator>
351void vector_map<K, T, C, A>::insert(InputIterator first, InputIterator last)
352{
353 while (first != last)
354 {
355 insert(*first++);
356 }
357}
358
359
360
361template <typename K, typename T, typename C, typename A>
362template <typename M>
363std::pair<typename vector_map<K, T, C, A>::iterator, bool>
364vector_map<K, T, C, A>::insert_or_assign(const key_type& key, M&& obj)
365{
366 iterator i = lower_bound(key);
367 if (i == end() || key_comp_(key, i->first))
368 {
369 i = data_.emplace(i, key, std::forward<M>(obj));
370 return std::make_pair(i, true);
371 }
372 i->second = std::forward<M>(obj);
373 return std::make_pair(i, false);
374}
375
376
377
378template <typename K, typename T, typename C, typename A>
379template <typename M>
380std::pair<typename vector_map<K, T, C, A>::iterator, bool>
381vector_map<K, T, C, A>::insert_or_assign(key_type&& key, M&& obj)
382{
383 iterator i = lower_bound(key);
384 if (i == end() || key_comp_(key, i->first))
385 {
386 i = data_.emplace(i, std::move(key), std::forward<M>(obj));
387 return std::make_pair(i, true);
388 }
389 i->second = std::forward<M>(obj);
390 return std::make_pair(i, false);
391}
392
393
394
395template <typename K, typename T, typename C, typename A>
396template <typename M>
397typename vector_map<K, T, C, A>::iterator
398vector_map<K, T, C, A>::insert_or_assign(const_iterator hint, const key_type& key, M&& obj)
399{
400 return is_insert_position(hint, key)
401 ? data_.emplace(hint, key, std::forward<M>(obj))
402 : insert_or_assign(key, std::forward<M>(obj)).first;
403}
404
405
406
407template <typename K, typename T, typename C, typename A>
408template <typename M>
409typename vector_map<K, T, C, A>::iterator
410vector_map<K, T, C, A>::insert_or_assign(const_iterator hint, key_type&& key, M&& obj)
411{
412 return is_insert_position(hint, key)
413 ? data_.emplace(hint, std::move(key), std::forward<M>(obj))
414 : insert_or_assign(std::move(key), std::forward<M>(obj)).first;
415}
416
417
418
419template <typename K, typename T, typename C, typename A>
420template <typename... Args>
421std::pair<typename vector_map<K, T, C, A>::iterator, bool>
422vector_map<K, T, C, A>::emplace(Args&&... args)
423{
424 value_type x{ std::forward<Args>(args)... };
425 return insert(std::move(x));
426}
427
428
429
430template <typename K, typename T, typename C, typename A>
431template <typename... Args>
432typename vector_map<K, T, C, A>::iterator
433vector_map<K, T, C, A>::emplace_hint(const_iterator hint, Args&&... args)
434{
435 value_type x{ std::forward<Args>(args)... };
436 return is_insert_position(hint, x.first)
437 ? data_.insert(hint, std::move(x))
438 : insert(std::move(x)).first;
439}
440
441
442template <typename K, typename T, typename C, typename A>
443template<typename... Args>
444std::pair<typename vector_map<K, T, C, A>::iterator, bool>
445vector_map<K, T, C, A>::try_emplace(const key_type& key, Args&&... args)
446{
447 iterator i = lower_bound(key);
448 if (i == end() || key_comp_(key, i->first))
449 {
450 i = data_.emplace(i, key, std::forward<Args>(args)...);
451 return std::make_pair(i, true);
452 }
453 return std::make_pair(i, false);
454}
455
456
457template <typename K, typename T, typename C, typename A>
458template<typename... Args>
459std::pair<typename vector_map<K, T, C, A>::iterator, bool>
460vector_map<K, T, C, A>::try_emplace(key_type&& key, Args&&... args)
461{
462 key_type k{ std::move(key) };
463 iterator i = lower_bound(k);
464 if (i == end() || key_comp_(k, i->first))
465 {
466 i = data_.emplace(i, std::move(k), std::forward<Args>(args)...);
467 return std::make_pair(i, true);
468 }
469 return std::make_pair(i, false);
470}
471
472
473template <typename K, typename T, typename C, typename A>
474template<typename... Args>
475typename vector_map<K, T, C, A>::iterator
476vector_map<K, T, C, A>::try_emplace(const_iterator hint, const key_type& key, Args&&... args)
477{
478 return is_insert_position(hint, key)
479 ? data_.emplace(hint, key, std::forward<Args>(args)...)
480 : try_emplace(key, std::forward<Args>(args)...).first;
481}
482
483
484template <typename K, typename T, typename C, typename A>
485template<typename... Args>
486typename vector_map<K, T, C, A>::iterator
487vector_map<K, T, C, A>::try_emplace(const_iterator hint, key_type&& key, Args&&... args)
488{
489 key_type k{ std::move(key) };
490 return is_insert_position(hint, k)
491 ? data_.emplace(hint, std::move(k), std::forward<Args>(args)...)
492 : try_emplace(std::move(k), std::forward<Args>(args)...).first;
493}
494
495
496template <typename K, typename T, typename C, typename A> inline
497void vector_map<K, T, C, A>::erase(const_iterator i)
498{
499 data_.erase(i);
500}
501
502
503
504template <typename K, typename T, typename C, typename A>
505typename vector_map<K, T, C, A>::size_type
506vector_map<K, T, C, A>::erase(const key_type& x)
507{
508 const const_iterator i = find(x);
509 if (i != cend())
510 {
511 erase(i);
512 return 1;
513 }
514 return 0;
515}
516
517
518
519template <typename K, typename T, typename C, typename A> inline
520void vector_map<K, T, C, A>::erase(const_iterator first, const_iterator last)
521{
522 data_.erase(first, last);
523}
524
525
526
527template <typename K, typename T, typename C, typename A> inline
528void vector_map<K, T, C, A>::swap(vector_map<K, T, C, A>& other) noexcept
529{
530 data_.swap(other.data_);
531 std::swap(key_comp_, other.key_comp_);
532}
533
534
535
536template <typename K, typename T, typename C, typename A> inline
537void vector_map<K, T, C, A>::clear() noexcept
538{
539 data_.clear();
540}
541
542
543
544template <typename K, typename T, typename C, typename A> inline
545typename vector_map<K, T, C, A>::key_compare
546vector_map<K, T, C, A>::key_comp() const
547{
548 return key_comp_;
549}
550
551
552
553template <typename K, typename T, typename C, typename A> inline
554typename vector_map<K, T, C, A>::value_compare
555vector_map<K, T, C, A>::value_comp() const
556{
557 return value_compare(key_comp_);
558}
559
560
561
562template <typename K, typename T, typename C, typename A>
563typename vector_map<K, T, C, A>::iterator
564vector_map<K, T, C, A>::find(const key_type& key)
565{
566 const iterator i = lower_bound(key);
567 if (i == end() || key_comp_(key, i->first))
568 {
569 return end();
570 }
571 return i;
572}
573
574
575
576template <typename K, typename T, typename C, typename A>
577typename vector_map<K, T, C, A>::const_iterator
578vector_map<K, T, C, A>::find(const key_type& key) const
579{
580 const const_iterator i = lower_bound(key);
581 if (i == end() || key_comp_(key, i->first))
582 {
583 return end();
584 }
585 return i;
586}
587
588
589
590template <typename K, typename T, typename C, typename A> inline
591typename vector_map<K, T, C, A>::size_type
592vector_map<K, T, C, A>::count(const key_type& key) const
593{
594 return find(key) != end() ? 1 : 0;
595}
596
597
598
599template <typename K, typename T, typename C, typename A> inline
600bool vector_map<K, T, C, A>::contains(const key_type& key) const
601{
602 return find(key) != end();
603}
604
605
606
607template <typename K, typename T, typename C, typename A> inline
608typename vector_map<K, T, C, A>::iterator
609vector_map<K, T, C, A>::lower_bound(const key_type& key)
610{
611 return std::lower_bound(data_.begin(), data_.end(), key,
612 [this](const value_type& x, const key_type& k) { return key_comp_(x.first, k); });
613}
614
615
616
617template <typename K, typename T, typename C, typename A> inline
618typename vector_map<K, T, C, A>::const_iterator
619vector_map<K, T, C, A>::lower_bound(const key_type& key) const
620{
621 return std::lower_bound(data_.cbegin(), data_.cend(), key,
622 [this](const value_type& x, const key_type& k) { return key_comp_(x.first, k); });
623
624}
625
626
627
628template <typename K, typename T, typename C, typename A> inline
629typename vector_map<K, T, C, A>::iterator
630vector_map<K, T, C, A>::upper_bound(const key_type& key)
631{
632 return std::upper_bound(data_.begin(), data_.end(), key,
633 [this](const key_type& k, const value_type& x) { return key_comp_(k, x.first); });
634
635}
636
637
638
639template <typename K, typename T, typename C, typename A> inline
640typename vector_map<K, T, C, A>::const_iterator
641vector_map<K, T, C, A>::upper_bound(const key_type& key) const
642{
643 return std::upper_bound(data_.cbegin(), data_.cend(), key,
644 [this](const key_type& k, const value_type& x) { return key_comp_(k, x.first); });
645}
646
647
648
649template <typename K, typename T, typename C, typename A> inline
650std::pair<typename vector_map<K, T, C, A>::iterator, typename vector_map<K, T, C, A>::iterator>
651vector_map<K, T, C, A>::equal_range(const key_type& key)
652{
653 const value_type k(key, mapped_type{});
654 return std::equal_range(data_.begin(), data_.end(), k,
655 [this](const value_type& a, const value_type& b) { return key_comp_(a.first, b.first); });
656}
657
658
659
660template <typename K, typename T, typename C, typename A> inline
661std::pair<typename vector_map<K, T, C, A>::const_iterator, typename vector_map<K, T, C, A>::const_iterator>
662vector_map<K, T, C, A>::equal_range(const key_type& key) const
663{
664 const value_type k(key, mapped_type{});
665 return std::equal_range(data_.cbegin(), data_.cend(), k,
666 [this](const value_type& a, const value_type& b) { return key_comp_(a.first, b.first); });
667}
668
669
670
671template <typename K, typename T, typename C, typename A>
672bool vector_map<K, T, C, A>::is_insert_position(const_iterator hint, const key_type& key) const
673{
674 // return true if prev(hint)->key < key < hint->key
675 return (hint == cend() || key_comp_(key, hint->first)) &&
676 (hint == cbegin() || key_comp_(stde::prev(hint)->first, key));
677}
678
679
680// --- free functions ------------------------------------------------------------------------------
681
682/** @relates vector_map
683 */
684template <typename K, typename T, typename C, typename A>
685bool operator==(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
686{
687 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin(), a.value_comp());
688}
689
690
691
692/** @relates vector_map
693 */
694template <typename K, typename T, typename C, typename A> inline
695bool operator!=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
696{
697 return !(a == b);
698}
699
700
701
702/** @relates vector_map
703 */
704template <typename K, typename T, typename C, typename A> inline
705bool operator<(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
706{
707 return std::lexicographical_compare(a.begin(), a.end(), b.begin, b.end(), a.value_comp());
708}
709
710
711
712/** @relates vector_map
713 */
714template <typename K, typename T, typename C, typename A> inline
715bool operator>(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
716{
717 return b < a;
718}
719
720
721
722/** @relates vector_map
723 */
724template <typename K, typename T, typename C, typename A> inline
725bool operator<=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
726{
727 return !(b < a);
728}
729
730
731
732/** @relates vector_map
733 */
734template <typename K, typename T, typename C, typename A> inline
735bool operator>=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
736{
737 return !(a < b);
738}
739
740
741
742/** @relates vector_map
743 */
744template <typename K, typename T, typename C, typename A, typename Char, typename Traits>
745std::basic_ostream<Char, Traits>&
746operator<<(std::basic_ostream<Char, Traits>& ostream, vector_map<K, T, C, A>& container)
747{
748 return impl::print_map<Char>(ostream, container.begin(), container.end(), "{", ", ", ": ", "}");
749}
750
751
752
753/** @relates vector_map
754 */
755template <typename Char, typename Traits, typename K, typename T, typename C, typename A>
756std::basic_istream<Char, Traits>&
757operator>>(std::basic_istream<Char, Traits>& istream, vector_map<K, T, C, A>& container)
758{
759 return impl::read_container<impl::set_traits, impl::pair_traits, std::pair<K, T>, Char>(
760 istream, container, '{', ',', ':', '}');
761}
762
763
764}
765}
766
767namespace std
768{
769
770/** @relates vector_map
771 */
772template <typename K, typename T, typename C, typename A>
773void swap(lass::stde::vector_map<K, T, C, A>& a, lass::stde::vector_map<K, T, C, A>& b) noexcept
774{
775 a.swap(b);
776}
777
778}
779
780// EOF
extended_iterator.h
lass::stde
lass extensions to the standard library
lass
Library for Assembled Shared Sources.
Definition config.h:53