Library of Assembled Shared Sources
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-2011 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... Args>
363std::pair<typename vector_map<K, T, C, A>::iterator, bool>
364vector_map<K, T, C, A>::emplace(Args&&... args)
365{
366 value_type x{ std::forward<Args>(args)... };
367 return insert(std::move(x));
368}
369
370
371
372template <typename K, typename T, typename C, typename A>
373template <typename... Args>
374typename vector_map<K, T, C, A>::iterator
375vector_map<K, T, C, A>::emplace_hint(const_iterator hint, Args&&... args)
376{
377 value_type x{ std::forward<Args>(args)... };
378 return is_insert_position(hint, x.first)
379 ? data_.insert(hint, std::move(x))
380 : insert(std::move(x)).first;
381}
382
383
384template <typename K, typename T, typename C, typename A>
385template<typename... Args>
386std::pair<typename vector_map<K, T, C, A>::iterator, bool>
387vector_map<K, T, C, A>::try_emplace(const key_type& key, Args&&... args)
388{
389 iterator i = lower_bound(key);
390 if (i == end() || key_comp_(key, i->first))
391 {
392 i = data_.emplace(i, key, std::forward<Args>(args)...);
393 return std::make_pair(i, true);
394 }
395 return std::make_pair(i, false);
396}
397
398
399template <typename K, typename T, typename C, typename A>
400template<typename... Args>
401std::pair<typename vector_map<K, T, C, A>::iterator, bool>
402vector_map<K, T, C, A>::try_emplace(key_type&& key, Args&&... args)
403{
404 key_type k{ std::move(key) };
405 iterator i = lower_bound(k);
406 if (i == end() || key_comp_(k, i->first))
407 {
408 i = data_.emplace(i, std::move(k), std::forward<Args>(args)...);
409 return std::make_pair(i, true);
410 }
411 return std::make_pair(i, false);
412}
413
414
415template <typename K, typename T, typename C, typename A>
416template<typename... Args>
417typename vector_map<K, T, C, A>::iterator
418vector_map<K, T, C, A>::try_emplace(const_iterator hint, const key_type& key, Args&&... args)
419{
420 return is_insert_position(hint, key)
421 ? data_.emplace(hint, key, std::forward<Args>(args)...)
422 : try_emplace(key, std::forward<Args>(args)...).first;
423}
424
425
426template <typename K, typename T, typename C, typename A>
427template<typename... Args>
428typename vector_map<K, T, C, A>::iterator
429vector_map<K, T, C, A>::try_emplace(const_iterator hint, key_type&& key, Args&&... args)
430{
431 key_type k{ std::move(key) };
432 return is_insert_position(hint, k)
433 ? data_.emplace(hint, std::move(k), std::forward<Args>(args)...)
434 : try_emplace(std::move(k), std::forward<Args>(args)...).first;
435}
436
437
438template <typename K, typename T, typename C, typename A> inline
439void vector_map<K, T, C, A>::erase(const_iterator i)
440{
441 data_.erase(i);
442}
443
444
445
446template <typename K, typename T, typename C, typename A>
447typename vector_map<K, T, C, A>::size_type
448vector_map<K, T, C, A>::erase(const key_type& x)
449{
450 const const_iterator i = find(x);
451 if (i != cend())
452 {
453 erase(i);
454 return 1;
455 }
456 return 0;
457}
458
459
460
461template <typename K, typename T, typename C, typename A> inline
462void vector_map<K, T, C, A>::erase(const_iterator first, const_iterator last)
463{
464 data_.erase(first, last);
465}
466
467
468
469template <typename K, typename T, typename C, typename A> inline
470void vector_map<K, T, C, A>::swap(vector_map<K, T, C, A>& other) noexcept
471{
472 data_.swap(other.data_);
473 std::swap(key_comp_, other.key_comp_);
474}
475
476
477
478template <typename K, typename T, typename C, typename A> inline
479void vector_map<K, T, C, A>::clear() noexcept
480{
481 data_.clear();
482}
483
484
485
486template <typename K, typename T, typename C, typename A> inline
487typename vector_map<K, T, C, A>::key_compare
488vector_map<K, T, C, A>::key_comp() const
489{
490 return key_comp_;
491}
492
493
494
495template <typename K, typename T, typename C, typename A> inline
496typename vector_map<K, T, C, A>::value_compare
497vector_map<K, T, C, A>::value_comp() const
498{
499 return value_compare(key_comp_);
500}
501
502
503
504template <typename K, typename T, typename C, typename A>
505typename vector_map<K, T, C, A>::iterator
506vector_map<K, T, C, A>::find(const key_type& key)
507{
508 const iterator i = lower_bound(key);
509 if (i == end() || key_comp_(key, i->first))
510 {
511 return end();
512 }
513 return i;
514}
515
516
517
518template <typename K, typename T, typename C, typename A>
519typename vector_map<K, T, C, A>::const_iterator
520vector_map<K, T, C, A>::find(const key_type& key) const
521{
522 const const_iterator i = lower_bound(key);
523 if (i == end() || key_comp_(key, i->first))
524 {
525 return end();
526 }
527 return i;
528}
529
530
531
532template <typename K, typename T, typename C, typename A> inline
533typename vector_map<K, T, C, A>::size_type
534vector_map<K, T, C, A>::count(const key_type& key) const
535{
536 return find(key) != end() ? 1 : 0;
537}
538
539
540
541template <typename K, typename T, typename C, typename A> inline
542bool vector_map<K, T, C, A>::contains(const key_type& key) const
543{
544 return find(key) != end();
545}
546
547
548
549template <typename K, typename T, typename C, typename A> inline
550typename vector_map<K, T, C, A>::iterator
551vector_map<K, T, C, A>::lower_bound(const key_type& key)
552{
553 return std::lower_bound(data_.begin(), data_.end(), key,
554 [this](const value_type& x, const key_type& k) { return key_comp_(x.first, k); });
555}
556
557
558
559template <typename K, typename T, typename C, typename A> inline
560typename vector_map<K, T, C, A>::const_iterator
561vector_map<K, T, C, A>::lower_bound(const key_type& key) const
562{
563 return std::lower_bound(data_.cbegin(), data_.cend(), key,
564 [this](const value_type& x, const key_type& k) { return key_comp_(x.first, k); });
565
566}
567
568
569
570template <typename K, typename T, typename C, typename A> inline
571typename vector_map<K, T, C, A>::iterator
572vector_map<K, T, C, A>::upper_bound(const key_type& key)
573{
574 return std::upper_bound(data_.begin(), data_.end(), key,
575 [this](const key_type& k, const value_type& x) { return key_comp_(k, x.first); });
576
577}
578
579
580
581template <typename K, typename T, typename C, typename A> inline
582typename vector_map<K, T, C, A>::const_iterator
583vector_map<K, T, C, A>::upper_bound(const key_type& key) const
584{
585 return std::upper_bound(data_.cbegin(), data_.cend(), key,
586 [this](const key_type& k, const value_type& x) { return key_comp_(k, x.first); });
587}
588
589
590
591template <typename K, typename T, typename C, typename A> inline
592std::pair<typename vector_map<K, T, C, A>::iterator, typename vector_map<K, T, C, A>::iterator>
593vector_map<K, T, C, A>::equal_range(const key_type& key)
594{
595 const value_type k(key, mapped_type{});
596 return std::equal_range(data_.begin(), data_.end(), k,
597 [this](const value_type& a, const value_type& b) { return key_comp_(a.first, b.first); });
598}
599
600
601
602template <typename K, typename T, typename C, typename A> inline
603std::pair<typename vector_map<K, T, C, A>::const_iterator, typename vector_map<K, T, C, A>::const_iterator>
604vector_map<K, T, C, A>::equal_range(const key_type& key) const
605{
606 const value_type k(key, mapped_type{});
607 return std::equal_range(data_.cbegin(), data_.cend(), k,
608 [this](const value_type& a, const value_type& b) { return key_comp_(a.first, b.first); });
609}
610
611
612
613template <typename K, typename T, typename C, typename A>
614bool vector_map<K, T, C, A>::is_insert_position(const_iterator hint, const key_type& key) const
615{
616 // return true if prev(hint)->key < key < hint->key
617 return (hint == cend() || key_comp_(key, hint->first)) &&
618 (hint == cbegin() || key_comp_(stde::prev(hint)->first, key));
619}
620
621
622// --- free functions ------------------------------------------------------------------------------
623
624/** @relates vector_map
625 */
626template <typename K, typename T, typename C, typename A>
627bool operator==(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
628{
629 return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin(), a.value_comp());
630}
631
632
633
634/** @relates vector_map
635 */
636template <typename K, typename T, typename C, typename A> inline
637bool operator!=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
638{
639 return !(a == b);
640}
641
642
643
644/** @relates vector_map
645 */
646template <typename K, typename T, typename C, typename A> inline
647bool operator<(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
648{
649 return std::lexicographical_compare(a.begin(), a.end(), b.begin, b.end(), a.value_comp());
650}
651
652
653
654/** @relates vector_map
655 */
656template <typename K, typename T, typename C, typename A> inline
657bool operator>(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
658{
659 return b < a;
660}
661
662
663
664/** @relates vector_map
665 */
666template <typename K, typename T, typename C, typename A> inline
667bool operator<=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
668{
669 return !(b < a);
670}
671
672
673
674/** @relates vector_map
675 */
676template <typename K, typename T, typename C, typename A> inline
677bool operator>=(const vector_map<K, T, C, A>& a, const vector_map<K, T, C, A>& b)
678{
679 return !(a < b);
680}
681
682
683
684/** @relates vector_map
685 */
686template <typename K, typename T, typename C, typename A, typename Char, typename Traits>
687std::basic_ostream<Char, Traits>&
688operator<<(std::basic_ostream<Char, Traits>& ostream, vector_map<K, T, C, A>& container)
689{
690 return impl::print_map<Char>(ostream, container.begin(), container.end(), "{", ", ", ": ", "}");
691}
692
693
694
695/** @relates vector_map
696 */
697template <typename Char, typename Traits, typename K, typename T, typename C, typename A>
698std::basic_istream<Char, Traits>&
699operator>>(std::basic_istream<Char, Traits>& istream, vector_map<K, T, C, A>& container)
700{
701 return impl::read_container<impl::set_traits, impl::pair_traits, std::pair<K, T>, Char>(
702 istream, container, '{', ',', ':', '}');
703}
704
705
706}
707}
708
709namespace std
710{
711
712/** @relates vector_map
713 */
714template <typename K, typename T, typename C, typename A>
715void swap(lass::stde::vector_map<K, T, C, A>& a, lass::stde::vector_map<K, T, C, A>& b) noexcept
716{
717 a.swap(b);
718}
719
720}
721
722// EOF
extended_iterator.h
lass::stde
lass extensions to the standard library
lass
Library for Assembled Shared Sources.
Definition config.h:53