1 /*
2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * All rights reserved. Distributed under the terms of the MIT license.
4 */
5 #ifndef _VECTOR_MAP_H
6 #define _VECTOR_MAP_H
7
8 #include <stdlib.h>
9 #include <string.h>
10
11 #include <SupportDefs.h>
12
13 #include <util/kernel_cpp.h>
14 #include <util/KernelUtilsOrder.h>
15 #include <util/Vector.h>
16
17 namespace VectorMapEntryStrategy {
18 // Pair
19 template<typename Key, typename Value,
20 typename KeyOrder = KernelUtilsOrder::Ascending<Key> > class Pair;
21 // ImplicitKey
22 template<typename Key, typename Value, typename GetKey,
23 typename KeyOrder = KernelUtilsOrder::Ascending<Key> >
24 class ImplicitKey;
25 }
26
27 template<typename Entry, typename Parent, typename EntryIterator>
28 class VectorMapIterator;
29 template<typename _Key, typename _Value, typename Entry, typename Parent>
30 class VectorMapEntry;
31
32 // for convenience
33 #define _VECTOR_MAP_TEMPLATE_LIST template<typename Key, typename Value, \
34 typename EntryStrategy>
35 #define _VECTOR_MAP_CLASS_NAME VectorMap<Key, Value, EntryStrategy>
36 #define _VECTOR_MAP_CLASS_TYPE typename VectorMap<Key, Value, EntryStrategy>
37
38 /*!
39 \class VectorMap
40 \brief A generic vector-based map implementation.
41
42 The map entries are ordered according to the supplied
43 compare function object. Default is ascending order.
44
45 Note that VectorMap::Entry is not the same class as EntryStrategy::Entry.
46 It is light-weight class, an object of which is returned when a iterator
47 is dereferenced. It features a Key() and a Value() method returning
48 references to the entry's key/value. This allows EntryStrategy::Entry
49 to be an arbitrary class, not needing to implement a certain interface.
50 */
51 template<typename Key, typename Value,
52 typename EntryStrategy = VectorMapEntryStrategy::Pair<Key, Value> >
53 class VectorMap {
54 private:
55 typedef _VECTOR_MAP_CLASS_NAME Class;
56 typedef typename EntryStrategy::Entry _Entry;
57 typedef typename EntryStrategy::KeyReference KeyReference;
58 typedef Vector<_Entry> ElementVector;
59
60 public:
61 typedef VectorMapEntry<KeyReference, Value, _Entry, Class>
62 Entry;
63 typedef VectorMapEntry<KeyReference, const Value, const _Entry,
64 const Class> ConstEntry;
65 typedef VectorMapIterator<Entry, Class, typename ElementVector::Iterator>
66 Iterator;
67 typedef VectorMapIterator<ConstEntry, const Class, typename ElementVector::ConstIterator>
68 ConstIterator;
69
70 private:
71 static const size_t kDefaultChunkSize = 10;
72 static const size_t kMaximalChunkSize = 1024 * 1024;
73
74 public:
75 VectorMap(size_t chunkSize = kDefaultChunkSize);
76 // TODO: Copy constructor, assignment operator.
77 ~VectorMap();
78
79 status_t Insert(const Key &key, const Value &value);
80 status_t Put(const Key &key, const Value &value);
81 Value &Get(const Key &key);
82 const Value &Get(const Key &key) const;
83
84 int32 Remove(const Key &key);
85 Iterator Erase(const Iterator &iterator);
86
87 inline int32 Count() const;
88 inline bool IsEmpty() const;
89 void MakeEmpty();
90
91 inline Iterator Begin();
92 inline ConstIterator Begin() const;
93 inline Iterator End();
94 inline ConstIterator End() const;
95 inline Iterator Null();
96 inline ConstIterator Null() const;
97
98 Iterator Find(const Key &key);
99 ConstIterator Find(const Key &key) const;
100 Iterator FindClose(const Key &key, bool less);
101 ConstIterator FindClose(const Key &key, bool less) const;
102
103 private:
104 int32 _FindInsertionIndex(const Key &key, bool &exists) const;
105
106 private:
107 // friend class Entry;
108 // friend class ConstEntry;
109 friend class VectorMapEntry<KeyReference, Value, _Entry, Class>;
110 friend class VectorMapEntry<KeyReference, const Value, const _Entry,
111 const Class>;
112
113 ElementVector fElements;
114 EntryStrategy fEntryStrategy;
115 };
116
117
118 // VectorMapEntry
119 template<typename KeyReference, typename _Value, typename Entry,
120 typename Parent>
121 class VectorMapEntry {
122 private:
123 typedef VectorMapEntry<KeyReference, _Value, Entry, Parent> Class;
124
125 public:
VectorMapEntry()126 VectorMapEntry()
127 : fParent(NULL), fEntry(NULL) {}
128
Key()129 inline KeyReference Key() const
130 {
131 return fParent->fEntryStrategy.GetKey(*fEntry);
132 }
133
Value()134 inline _Value &Value() const
135 {
136 return fParent->fEntryStrategy.GetValue(*fEntry);
137 }
138
139 inline const Class *operator->() const
140 {
141 return this;
142 }
143
144 // private
145 public:
VectorMapEntry(Parent * parent,Entry * entry)146 VectorMapEntry(Parent *parent, Entry *entry)
147 : fParent(parent), fEntry(entry) {}
148
149 private:
150 const Parent *fParent;
151 Entry *fEntry;
152 };
153
154
155 // VectorMapIterator
156 template<typename Entry, typename Parent, typename EntryIterator>
157 class VectorMapIterator {
158 private:
159 typedef VectorMapIterator<Entry, Parent, EntryIterator> Iterator;
160
161 public:
VectorMapIterator()162 inline VectorMapIterator()
163 : fParent(NULL),
164 fIterator()
165 {
166 }
167
VectorMapIterator(const Iterator & other)168 inline VectorMapIterator(
169 const Iterator &other)
170 : fParent(other.fParent),
171 fIterator(other.fIterator)
172 {
173 }
174
175 inline Iterator &operator++()
176 {
177 ++fIterator;
178 return *this;
179 }
180
181 inline Iterator operator++(int)
182 {
183 Iterator it(*this);
184 ++*this;
185 return it;
186 }
187
188 inline Iterator &operator--()
189 {
190 --fIterator;
191 return *this;
192 }
193
194 inline Iterator operator--(int)
195 {
196 Iterator it(*this);
197 --*this;
198 return it;
199 }
200
201 inline Iterator &operator=(const Iterator &other)
202 {
203 fParent = other.fParent;
204 fIterator = other.fIterator;
205 return *this;
206 }
207
208 inline bool operator==(const Iterator &other) const
209 {
210 return (fParent == other.fParent && fIterator == other.fIterator);
211 }
212
213 inline bool operator!=(const Iterator &other) const
214 {
215 return !(*this == other);
216 }
217
218 inline Entry operator*() const
219 {
220 return Entry(fParent, &*fIterator);
221 }
222
223 inline Entry operator->() const
224 {
225 return Entry(fParent, &*fIterator);
226 }
227
228 inline operator bool() const
229 {
230 return fIterator;
231 }
232
233 // private
234 public:
VectorMapIterator(Parent * parent,const EntryIterator & iterator)235 inline VectorMapIterator(Parent *parent, const EntryIterator &iterator)
236 : fParent(parent),
237 fIterator(iterator)
238 {
239 }
240
GetIterator()241 inline EntryIterator &GetIterator()
242 {
243 return fIterator;
244 }
245
GetIterator()246 inline const EntryIterator &GetIterator() const
247 {
248 return fIterator;
249 }
250
251 protected:
252 Parent *fParent;
253 EntryIterator fIterator;
254 };
255
256
257 // VectorMap
258
259 // constructor
260 /*! \brief Creates an empty map.
261 \param chunkSize The granularity for the underlying vector's capacity,
262 i.e. the minimal number of elements the capacity grows or shrinks
263 when necessary.
264 */
265 _VECTOR_MAP_TEMPLATE_LIST
VectorMap(size_t chunkSize)266 _VECTOR_MAP_CLASS_NAME::VectorMap(size_t chunkSize)
267 : fElements(chunkSize)
268 {
269 }
270
271 // destructor
272 /*! \brief Frees all resources associated with the object.
273
274 The contained keys and values are destroyed. Note, that for pointer
275 types only the pointer is destroyed, not the object it points to.
276 */
277 _VECTOR_MAP_TEMPLATE_LIST
~VectorMap()278 _VECTOR_MAP_CLASS_NAME::~VectorMap()
279 {
280 }
281
282 // Insert
283 /*! \brief Associates a key with a value.
284
285 If there is already a value associated with the key, the old entry
286 is replaced.
287
288 \param key The key to which a value shall be associated.
289 \param value The value to be associated with the key.
290 \return
291 - \c B_OK: Everything went fine.
292 - \c B_NO_MEMORY: Insufficient memory for this operation.
293 - \c B_BAD_VALUE: The map's EntryStrategy requires some special
294 relationship between key and value, that \a key and \a value haven't
295 (doesn't apply to the default strategy).
296 */
297 _VECTOR_MAP_TEMPLATE_LIST
298 status_t
Insert(const Key & key,const Value & value)299 _VECTOR_MAP_CLASS_NAME::Insert(const Key &key, const Value &value)
300 {
301 if (!fEntryStrategy.AreCompatible(key, value))
302 return B_BAD_VALUE;
303 bool exists = false;
304 int32 index = _FindInsertionIndex(key, exists);
305 if (exists) {
306 fElements[index] = fEntryStrategy.MakeEntry(key, value);
307 return B_OK;
308 }
309 return fElements.Insert(fEntryStrategy.MakeEntry(key, value), index);
310 }
311
312 // Put
313 /*! \brief Equivalent to Insert().
314 */
315 _VECTOR_MAP_TEMPLATE_LIST
316 inline
317 status_t
Put(const Key & key,const Value & value)318 _VECTOR_MAP_CLASS_NAME::Put(const Key &key, const Value &value)
319 {
320 return Insert(key, value);
321 }
322
323 // Get
324 /*! \brief Returns the value associated with a given key.
325
326 \note Invoking this method for a key not know to the map is dangerous!
327 The behavior is unspecified. It may even crash.
328
329 \param key The key to be looked up.
330 \return The value associated with \a key.
331 */
332 _VECTOR_MAP_TEMPLATE_LIST
333 Value &
Get(const Key & key)334 _VECTOR_MAP_CLASS_NAME::Get(const Key &key)
335 {
336 bool exists = false;
337 int32 index = _FindInsertionIndex(key, exists);
338 if (!exists)
339 return fEntryStrategy.GetValue(fElements[0]);
340 return fEntryStrategy.GetValue(fElements[index]);
341 }
342
343 // Get
344 /*! \brief Returns the value associated with a given key.
345
346 \note Invoking this method for a key not know to the map is dangerous!
347 The behavior is unspecified. It may even crash.
348
349 \param key The key to be looked up.
350 \return The value associated with \a key.
351 */
352 _VECTOR_MAP_TEMPLATE_LIST
353 const Value &
Get(const Key & key)354 _VECTOR_MAP_CLASS_NAME::Get(const Key &key) const
355 {
356 bool exists = false;
357 int32 index = _FindInsertionIndex(key, exists);
358 if (!exists)
359 return fEntryStrategy.GetValue(fElements[0]);
360 return fEntryStrategy.GetValue(fElements[index]);
361 }
362
363 // Remove
364 /*! \brief Removes the entry with the supplied key.
365 \param key The key to be removed.
366 \return The number of removed occurrences, i.e. \c 1, if the map
367 contained an entry with that key, \c 0 otherwise.
368 */
369 _VECTOR_MAP_TEMPLATE_LIST
370 int32
Remove(const Key & key)371 _VECTOR_MAP_CLASS_NAME::Remove(const Key &key)
372 {
373 bool exists = false;
374 int32 index = _FindInsertionIndex(key, exists);
375 if (!exists)
376 return 0;
377 fElements.Erase(index);
378 return 1;
379 }
380
381 // Erase
382 /*! \brief Removes the entry at the given position.
383 \param iterator An iterator referring to the entry to be removed.
384 \return An iterator referring to the entry succeeding the removed
385 one (End(), if it was the last element that has been
386 removed), or Null(), if \a iterator was an invalid iterator
387 (in this case including End()).
388 */
389 _VECTOR_MAP_TEMPLATE_LIST
390 _VECTOR_MAP_CLASS_TYPE::Iterator
Erase(const Iterator & iterator)391 _VECTOR_MAP_CLASS_NAME::Erase(const Iterator &iterator)
392 {
393 return Iterator(this, fElements.Erase(iterator.GetIterator()));
394 }
395
396 // Count
397 /*! \brief Returns the number of entry the map contains.
398 \return The number of entries the map contains.
399 */
400 _VECTOR_MAP_TEMPLATE_LIST
401 inline
402 int32
Count()403 _VECTOR_MAP_CLASS_NAME::Count() const
404 {
405 return fElements.Count();
406 }
407
408 // IsEmpty
409 /*! \brief Returns whether the map is empty.
410 \return \c true, if the map is empty, \c false otherwise.
411 */
412 _VECTOR_MAP_TEMPLATE_LIST
413 inline
414 bool
IsEmpty()415 _VECTOR_MAP_CLASS_NAME::IsEmpty() const
416 {
417 return fElements.IsEmpty();
418 }
419
420 // MakeEmpty
421 /*! \brief Removes all entries from the map.
422 */
423 _VECTOR_MAP_TEMPLATE_LIST
424 void
MakeEmpty()425 _VECTOR_MAP_CLASS_NAME::MakeEmpty()
426 {
427 fElements.MakeEmpty();
428 }
429
430 // Begin
431 /*! \brief Returns an iterator referring to the beginning of the map.
432
433 If the map is not empty, Begin() refers to its first entry,
434 otherwise it is equal to End() and must not be dereferenced!
435
436 \return An iterator referring to the beginning of the map.
437 */
438 _VECTOR_MAP_TEMPLATE_LIST
439 inline
440 _VECTOR_MAP_CLASS_TYPE::Iterator
Begin()441 _VECTOR_MAP_CLASS_NAME::Begin()
442 {
443 return Iterator(this, fElements.Begin());
444 }
445
446 // Begin
447 /*! \brief Returns an iterator referring to the beginning of the map.
448
449 If the map is not empty, Begin() refers to its first entry,
450 otherwise it is equal to End() and must not be dereferenced!
451
452 \return An iterator referring to the beginning of the map.
453 */
454 _VECTOR_MAP_TEMPLATE_LIST
455 inline
456 _VECTOR_MAP_CLASS_TYPE::ConstIterator
Begin()457 _VECTOR_MAP_CLASS_NAME::Begin() const
458 {
459 return ConstIterator(this, fElements.Begin());
460 }
461
462 // End
463 /*! \brief Returns an iterator referring to the end of the map.
464
465 The position identified by End() is the one succeeding the last
466 entry, i.e. it must not be dereferenced!
467
468 \return An iterator referring to the end of the map.
469 */
470 _VECTOR_MAP_TEMPLATE_LIST
471 inline
472 _VECTOR_MAP_CLASS_TYPE::Iterator
End()473 _VECTOR_MAP_CLASS_NAME::End()
474 {
475 return Iterator(this, fElements.End());
476 }
477
478 // End
479 /*! \brief Returns an iterator referring to the end of the map.
480
481 The position identified by End() is the one succeeding the last
482 entry, i.e. it must not be dereferenced!
483
484 \return An iterator referring to the end of the map.
485 */
486 _VECTOR_MAP_TEMPLATE_LIST
487 inline
488 _VECTOR_MAP_CLASS_TYPE::ConstIterator
End()489 _VECTOR_MAP_CLASS_NAME::End() const
490 {
491 return ConstIterator(this, fElements.End());
492 }
493
494 // Null
495 /*! \brief Returns an invalid iterator.
496
497 Null() is used as a return value, if something went wrong. It must
498 neither be incremented or decremented nor dereferenced!
499
500 \return An invalid iterator.
501 */
502 _VECTOR_MAP_TEMPLATE_LIST
503 inline
504 _VECTOR_MAP_CLASS_TYPE::Iterator
Null()505 _VECTOR_MAP_CLASS_NAME::Null()
506 {
507 return Iterator(this, fElements.Null());
508 }
509
510 // Null
511 /*! \brief Returns an invalid iterator.
512
513 Null() is used as a return value, if something went wrong. It must
514 neither be incremented or decremented nor dereferenced!
515
516 \return An invalid iterator.
517 */
518 _VECTOR_MAP_TEMPLATE_LIST
519 inline
520 _VECTOR_MAP_CLASS_TYPE::ConstIterator
Null()521 _VECTOR_MAP_CLASS_NAME::Null() const
522 {
523 return ConstIterator(this, fElements.Null());
524 }
525
526 // Find
527 /*! \brief Returns an iterator referring to the entry with the
528 specified key.
529 \param key The key of the entry to be found.
530 \return An iterator referring to the found entry, or End(), if the
531 map doesn't contain any entry with the given value.
532 */
533 _VECTOR_MAP_TEMPLATE_LIST
534 _VECTOR_MAP_CLASS_TYPE::Iterator
Find(const Key & key)535 _VECTOR_MAP_CLASS_NAME::Find(const Key &key)
536 {
537 bool exists = false;
538 int32 index = _FindInsertionIndex(key, exists);
539 if (!exists)
540 return End();
541 return Iterator(this, fElements.IteratorForIndex(index));
542 }
543
544 // Find
545 /*! \brief Returns an iterator referring to the entry with the
546 specified key.
547 \param key The key of the entry to be found.
548 \return An iterator referring to the found entry, or End(), if the
549 map doesn't contain any entry with the given value.
550 */
551 _VECTOR_MAP_TEMPLATE_LIST
552 _VECTOR_MAP_CLASS_TYPE::ConstIterator
Find(const Key & key)553 _VECTOR_MAP_CLASS_NAME::Find(const Key &key) const
554 {
555 bool exists = false;
556 int32 index = _FindInsertionIndex(key, exists);
557 if (!exists)
558 return End();
559 return ConstIterator(this, fElements.IteratorForIndex(index));
560 }
561
562 // FindClose
563 /*! \brief Returns an iterator referring to the entry with a key closest
564 to the specified one.
565
566 If the map contains an entry with the specified key, an iterator
567 to it is returned. Otherwise \a less indicates whether an iterator to
568 the entry with an directly smaller or greater key shall be returned.
569
570 If \a less is \c true and the first entry in the map has a greater
571 key than the specified one, End() is returned. Similarly, when \a less
572 is \c false and the last entry's key is smaller. Find() invoked on an
573 empty map always returns End().
574
575 Note, that the key order used for the set is specified as template
576 argument to the class. Default is ascending order. Descending order
577 inverts the meaning of \a less, i.e. if \c true, greater values will
578 be returned, since they are smaller ones according to the order.
579
580 \param value The key of the entry to be found.
581 \return An iterator referring to the found entry, or End(), if the
582 map doesn't contain any entry with the given key or a close
583 one according to \a less.
584 */
585 _VECTOR_MAP_TEMPLATE_LIST
586 _VECTOR_MAP_CLASS_TYPE::Iterator
FindClose(const Key & key,bool less)587 _VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less)
588 {
589 bool exists = false;
590 int32 index = _FindInsertionIndex(key, exists);
591 // If not found, the index _FindInsertionIndex() returns will point to
592 // an element with a greater value or to End(). So, no special handling
593 // is needed for !less.
594 if (exists || !less)
595 return Iterator(this, fElements.IteratorForIndex(index));
596 // An element with a smaller value is desired. The previous one (if any)
597 // will do.
598 if (index > 0)
599 return Iterator(this, fElements.IteratorForIndex(index - 1));
600 return End();
601 }
602
603 // FindClose
604 /*! \brief Returns an iterator referring to the entry with a key closest
605 to the specified one.
606
607 If the map contains an entry with the specified key, an iterator
608 to it is returned. Otherwise \a less indicates whether an iterator to
609 the entry with an directly smaller or greater key shall be returned.
610
611 If \a less is \c true and the first entry in the map has a greater
612 key than the specified one, End() is returned. Similarly, when \a less
613 is \c false and the last entry's key is smaller. Find() invoked on an
614 empty map always returns End().
615
616 Note, that the key order used for the set is specified as template
617 argument to the class. Default is ascending order. Descending order
618 inverts the meaning of \a less, i.e. if \c true, greater values will
619 be returned, since they are smaller ones according to the order.
620
621 \param value The key of the entry to be found.
622 \return An iterator referring to the found entry, or End(), if the
623 map doesn't contain any entry with the given key or a close
624 one according to \a less.
625 */
626 _VECTOR_MAP_TEMPLATE_LIST
627 _VECTOR_MAP_CLASS_TYPE::ConstIterator
FindClose(const Key & key,bool less)628 _VECTOR_MAP_CLASS_NAME::FindClose(const Key &key, bool less) const
629 {
630 bool exists = false;
631 int32 index = _FindInsertionIndex(key, exists);
632 // If not found, the index _FindInsertionIndex() returns will point to
633 // an element with a greater value or to End(). So, no special handling
634 // is needed for !less.
635 if (exists || !less)
636 return ConstIterator(this, fElements.IteratorForIndex(index));
637 // An element with a smaller value is desired. The previous one (if any)
638 // will do.
639 if (index > 0)
640 return ConstIterator(this, fElements.IteratorForIndex(index - 1));
641 return End();
642 }
643
644 // _FindInsertionIndex
645 /*! \brief Finds the index at which the entry with the supplied key is
646 located or at which it would need to be inserted.
647 \param key The key.
648 \param exists Is set to \c true, if the map does already contain an
649 entry with that key, to \c false otherwise.
650 \return The index at which the entry with the supplied key is
651 located or at which it would need to be inserted.
652 */
653 _VECTOR_MAP_TEMPLATE_LIST
654 int32
_FindInsertionIndex(const Key & key,bool & exists)655 _VECTOR_MAP_CLASS_NAME::_FindInsertionIndex(const Key &key,
656 bool &exists) const
657 {
658 // binary search
659 int32 lower = 0;
660 int32 upper = Count();
661 while (lower < upper) {
662 int32 mid = (lower + upper) / 2;
663 int cmp = fEntryStrategy.Compare(fEntryStrategy.GetKey(fElements[mid]),
664 key);
665 if (cmp < 0)
666 lower = mid + 1;
667 else
668 upper = mid;
669 }
670 exists = (lower < Count() && fEntryStrategy.Compare(key,
671 fEntryStrategy.GetKey(fElements[lower])) == 0);
672 return lower;
673 }
674
675
676 // entry strategies
677
678 namespace VectorMapEntryStrategy {
679
680 // Pair
681 template<typename Key, typename Value, typename KeyOrder>
682 class Pair {
683 public:
684 typedef const Key &KeyReference;
685
686 class Entry {
687 public:
Entry(const Key & key,const Value & value)688 Entry(const Key &key, const Value &value)
689 : key(key), value(value) {}
690
691 Key key;
692 Value value;
693 };
694
GetKey(const Entry & entry)695 inline KeyReference GetKey(const Entry &entry) const
696 {
697 return entry.key;
698 }
699
GetValue(const Entry & entry)700 inline const Value &GetValue(const Entry &entry) const
701 {
702 return entry.value;
703 }
704
GetValue(Entry & entry)705 inline Value &GetValue(Entry &entry) const
706 {
707 return entry.value;
708 }
709
MakeEntry(const Key & key,const Value & value)710 inline Entry MakeEntry(const Key &key, const Value &value) const
711 {
712 return Entry(key, value);
713 }
714
AreCompatible(const Key &,const Value &)715 inline bool AreCompatible(const Key &, const Value &) const
716 {
717 return true;
718 }
719
Compare(const Key & a,const Key & b)720 inline int Compare(const Key &a, const Key &b) const
721 {
722 return fCompare(a, b);
723 }
724
725 private:
726 KeyOrder fCompare;
727 };
728
729 // ImplicitKey
730 template<typename Key, typename Value, typename _GetKey, typename KeyOrder>
731 class ImplicitKey {
732 public:
733 typedef Key KeyReference;
734 typedef Value Entry;
735
GetKey(const Entry & entry)736 inline KeyReference GetKey(const Entry &entry) const
737 {
738 return fGetKey(entry);
739 }
740
GetValue(const Entry & entry)741 inline const Value &GetValue(const Entry &entry) const
742 {
743 return entry;
744 }
745
GetValue(Entry & entry)746 inline Value &GetValue(Entry &entry) const
747 {
748 return entry;
749 }
750
MakeEntry(const Key &,const Value & value)751 inline Entry MakeEntry(const Key &, const Value &value) const
752 {
753 return value;
754 }
755
AreCompatible(const Key & key,const Value & value)756 inline bool AreCompatible(const Key &key, const Value &value) const
757 {
758 return (fGetKey(value) == key);
759 }
760
Compare(const Key & a,const Key & b)761 inline int Compare(const Key &a, const Key &b) const
762 {
763 return fCompare(a, b);
764 }
765
766 private:
767 KeyOrder fCompare;
768 _GetKey fGetKey;
769 };
770
771 } // VectorMapEntryStrategy
772
773 #endif // _VECTOR_MAP_H
774