/[pcsx2_0.9.7]/trunk/common/include/Utilities/HashMap.h
ViewVC logotype

Contents of /trunk/common/include/Utilities/HashMap.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (10 years, 2 months ago) by william
File MIME type: text/plain
File size: 24099 byte(s)
committing r3113 initial commit again...
1 #pragma once
2
3 #include <google/type_traits.h>
4 #include <google/dense_hash_set>
5 #include <google/dense_hash_map>
6 #include <google/sparsehash/densehashtable.h>
7
8 namespace HashTools {
9
10 #define HashFriend(Key,T) friend class HashMap<Key,T>
11
12 /// Defines an equality comparison unary method.
13 /// Generally intended for internal use only.
14 #define _EQUALS_UNARY_OP( Type ) bool operator()(const Type s1, const Type s2) const { return s1.Equals( s2 ); }
15
16 /// Defines a hash code unary method
17 /// Generally intended for internal use only.
18 #define _HASHCODE_UNARY_OP( Type ) hash_key_t operator()( const Type& val ) const { return val.GetHashCode(); }
19
20 /// <summary>
21 /// Defines an equality comparison method within an encapsulating struct, using the 'unary method' approach.
22 /// </summary>
23 /// <remarks>
24 /// <para>
25 /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
26 /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
27 /// the HashCode predicate and Compare predicate.
28 /// </para>
29 /// The code generated by this macro is equivalent to this:
30 /// <code>
31 /// // where 'Type' is the parameter used in the macro.
32 /// struct UnaryEquals
33 /// {
34 /// bool operator()(const Type s1, const Type s2) const
35 /// {
36 /// return s1.Equals( s2 ); // this operator must be implemented by the user.
37 /// }
38 /// };
39 /// </code>
40 /// Note:
41 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
42 /// <c>operator ()</c>, such that the object instance itself acts as a method.
43 /// Note:
44 /// This methodology is similar to C# / .NET's <c>object.Equals()</c> method: The class member method
45 /// implementation of <c>Equals</c> should *not* throw exceptions -- it should instead return <c>false</c>
46 /// if either side of the comparison is not a matching type. See <see cref="IHashable" /> for details.
47 /// Note:
48 /// The reason for this (perhaps seemingly) hogwash red tape is because you can define custom
49 /// equality behavior for individual hashmaps, which are independent of the type used. The only
50 /// obvious scenario where such a feature is useful is in
51 /// </remarks>
52 /// <seealso cref="DEFINE_HASHCODE_UNARY"/>
53 /// <seealso cref="DEFINE_HASH_API"/>
54 /// <seealso cref="IHashable"/>
55 /// <seealso cref="HashMap"/>
56 #define DEFINE_EQUALS_UNARY( Type ) struct UnaryEquals{ _EQUALS_UNARY_OP( Type ) }
57
58 /// <summary>
59 /// Defines a hash code predicate within an encapsulating struct; for use in hashable user datatypes
60 /// </summary>
61 /// <remarks>
62 /// <para>
63 /// This macro is a shortcut helper to implementing types usable as keys in <see cref="HashMap"/>s.
64 /// Normally you will want to use <see cref="DEFINE_HASH_API"/> instead as it defines both
65 /// the HashCode predicate and Compare predicate.
66 /// </para>
67 /// The code generated by this macro is equivalent to this:
68 /// <code>
69 /// // where 'Type' is the parameter used in the macro.
70 /// struct UnaryHashCode
71 /// {
72 /// hash_key_t operator()( const Type& val ) const
73 /// {
74 /// return val.GetHashCode(); // this member function must be implemented by the user.
75 /// }
76 /// };
77 /// </code>
78 /// </remarks>
79 /// <seealso cref="DEFINE_EQUALS_UNARY"/>
80 /// <seealso cref="DEFINE_HASH_API"/>
81 /// <seealso cref="IHashable"/>
82 /// <seealso cref="HashMap"/>
83 #define DEFINE_HASHCODE_UNARY( Type ) struct UnaryHashCode{ _HASHCODE_UNARY_OP( Type ) }
84
85 /// <summary>
86 /// Defines the API for hashcode and comparison unary methods; for use in hashable user datatypes
87 /// </summary>
88 /// <remarks>
89 /// This macro creates APIs that allow the class or struct to be used as a key in a <see cref="HashMap"/>.
90 /// It requires that the data type implement the following items:
91 /// * An equality test via an <c>operator==</c> overload.
92 /// * A public instance member method <c>GetHashCode.</c>
93 /// The code generated by this macro is equivalent to this:
94 /// <code>
95 /// // where 'Type' is the parameter used in the macro.
96 /// struct UnaryHashCode
97 /// {
98 /// hash_key_t operator()( const Type& val ) const
99 /// {
100 /// return val.GetHashCode(); // this member function must be implemented by the user.
101 /// }
102 /// };
103 ///
104 /// struct UnaryEquals
105 /// {
106 /// bool operator()(const Type s1, const Type s2) const
107 /// {
108 /// return s1.Equals( s2 ); // this operator must be implemented by the user.
109 /// }
110 /// };
111 /// </code>
112 /// Note:
113 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
114 /// <c>operator ()</c>, such that the object instance itself acts as a method.
115 /// Note:
116 /// For class types you can use the <see cref="IHashable"/> interface, which also allows you to group
117 /// multiple types of objects into a single complex HashMap.
118 /// Note:
119 /// Generally speaking, you do not use the <c>IHashable</c> interface on simple C-style structs, since it
120 /// would incur the overhead of a vtbl and could potentially break code that assumes the structs to have
121 /// 1-to-1 data-to-declaration coorlations.
122 /// Note:
123 /// Internally, using this macro is functionally equivalent to using both <see cref="DEFINE_HASHCODE_CLASS"/>
124 /// and <see cref="DEFINE_EQUALS_CLASS"/>.
125 /// </remarks>
126 /// <seealso cref="IHashable"/>
127 /// <seealso cref="DEFINE_HASHCODE_CLASS"/>
128 /// <seealso cref="DEFINE_COMPARE_CLASS"/>
129 /// <seealso cref="DEFINE_HASH_API"/>
130 /// <seealso cref="HashMap"/>
131 #define DEFINE_HASH_API( Type ) DEFINE_HASHCODE_UNARY( Type ); DEFINE_EQUALS_UNARY( Type );
132
133 /// <summary>
134 /// A helper macro for creating custom types that can be used as <see cref="HashMap" /> keys.
135 /// </summary>
136 /// <remarks>
137 /// Use of this macro is only needed if the hashable type in question is a struct that is a private
138 /// local to the namespace of a containing class.
139 /// </remarks>
140 #define PRIVATE_HASHMAP( Key, T ) \
141 typedef SpecializedHashMap<Key, T> Key##HashMap; \
142 friend Key##HashMap;
143
144 /// <summary>
145 /// Type that represents a hashcode; returned by all hash functions.
146 /// </summary>
147 /// <remarks>
148 /// In theory this could be changed to a 64 bit value in the future, although many of the hash algorithms
149 /// would have to be changed to take advantage of the larger data type.
150 /// </remarks>
151 typedef u32 hash_key_t;
152
153 hash_key_t Hash(const char* data, int len);
154
155 struct CommonHashClass;
156 extern const CommonHashClass GetCommonHash;
157
158 /// <summary>
159 /// A unary-style set of methods for getting the hash code of C++ fundamental types.
160 /// </summary>
161 /// <remarks>
162 /// This class is used to pass hash functions into the <see cref="HashMap"/> class and
163 /// it's siblings. It houses methods for most of the fundamental types of C++ and the STL,
164 /// such as all int and float types, and also <c>std::string</c>. All functions can be
165 /// accessed via the () overload on an instance of the class, such as:
166 /// <code>
167 /// const CommonHashClass GetHash;
168 /// int v = 27;
169 /// std::string s = "Joe's World!";
170 /// hash_key_t hashV = GetHash( v );
171 /// hash_key_t hashS = GetHash( s );
172 /// </code>
173 /// Note:
174 /// In C++, the term 'unary method' refers to a method that is implemented as an overload of the
175 /// <c>operator ()</c>, such that the object instance itself acts as a method.
176 /// </remarks>
177 /// <seealso cref="GetCommonHash"/>
178 struct CommonHashClass
179 {
180 public:
181 // GCC needs empty constructors on const instances, because it likes pointlessness.
182 CommonHashClass() {}
183
184 hash_key_t DoInt( u32 val ) const
185 {
186 u32 key = val;
187 key = ~key + (key << 15);
188 key = key ^ (key >> 12);
189 key = key + (key << 2);
190 key = key ^ (key >> 4);
191 key = key * 2057;
192 key = key ^ (key >> 16);
193
194 return val;
195 }
196
197 hash_key_t operator()(const std::string& src) const
198 {
199 return Hash( src.data(), src.length() );
200 }
201
202 hash_key_t operator()( const std::wstring& src ) const
203 {
204 return Hash( (const char *)src.data(), src.length() * sizeof( wchar_t ) );
205 }
206
207 // Returns a hashcode for a character.
208 // This has function has been optimized to return an even distribution
209 // across the range of an int value. In theory that should be more rewarding
210 // to hastable performance than a straight up char lookup.
211 hash_key_t operator()( const char c1 ) const
212 {
213 // Most chars contain values between 0 and 128, so let's mix it up a bit:
214 int cs = (int)( c1 + (char)64 );
215 return ( cs + ( cs<<8 ) + ( cs << 16 ) + (cs << 24 ) );
216 }
217
218 hash_key_t operator()( const wchar_t wc1 ) const
219 {
220 // Most unicode values are between 0 and 128, with 0-1024
221 // making up the bulk of the rest. Everything else is spatially used.
222 /*int wcs = (int) ( wc1 + 0x2000 );
223 return wcs ^ ( wcs + 0x19000 );*/
224
225 // or maybe I'll just feed it into the int hash:
226 return GetCommonHash( (u32)wc1 );
227 }
228
229 /// <summary>
230 /// Gets the hash code for a 32 bit integer.
231 /// </summary>
232 /// <remarks>
233 /// This method performs a very fast algorithm optimized for typical integral
234 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
235 /// leaving the extremes un-used).
236 /// Note:
237 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
238 /// </remarks>
239 hash_key_t operator()( const u32 val ) const
240 {
241 return DoInt(val);
242 }
243
244 /// <summary>
245 /// Gets the hash code for a 32 bit integer.
246 /// </summary>
247 /// <remarks>
248 /// This method performs a very fast algorithm optimized for typical integral
249 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
250 /// leaving the extremes un-used).
251 /// Note:
252 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
253 /// </remarks>
254 hash_key_t operator()( const s32 val ) const
255 {
256 return DoInt(val);
257 }
258
259 /// <summary>
260 /// Gets the hash code for a 64 bit integer.
261 /// </summary>
262 /// <remarks>
263 /// This method performs a very fast algorithm optimized for typical integral
264 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
265 /// leaving the extremes un-used).
266 /// Note:
267 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
268 /// </remarks>
269 hash_key_t operator()( const u64 val ) const
270 {
271 u64 key = val;
272 key = (~key) + (key << 18);
273 key = key ^ (key >> 31);
274 key = key * 21; // key = (key + (key << 2)) + (key << 4);
275 key = key ^ (key >> 11);
276 key = key + (key << 6);
277 key = key ^ (key >> 22);
278 return (u32) key;
279 }
280
281 /// <summary>
282 /// Gets the hash code for a 64 bit integer.
283 /// </summary>
284 /// <remarks>
285 /// This method performs a very fast algorithm optimized for typical integral
286 /// dispersion patterns (which tend to favor a bit heavy on the lower-range of values while
287 /// leaving the extremes un-used).
288 /// Note:
289 /// Implementation is based on an article found here: http://www.concentric.net/~Ttwang/tech/inthash.htm
290 /// </remarks>
291 hash_key_t operator()( const s64 val ) const
292 {
293 return GetCommonHash((u64)val);
294 }
295
296 hash_key_t operator()( const float val ) const
297 {
298 // floats do a fine enough job of being scattered about
299 // the universe:
300 return *((hash_key_t *)&val);
301 }
302
303 hash_key_t operator()( const double val ) const
304 {
305 // doubles have to be compressed into a 32 bit value:
306 return GetCommonHash( *((u64*)&val) );
307 }
308
309 /// <summary>
310 /// Calculates the hash of a pointer.
311 /// </summary>
312 /// <remarks>
313 /// This method has been optimized to give typical 32 bit pointers a reasonably
314 /// wide spread across the integer spectrum.
315 /// Note:
316 /// This method is optimized for 32 bit pointers only. 64 bit pointer support
317 /// has not been implemented, and thus on 64 bit platforms performance could be poor or,
318 /// worse yet, results may not have a high degree of uniqueness.
319 /// </remarks>
320 hash_key_t operator()( const void* addr ) const
321 {
322 hash_key_t key = (hash_key_t) addr;
323 return (hash_key_t)((key >> 3) * 2654435761ul);
324 }
325 };
326
327 /// <summary>
328 /// This class contains comparison methods for most fundamental types; and is used by the CommonHashMap class.
329 /// </summary>
330 /// <remarks>
331 /// The predicates of this class do standard equality comparisons between fundamental C/STL types such as
332 /// <c>int, float</c>, and <c>std::string.</c> Usefulness of this class outside the <see cref="CommonHashMap"/>
333 /// class is limited.
334 /// </remarks>
335 /// <seealso cref="CommonHashMap">
336 struct CommonComparisonClass
337 {
338 bool operator()(const char* s1, const char* s2) const
339 {
340 return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
341 }
342 };
343
344 /// <summary>
345 /// An interface for classes that implement hashmap functionality.
346 /// </summary>
347 /// <remarks>
348 /// This class provides interface methods for getting th hashcode of a class and checking for object
349 /// equality. It's general intent is for use in situations where you have to store *non-similar objects*
350 /// in a single unified hash map. As all object instances derive from this type, it allows the equality
351 /// comparison to use typeid or dynamic casting to check for type similarity, and then use more detailed
352 /// equality checks for similar types.
353 /// </remarks>
354 class IHashable
355 {
356 public:
357 /// Obligatory Virtual destructor mess!
358 virtual ~IHashable() {};
359
360 /// <summary>
361 /// Your basic no-thrills equality comparison; using a pointer comparison by default.
362 /// </summary>
363 /// <remarks>
364 /// This method uses a pointer comparison by default, which is the only way to really compare objects
365 /// of unrelated types or of derrived types. When implementing this method, you may want to use typeid comparisons
366 /// if you want derived types to register as being non-equal, or <c>dynamic_cast</c> for a more robust
367 /// base-class comparison (illustrated in the example below).
368 /// Note:
369 /// It's recommended important to always do a pointer comparison as the first step of any object equality check.
370 /// It is fast and easy, and 100% reliable.
371 /// </remarks>
372 /// <example>
373 /// Performing non-pointer comparisons:
374 /// <code>
375 /// class Hasher : IHashable
376 /// {
377 /// int someValue;
378 ///
379 /// virtual bool Equals( const IHashable& right ) const
380 /// {
381 /// // Use pointer comparison first since it's fast and accurate:
382 /// if( &right == this ) return true;
383 ///
384 /// Hasher* them = dynamic_cast&lt;Hasher*&gt;( right );
385 /// if( them == NULL ) return false;
386 /// return someValue == them->SomeValue;
387 /// }
388 /// }
389 /// </code>
390 /// </example>
391 virtual bool Equals( const IHashable& right ) const
392 {
393 return ( &right == this ); // pointer comparison.
394 }
395
396 /// <summary>
397 /// Returns a hash value for this object; by default the hash of its pointer address.
398 /// </summary>
399 /// <remarks>
400 /// </remarks>
401 /// <seealso cref="HashMap"/>
402 virtual hash_key_t GetHashCode() const
403 {
404 return GetCommonHash( this );
405 }
406 };
407
408 template< typename Key >
409 class HashSet : public google::dense_hash_set< Key, CommonHashClass >
410 {
411 public:
412 /// <summary>
413 /// Constructor.
414 /// </summary>
415 /// <remarks>
416 /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
417 /// are *not* used as actual values in the set.
418 /// </remarks>
419 HashSet( Key emptyKey, Key deletedKey, int initialCapacity=33 ) :
420 google::dense_hash_set<Key, CommonHashClass>( initialCapacity )
421 {
422 set_empty_key( emptyKey );
423 set_deleted_key( deletedKey );
424 }
425 };
426
427 /// <summary>
428 /// Defines a hashed collection of objects and provides methods for adding, removing, and reading items.
429 /// </summary>
430 /// <remarks>
431 /// <para>This class is for hashing out a set data using objects as keys. Objects should derive from the
432 /// <see cref="IHashable"/> type, and in either case *must* implement the UnaryHashCode and UnaryEquals
433 /// unary classes.</para>
434 /// <para>*Details On Implementing Key Types*</para>
435 /// <para>
436 /// Custom hash keying uses what I consider a somewhat contrived method of implementing the Key type;
437 /// involving a handful of macros in the best case, and a great deal of syntaxical red tape in
438 /// the worst case. Most cases should fall within the realm of the macros, which make life a lot easier,
439 /// so that's the only implementation I will cover in detail here (see below for example).
440 /// </para>
441 /// Note:
442 /// For most hashs based on common or fundamental types or types that can be adequately compared using
443 /// the default equality operator ==, such as <c>int</c> or structs that have no padding alignment concerns,
444 /// use <see cref="HashMap" /> instead. For string-based hashs, use <see cref="Dictionary" /> or <see cref="UnicodeDictionary" />.
445 /// </remarks>
446 /// <example>
447 /// This is an example of making a hashable type out of a struct. This is useful in situations where
448 /// inheriting the <see cref="IHashable"/> type would cause unnecessary overhead and/or broken C/C++
449 /// compatability.
450 /// <code>
451 /// struct Point
452 /// {
453 /// int x, y;
454 ///
455 /// // Empty constructor is necessary for HashMap.
456 /// // This can either be initialized to zero, or uninitialized as here:
457 /// Point() {}
458 ///
459 /// // Copy Constructor is just always necessary.
460 /// Point( const Point& src ) : first( src.first ), second( src.second ) {}
461 ///
462 /// // Standard content constructor (Not needed by HashMap)
463 /// Point( int xpos, int ypos ) : x( xpos ), y( ypos ) {}
464 ///
465 /// /**** Begin Hashmap Interface Implementation ****/
466 ///
467 /// // HashMap Requires both GetEmptyKey() and GetDeleteKey() instance member
468 /// // methods to be defined. These act as defaults. The actual values used
469 /// // can be overridden on an individual HashMap basis via the HashMap constructor.
470 ///
471 /// static Point GetEmptyKey() { return Point( -0xffffff, 0xffffff ); }
472 /// static Point GetDeletedKey() { return Kerning( -0xffffee, 0xffffee ); }
473 ///
474 /// // HashMap Requires an Equality Overload.
475 /// // The inequality overload is not required but is probably a good idea since
476 /// // orphaned equality (without sibling inequality) operator overloads are ugly code.
477 ///
478 /// bool Equals( const Point& right ) const
479 /// {
480 /// return ( x == right.x ) && ( y == right.y );
481 /// }
482 ///
483 /// hash_key_t GetHashCode() const
484 /// {
485 /// // This is a decent "universal" hash method for when you have multiple int types:
486 /// return GetCommonHash( x ) ^ GetCommonHash( y );
487 /// }
488 ///
489 /// // Use a macro to expose the hash API to the HashMap templates.
490 /// // This macro creates MakeHashCode and Compare structs, which use the ()
491 /// // operator to create "unary methods" for the GetHashCode and == operator above.
492 /// // Feeling dizzy yet? Don't worry. Just follow this template. It works!
493 ///
494 /// DEFINE_HASH_API( Point );
495 ///
496 /// /**** End HashMap Interface Implementation ****/
497 /// };
498 /// </code>
499 /// </example>
500 template< class Key, class T >
501 class SpecializedHashMap : public google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>
502 {
503 public:
504 virtual ~SpecializedHashMap() {}
505 SpecializedHashMap( int initialCapacity=33, Key emptyKey=Key::GetEmptyKey(), Key deletedKey=Key::GetDeletedKey() ) :
506 google::dense_hash_map<Key, T, typename Key::UnaryHashCode, typename Key::UnaryEquals>( initialCapacity )
507 {
508 set_empty_key( emptyKey );
509 set_deleted_key( deletedKey );
510 }
511
512 /// <summary>
513 /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
514 /// </summary>
515 /// <remarks>
516 /// If found, the value associated with the requested key is copied into the <c>outval</c>
517 /// parameter. This is a more favorable alternative to the indexer operator since the
518 /// indexer implementation can and will create new entries for every request that
519 /// </remarks>
520 /*void TryGetValue( const Key& key, T& outval ) const
521 {
522 // GCC doesn't like this for some reason -- says const_iterator can't be found.
523 // Fortunately nothing uses these functions yet, so I just commented them out. --air
524 const_iterator iter = find( key );
525 if( iter != end() )
526 outval = iter->second;
527 }*/
528
529 const T& GetValue( Key key ) const
530 {
531 return (this->find( key ))->second;
532 }
533 };
534
535 /// <summary>
536 /// This class implements a hashmap that uses fundamental types such as <c>int</c> or <c>std::string</c>
537 /// as keys.
538 /// </summary>
539 /// <remarks>
540 /// This class is provided so that you don't have to jump through hoops in order to use fundamental types as
541 /// hash keys. The <see cref="HashMap" /> class isn't suited to the task since it requires the key type to
542 /// include a set of unary methods. Obviously predicates cannot be added to fundamentals after the fact. :)
543 /// Note:
544 /// Do not use <c>char *</c> or <c>wchar_t *</c> as key types. Use <c>std::string</c> and <c>std::wstring</c>
545 /// instead, as performance of those types will generally be superior due to string length caching. For that
546 /// matter, don't use this class at all! Use the string-specialized classes <see cref="Dictionary" /> and
547 /// <see cref="UnicodeDictionary" />.
548 /// </remarks>
549 template< class Key, class T >
550 class HashMap : public google::dense_hash_map<Key, T, CommonHashClass>
551 {
552 typedef typename google::dense_hash_map<Key, T, CommonHashClass> _parent;
553
554 public:
555 using _parent::operator[];
556 using _parent::end;
557 typedef typename _parent::const_iterator const_iterator;
558
559 virtual ~HashMap() {}
560
561 /// <summary>
562 /// Constructor.
563 /// </summary>
564 /// <remarks>
565 /// Both the <c>emptyKey</c>a nd c>deletedKey</c> parameters must be unique values that
566 /// are *not* used as actual values in the set.
567 /// </remarks>
568 HashMap( const Key& emptyKey, const Key& deletedKey, int initialCapacity=33 ) :
569 google::dense_hash_map<Key, T, CommonHashClass>( initialCapacity )
570 {
571 set_empty_key( emptyKey );
572 set_deleted_key( deletedKey );
573 }
574
575 /// <summary>
576 /// Tries to get a value from this hashmap; or does nothing if the Key does not exist.
577 /// </summary>
578 /// <remarks>
579 /// If found, the value associated with the requested key is copied into the <c>outval</c>
580 /// parameter. This is a more favorable alternative to the indexer operator since the
581 /// indexer implementation can and will create new entries for every request that
582 /// </remarks>
583 void TryGetValue( const Key& key, T& outval ) const
584 {
585 const_iterator iter( find(key) );
586 if( iter != end() )
587 outval = iter->second;
588 }
589
590 const T& GetValue( Key key ) const
591 {
592 return (this->find( key ))->second;
593 }
594 };
595
596 /// <summary>
597 /// A shortcut class for easy implementation of string-based hash maps.
598 /// </summary>
599 /// <remarks>
600 /// Note:
601 /// This class does not support Unicode character sets natively. To use Unicode strings as keys,
602 /// use <see cref="UnicodeDictionary"/> instead.
603 /// </remarks>
604 template< class T >
605 class Dictionary : public HashMap<std::string, T>
606 {
607 public:
608 virtual ~Dictionary() {}
609
610 Dictionary( int initialCapacity=33, const std::string& emptyKey = "@@-EMPTY-@@", const std::string& deletedKey = "@@-DELETED-@@" ) :
611 HashMap<std::string, T>( emptyKey, deletedKey, initialCapacity)
612 {
613 }
614 private:
615 Dictionary( const Dictionary& src ) {}
616 };
617
618 /// <summary>
619 /// A shortcut class for easy implementation of string-based hash maps.
620 /// </summary>
621 /// <remarks>
622 /// Note:
623 /// This class does incur some amount of additional overhead over <see cref="Dictionary"/>, as it
624 /// requires twice as much memory and much hash twice as much data.
625 /// If you're only using the hash for friendly named array access (via string constants)
626 /// then you should probably just stick to using the regular dictionary.
627 /// </remarks>
628 template< class T >
629 class UnicodeDictionary : public HashMap<std::wstring, T>
630 {
631 public:
632 virtual ~UnicodeDictionary() {}
633
634 UnicodeDictionary( int initialCapacity=33, const std::wstring& emptyKey = L"@@-EMPTY-@@", const std::wstring& deletedKey = L"@@-DELETED-@@" ) :
635 HashMap<std::wstring, T>( emptyKey, deletedKey, initialCapacity)
636 {
637 }
638
639 private:
640 UnicodeDictionary( const UnicodeDictionary& src ) {}
641 };
642
643 }

  ViewVC Help
Powered by ViewVC 1.1.22