Source

mana-core-gaudikernel / GaudiKernel / VectorMap.h

Full commit
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
// $Id: VectorMap.h,v 1.11 2007/05/24 14:39:11 hmd Exp $
// ============================================================================
// CVS tag $Name:  $, version $Revision: 1.11 $
// ============================================================================
#ifndef GAUDIKERNEL_VECTORMAP_H
#define GAUDIKERNEL_VECTORMAP_H 1
// ============================================================================
// Include files
// ============================================================================
// STD & STL
// ============================================================================
#include <utility>
#include <functional>
#include <vector>
#include <algorithm>
#include <ostream>
// ============================================================================
// GaudiKernel
// ============================================================================
#include "GaudiKernel/MapBase.h"
// ============================================================================
namespace GaudiUtils
{
  // ==========================================================================
  /** @class VectorMap GaudiKernel/VectorMap.h
   *
   *  A bit modified version of 'Loki::AssocVector' associative
   *  vector from Loki library by Andrei Alexandrescu
   *
   *  The number of "non-const" operations is reduced,
   *  e.g. all non-const iterators are not exported,
   *  therefore it is almost impossible e.g. externally
   *  re-sort the underlying sorted container.
   *
   *  ---------------------------
   *  The nominal CPU performance:
   *  ---------------------------
   *    Container insertion: O(N)
   *    Container look-up:   O(log(N)) (a'la std::map, but a bit faster)
   *
   *  It could be used as a "light" and good alternative
   *  for std::map associative container, in the case of
   *  relatively rare insertion and frequent look-up.
   *
   *  Due to helper base class Gaudi::Utils::MapBase, this class 
   *  is "python-friendly", and one can perform all python 
   *  manipulaitons 
   *  in intuitive way:
   *  @code 
   *  
   *    >>> m = ...        ## get the map 
   *    >>> print m        ## print the map a'la python class dict 
   *    ...   
   *    >>> for key in m :  print key, m[key]   ## iteration over the map
   *    ...
   *    >>> for key,value in m.iteritems() : print key, value 
   *    ...
   *    >>> keys   = m.keys()                     ## get the list of keys 
   *    >>> values = m.values ()                  ## get the list of values 
   *    >>  items  = m.items  ()                  ## get the list of items 
   *
   *    >>> if 'one' in m           ## check the presence of the key in map
   * 
   *    >>>  v = m.get(key', None) ## return m[key] for existing key, else None
   *
   *    >>>  del m[key]      ## erase the key form the map 
   *
   *    >>> value m[key]     ## unchecked access through the key
   *    ...
   *    >>> m.update( key, value ) ## update/insert key/value pair 
   *    
   *   @endcode 
   *  
   *   @attention The syntax can be drastically simplified, if one 
   *              redefines the __setitem__ attribute:  
   *
   *   @code 
   *   
   *    >>> type(m).__setitem__ = Gaudi.Utils.MapBase.__setitem__ 
   *
   *    >>> m[key] = value  ## much more intuitive semantics for key insertion
   *   
   *   @endcode 
   *   In a similar way <c>__getitem__</c> and <c>__delitem__</c> methods 
   *   can be redefind 
   *
   *   To avoid the unnesessary expansion of dictionaries
   *   it is highly recommended to exclude from dictionary the following methods:
   *     - lower_bound 
   *     - upper_bound 
   *     - equal_range 
   *     - insert 
   *
   *   @see Gaudi::Utils::MapBase 
   *   
   *  @author Vanya BELYAEV Ivan.Belyaev@lapp.in2p3.fr
   *  @date   2005-07-23
   */
  template
  <
    class KEY                                                 ,
    class VALUE                                               ,
    class KEYCOMPARE=std::less<const KEY>                     ,
    class ALLOCATOR=std::allocator<std::pair<KEY,VALUE> >
    >
  class VectorMap : public Gaudi::Utils::MapBase
  {
  public:
    // ========================================================================
    /// the actual type of key
    typedef KEY                                    key_type         ;
    /// the actual type of value
    typedef VALUE                                  mapped_type      ;
    /// comparison of keys
    typedef KEYCOMPARE                             key_compare      ;
    /// the actual storage item
    typedef std::pair<key_type,mapped_type>        value_type       ;
    // ========================================================================
  public:
    // ========================================================================
    /// allocator (could be useful for optimizations)
    typedef ALLOCATOR                              allocator_type   ;
    /// the types to conform STL
    typedef typename ALLOCATOR::const_reference    reference        ;
    /// the types to conform STL
    typedef typename ALLOCATOR::const_reference    const_reference  ;
    /// the types to conform STL
    typedef typename ALLOCATOR::size_type          size_type        ;
    /// the types to conform STL
    typedef typename ALLOCATOR::difference_type    difference_type  ;
    // ========================================================================
  public:
    // ========================================================================
    /// the actual storage container (no export)
    typedef std::vector<value_type,allocator_type> _vector          ;
    // ========================================================================
  protected:
    // ========================================================================
    /// the regular iterator  (no export)
    typedef typename _vector::iterator             _iterator        ;
    // ========================================================================
  public:
    // ========================================================================
    /// visible const_iterator (exported)
    typedef typename _vector::const_iterator       iterator         ;
    /// visible const_iterator (exported)
    typedef typename _vector::const_iterator       const_iterator   ;
    /// visible reverse const_iterator (exported)
    typedef std::reverse_iterator<iterator>        reverse_iterator ;
    /// visible reverse const_iterator (exported)
    typedef std::reverse_iterator<const_iterator>  const_reverse_iterator ;
    /// visible iterator pait
    typedef std::pair<iterator,iterator>           iterators        ;
    /// visible iterator pait
    typedef std::pair<iterator,bool>               result_type      ;
    // ========================================================================
  public:
    // ========================================================================
    /** @struct _compare_type
     *  The actual structure used to compare the elements
     *  Only "key" is important for comparison
     */
    struct _compare_type : public key_compare
    {
    public:
      // ======================================================================
      /// constructor from the key-comparison criteria
      _compare_type ( const key_compare& cmp ) : key_compare ( cmp ) {} ;
      /// default constructor
      _compare_type ()                         : key_compare (     ) {} ;
      /// compare keys: use key_compare
      bool operator () ( const key_type&  k1 , const key_type&   k2 ) const
      { return this->key_compare::operator() ( k1 , k2 ) ; }
      /// compare pairs (key,mapped): use compare by keys
      bool operator() ( const value_type& v1 , const value_type& v2 ) const
      { return operator() ( v1.first, v2.first ); }
      /// compare key and pair (key,mapped): use compare by keys
      bool operator() ( const key_type&   k  , const value_type& v  ) const
      { return operator() ( k , v.first ) ; }
      /// compare pair (key,mapped) and the key: use compare by keys
      bool operator() ( const value_type& v  , const key_type  & k  ) const
      { return operator() ( v.first , k ) ; }
      // ======================================================================
    };
    // ========================================================================
    /// the actual comparison criteria for valye_type objects
    typedef _compare_type                            compare_type   ;
    // ========================================================================
  public:
    // ========================================================================
    // sequential access  (only const-versions!)
    // ========================================================================
    /// "begin"  iterator for sequential access (const-only version!)
    iterator         begin  () const { return m_vct . begin  () ; }
    /// "end"    iterator for sequential access (const-only version!)
    iterator         end    () const { return m_vct . end    () ; }
    /// "rbegin" iterator for sequential access (const-only version!)
    reverse_iterator rbegin () const { return m_vct . rbegin () ; }
    /// "rend"   iterator for sequential access (const-only version!)
    reverse_iterator rend   () const { return m_vct . rend   () ; }
    // ========================================================================
    // list operations : erase & insert
    // ========================================================================
    /** erase the element using the iterator
     *  @param pos position of the element to be erased
     */
    void erase  ( iterator pos ) { m_vct.erase ( iter ( pos ) ) ; }
    // ========================================================================
    /** erase the element using the key
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *  ...
     *  K key = ... ;
     *
     *  std::cout << " # of erased elements "
     *            << m.erase ( key ) << std::endl ;
     *  @endcode
     *
     *  @param key key for the element to be erased
     *  @return number of erased elements (0 or 1)
     */
    size_type erase  ( const key_type&    key    )
    {
      iterator pos = find ( key ) ;
      if ( end() == pos ) { return 0 ; }
      erase ( pos ) ;
      return 1 ;
    }
    // ========================================================================
    /** erase the sequence of elements using the iterators
     *  @param first begin iterator of sub-sequence to be erased
     *  @param end   end iterator of the sub_sequence to be erased
     *  @return number of erased elements
     */
    size_type erase  ( iterator           first   ,
                       iterator           last    )
    {
      m_vct.erase ( iter ( first ) , iter ( last )  ) ;
      return last - first ;
    }
    // ========================================================================
    /** erase the sequence of elements using the sequence of keys
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *  // some sequence of keys, to be removed
     *  KEYS keys = ... ;
     *
     *  std::cout
     *   << " # keys to be removed: " << keys.size()
     *   << " # keys removed: " << m.erase( keys.begin() , keys.end() )
     *   << std::endl ;
     *
     *  @endcode
     *
     *  @param first begin-iterator for the sequence of keys
     *  @param last    end-iterator for the sequence of keys
     *  @return number of erased elements
     */
    template <class TYPE>
    size_type erase  ( TYPE first , TYPE last )
    {
      size_type res = 0 ;
      for ( ; first != last ; ++first ) { res += erase ( *first ) ; }
      return res ;
    }
    // ========================================================================
    /** insert the (key,value) pair into the container
     *
     *  @attention there is no replacement for the existing key!
     *
     *  It is STL-compliant behavior for associative containers.
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m ;
     *
     *  K key  = ... ;
     *  V val1 = ... ;
     *  V val2 = ... ;
     *
     *  std::cout
     *     << " Before insert: " << m[key]                  // should be: V()
     *     << std::end ;
     *
     *  // insert the value into the map:
     *  const bool inserted1 = m.insert( key , val1 ).second ;
     *  std::cout
     *     << " 1st insert: "
     *     << Gaudi::Utils::toString( inserted1 )           // should be: "True"
     *     << " value: " << m[key]                          // should be: val1
     *     << std::endl ;
     *
     *  // try to re-insert another value with the same key:
     *  const bool inserted2 = m.insert( key , val2 ).second ;
     *  std::cout
     *     << " 2nd insert: "
     *     << Gaudi::Utils::toString( inserted2 )           // should be: "False"
     *     << " value: " << m[key]                          // should be: val1
     *     << std::endl ;
     *
     *  @endcode
     *
     *  @param  key    key value to be inserted
     *  @param  mapped value to be associated with the key
     *  @return position of the inserted elements with the flag
     *          which allows to distinguish the actual insertion
     */
    result_type insert
    ( const key_type&    key    ,
      const mapped_type& mapped  )
    { return insert ( value_type ( key , mapped ) ) ; }
    // ========================================================================
    /** insert the (key,value) pair into the container
     *
     *  @attention there is no replacement for the existing element!
     *
     *  It is STL-compliant behavior for associative containers.
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m ;
     *
     *  K key  = ... ;
     *  V val1 = ... ;
     *  V val2 = ... ;
     *
     *  std::cout
     *     << " Before insert: " << m[key]                  // should be: V()
     *     << std::end ;
     *
     *  // insert the value into the map:
     *  const bool inserted1 = m.insert ( std::make_pair( key , val1 ) ).second ;
     *  std::cout
     *     << " 1st insert: "
     *     << Gaudi::Utils::toString( inserted1 )           // should be: "True"
     *     << " value: " << m[key]                          // should be: val1
     *     << std::endl ;
     *
     *  // try to re-insert another value with the same key:
     *  const bool inserted2 = m.insert ( std::make_pair( key , val2 ) ).second ;
     *  std::cout
     *     << " 2nd insert: "
     *     << Gaudi::Utils::toString( inserted2 )           // should be: "False"
     *     << " value: " << m[key]                          // should be: val1
     *     << std::endl ;
     *
     *  @endcode
     *
     *  @param  value value to be inserted
     *  @return position of the inserted elements with the flag
     *          which allows to distinguish the actual insertion
     */
    result_type insert
    ( const value_type&  value  )
    {
      bool found = true ;
      _iterator result = lower_bound ( value.first ) ;
      if ( end() == result || compare( value.first , result -> first ) )
      { result = m_vct.insert ( result , value ) ; found = false ; }
      return result_type ( iter ( result ) , !found ) ;
    }
    // ========================================================================
    /** insert the element with some guess about its new position
     *  With the right guess the method could be  more efficient
     *  @attention there is no replacement for the existing element!
     *  @param  pos the guess about position where to insert the element
     *  @param  value value to be inserted
     *  @return position of the inserted elements with the flag
     *          which indicated the actual insertion
     */
    result_type insert
    ( iterator           pos    ,
      const value_type&  value  )
    {
      if ( pos != end() && compare ( *pos , value ) &&
           ( pos == end() - 1 ||
              ( !compare ( value , *( pos + 1 ) )
                && compare ( *( pos + 1 ) , value ) ) ) )
      { return result_type( m_vct.insert ( iter ( pos ) , value ) , true ) ; }
      return insert ( value ) ;
    }
    // ========================================================================
    /** insert the (key,value) pair into the container
     *  With the right guess the method could be more efficient
     *  @attention there is no replacement for the existing element!
     *  @param  pos    the guess about position where to insert the element
     *  @param  key    key value to be inserted
     *  @param  mapped value to be associated with the key
     *  @return position of the inserted elements with the flag
     *          which indicated the actual insertion
     */
    result_type insert
    ( iterator           pos    ,
      const key_type&    key    ,
      const mapped_type& mapped )
    { return insert ( pos , value_type ( key , mapped ) ) ; }
    // ========================================================================
    /** insert the sequence of elements into the container
     *  @attention there is no replacement for the existing element!
     *  @param first the begin iterator of the sequence
     *  @param last the end iterator of the sequence
     */
    template <class PAIRS>
    void insert
    ( PAIRS first ,
      PAIRS last  )
    { for ( ; first != last ; ++first ) { insert ( *first ) ; } }
    // ========================================================================
    /** insert into the container the elements from
     *  2 "parallel" sequences
     *  @attention there is no replacement for the existing element!
     *  @param kf the begin iterator of the sequence of keys
     *  @param kl the end iterator of the sequence of keys
     *  @param vf the begin iterator of the sequence of values
     */
    template <class KEYS, class VALUES> void insert
    ( KEYS   kf ,
      KEYS   kl ,
      VALUES vf )
    { for ( ; kf != kl ; ++kf, ++vf ) { insert ( *kf , *vf ) ; } }
    // ========================================================================
    // map operations: lookup, count, ...
    // ========================================================================
    /** find the element by key
     *
     *  @code
     *
     *  typedef GaudiUtils::VectorMap<K,V> Map ;
     *
     *  Map m  = ... ;
     *
     *  K key = ...;
     *
     *  // Is key in the container?
     *  Map::iterator ifound = m.find( key ) ;
     *
     *  if ( m.end() != ifound )
     *   {
     *     std::cout << "The value is : " << ifound->second << std::endl ;
     *   }
     *
     *  @endcode
     *
     *  @param key key to be searched
     *  @return iterator to the element position in the container
     */
    iterator find ( const key_type& key ) const
    {
      iterator res = lower_bound ( key ) ;
      if ( end() != res && compare ( key , res->first ) )
      { res = end(); }
      return res ;
    }
    // ========================================================================
    /** count number of elements with the certain key
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *  K key = ... ;
     *
     *  std::cout << " # of elements for the key: " << m.count(key) << std::end ;
     *
     *  @endcode
     *
     *  @param key key to be searched
     *  @return number of elements with the given key (0 or 1)
     */
    size_type count ( const key_type& key ) const
    { return end() == find ( key ) ? 0 : 1 ; }
    // ========================================================================
    iterator  lower_bound ( const key_type& key ) const
    { return std::lower_bound ( begin () , end () , key , compare () ) ; }
    iterator  upper_bound ( const key_type& key ) const
    { return std::upper_bound ( begin () , end () , key , compare () ) ; }
    iterators equal_range ( const key_type& key ) const
    { return std::equal_range ( begin () , end () , key , compare () ) ; }
    // ========================================================================
    // general container operations :
    // ========================================================================
    /// empty container ?
    bool      empty    () const { return m_vct . empty    () ; }
    /// number of elements
    size_type size     () const { return m_vct . size     () ; }
    /// maximal allowed size
    size_type max_size () const { return m_vct . max_size () ; }
    /// clear the container
    void clear    ()                { m_vct.clear   ()       ; }
    /// reserve the space in the container for at least 'num' elements
    void reserve  ( size_type num ) { m_vct.reserve ( num )  ; }
    // ========================================================================
    /// swap function, which 'swaps' the content of two containers
    void swap     ( VectorMap& other )
    {
      std::swap ( m_vct , other.m_vct ) ;
    }
    // ========================================================================
    // The basic comparison operators for container
    // ========================================================================
    /// comparison criteria for containers
    bool operator== ( const VectorMap& other ) const
    { return m_vct == other.m_vct ; }
    /// comparison criteria for containers
    bool operator<  ( const VectorMap& other ) const
    { return m_vct <  other.m_vct ; }
    // ========================================================================
    // The derived comparison operators for container
    // ========================================================================
    friend bool operator>  ( const VectorMap& left  ,
                             const VectorMap& right )
    { return    right < left     ; }
    friend bool operator!= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( left == right  ) ; }
    friend bool operator>= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( left  <  right ) ; }
    friend bool operator<= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( right <  left  ) ; }
    // ========================================================================    
    /** forced insertion of the key/mapped pair
     *  The method acts like "insert" but it *DOES*
     *  overwrite the existing mapped value.
     *
     *  @attention There is no STL analogue
     *
     *  The method is added on request from ATLAS
     *  (see Savannah report #21395 and #21394)
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *  K key  = ... ;
     *  V val1 = ... ;
     *  V val2 = ... ;
     *
     *  std::cout << "Value " << m[key] << std::endl ; // should be: V()
     *  m.update ( key , val1 ) ;
     *  std::cout << "Value " << m[key] << std::endl ; // should be: val1
     *  m.update ( key , val2 ) ;
     *  std::cout << "Value " << m[key] << std::endl ; // should be: val2
     *
     *  @endcode
     *
     *  @param key key value
     *  @param mapped mapped value
     *  @return true if the existing value has been replaced 
     */
    bool update
    ( const key_type&    key    ,
      const mapped_type& mapped )
    {
      _iterator result = lower_bound ( key ) ;
      if ( end() == result || compare ( key , result -> first ) )
      { 
        result = m_vct.insert ( result , value_type(key,mapped) ) ; 
        return false ;
      }
      else { result->second = mapped ; }
      //
      return true ;
    }
    // ========================================================================
    /** forced insertion of the key/mapped pair
     *  The method acts like "insert" but it *DOES*
     *  overwrite the mapped value.
     *
     *  @attention There is no STL analogue
     *
     *  The method is added on request from ATLAS
     *  (see Savannah report #21395 and #21394)
     *
     *  @code
     *
     *  GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *  K key  = ... ;
     *  V val1 = ... ;
     *  V val2 = ... ;
     *
     *  std::cout << "Value " << m[key] << std::endl ; // should be: V()
     *  m.update ( std::make_pair ( key , val1 ) ) ;
     *  std::cout << "Value " << m[key] << std::endl ; // should be: val1
     *  m.update ( std::make_pair ( key , val2 ) ) ;
     *  std::cout << "Value " << m[key] << std::endl ; // should be: val2
     *
     *  @endcode
     *
     *  @param  val a pair of (key,value)
     *  @return true if the existing value has been replaced 
     */
    bool update ( const value_type& val )
    { return update ( val.first , val.second ) ; }
    // ========================================================================
    /** access to element by key (const version)
     *  there is no container increment for missing keys
     *
     *  @attention The behavior different from std::map,
     *             it is similar to GaudiUtils::Map
     *
     *  The method is added on request from ATLAS
     *  (see Savannah report #21395 and #21394)
     *  For typical usage of this class in LHCb context
     *  as "ExtraInfo" field I would like to recommend
     *  to AVOID this method
     *
     *  @code
     *
     *   GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *   // OK:
     *   K key = ... ;
     *   std::cout << " Value: " << m(key) << std::end ; // it is OK!
     *
     *   // ERROR:
     *   V value = ... ;
     *   m(key) = value ;                                // ERROR!
     *
     *   @endcode
     *
     *  @see GaudiUtils::Map
     *  @param key key value
     *  @return mapped value for existing key and the
     *                 default value for non-existing key
     */
    const mapped_type& operator() ( const key_type& key ) const
    {
      static const mapped_type s_default = mapped_type() ;
      iterator res = find ( key ) ;
      if ( end() == res ) { return s_default ; }
      return res->second ;
    }
    // ========================================================================
    /** access to element by key (const version)
     *  there is no container increment for missing keys
     *
     *  @attention The behavior different from std::map,
     *             it is similar to GaudiUtils::Map
     *
     *  The method is added on request from ATLAS
     *  (see Savannah report #21395 and #21394)
     *  For typical usage of this class in LHCb context
     *  as "ExtraInfo" field I would like to recommend
     *  to AVOID this method
     *
     *  @code
     *
     *   GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *   // OK:
     *   K key = ... ;
     *   std::cout << " Value: " << m[key] << std::end ; // it is OK!
     *
     *   // ERROR:
     *   V value = ... ;
     *   m[key] = value ;                                // ERROR!
     *
     *   @endcode
     *
     *  @see GaudiUtils::Map
     *  @param key key value
     *  @return mapped value
     */
    const mapped_type& operator[] ( const key_type& key ) const
    { return (*this)( key ) ; }
    // ========================================================================
    /** checked access to elements by key
     *  throw std::out_of_range exception for non-existing keys
     *
     *  @code
     *
     *   GaudiUtils::VectorMap<K,V> m = ... ;
     *
     *   // OK:
     *   K key = ... ;
     *   std::cout << " Value: " << m.at(key) << std::end ; // it is OK!
     *
     *  @endcode
     *
     *  @exception std::out_of_range for non-existing keys
     *  @param key key value
     *  @return mapped value
     */
    const mapped_type& at ( const key_type& key ) const
    {
      iterator res = find ( key ) ;
      if ( end() == res ) { this->throw_out_of_range_exception () ; }
      return res->second ;
    }
    // ========================================================================
  public:
    // ========================================================================
    // Constructors, destructors, etc.
    // ========================================================================
    /** default constructor from the the allocator
     *  @param cmp comparison criteria for the key
     *  @param alloc allocator to be used
     */
    VectorMap ( const allocator_type& alloc = allocator_type () )
      : m_vct ( alloc )
    {}
    // ========================================================================
    /** copy constructor
     *  @param right object to be copied
     */
    VectorMap ( const VectorMap& right )
      : Gaudi::Utils::MapBase(right), m_vct ( right.m_vct )
    {}
    // ========================================================================
    /** templated constructor from "convertible" sequence
     *  @param first 'begin'-iterator for the convertible sequence
     *  @param last  'end'-iterator for the convertible sequence
     *  @param cmp comparison criteria for the key
     *  @param alloc allocator to be used
     */
    template <class INPUT>
    VectorMap ( INPUT first ,
                INPUT last  ,
                const allocator_type& alloc = allocator_type () )
      : m_vct ( first , last , alloc )
    { std::sort ( m_vct.begin(), m_vct.end(), compare() ) ; }
    // ========================================================================
    /// destructor (non-virtual!)
    ~VectorMap() { clear() ; }                     // destructor (non-virtual!)
    // ========================================================================
    /* assignement operator
     * @param rigth object to be assigned
     * @return self
     */
    VectorMap& operator= ( const VectorMap& right )
    {
      if ( &right == this ) { return *this ; }
      m_vct = right.m_vct ;
      return *this ;
    }
    // ========================================================================
  public:
    // ========================================================================
    // The specific public accessors
    // ========================================================================
    /// get the comparison criteria itself
    const compare_type& compare     () const
    {
      static const  compare_type s_cmp = compare_type() ;
      return s_cmp ;
    }
    /// get the comparison criteria for keys
    const key_compare&  compare_key () const { return compare()  ; }
    /// printout to ostream - not implemented
    friend std::ostream& operator<<
      ( std::ostream& str , const VectorMap& /* obj */) { return str ; }
    // ========================================================================
  public:
    // ========================================================================
    /// merge two maps 
    inline VectorMap& merge ( const VectorMap& right ) 
    {
      for ( const_iterator it = right.begin() ; right.end() != it ; ++it ) 
      { update ( it->first , it->second ) ; }
      //
      return *this ;
    }
    /// merge two maps 
    template <class K1,class K2, class K3,class K4>
    inline VectorMap& merge ( const VectorMap<K1,K2,K3,K4>& right ) 
    {
      for ( typename VectorMap<K1,K2,K3,K4>::const_iterator it = 
              right.begin() ; right.end() != it ; ++it ) 
      { update ( it->first , it->second ) ; }
      //
      return *this ;
    }
    // ========================================================================
  public:
    // ========================================================================
    /** useful method for python decoration: 
     *  @param index (INPUT) the index 
     *  @return the key at given index 
     *  @exception std::out_of_range for invalid index 
     */
    const key_type&    key_at   ( const size_t index ) const 
    {
      if ( index  >= size() ) 
      { this->throw_out_of_range_exception () ; }
      const_iterator it = this->begin() ;
      std::advance ( it , index ) ;
      return it -> first ;
    }
    /** useful method for python decoration: 
     *  @param index (INPUT) the index 
     *  @return the value at given index 
     *  @exception std::out_of_range for invalid index 
     */
    const mapped_type& value_at ( const size_t index ) const 
    {
      if ( index  >= size() ) 
      { this->throw_out_of_range_exception () ; }
      const_iterator it = this->begin() ;
      std::advance ( it , index ) ;
      return it -> second ;
    }
    // ========================================================================
  protected:
    // ========================================================================
    // Pure technical helper functions
    // ========================================================================
    /** compare the objects using the comaprison criteria
     *  @param obj the first object
     *  @param obj the second object
     *  @return result of (obj1,obj2) comparison
     */
    template <class TYPE1, class TYPE2>
    bool  compare ( const TYPE1& obj1 ,
                    const TYPE2& obj2 ) const
    {
      return compare() ( obj1 , obj2 )  ;
    }
    // ========================================================================
    /// 'lower-bound' - non-const version
    _iterator lower_bound ( const key_type& key )
    {
      return std::lower_bound
      ( m_vct.begin() , m_vct.end() , key , compare() ) ;
    } 
    // ========================================================================
    /// the conversion from 'const' to 'non-const' iterator
    _iterator iter (  iterator p )
    {
      _iterator result = m_vct.begin() ;
      std::advance ( result , std::distance ( begin() , p ) ) ;
      return result ;
    }
    // ========================================================================
    /// the conversion from 'non-const' to 'const' iterator
    iterator  iter ( _iterator p )
    {
      iterator result ( begin() ) ;
      std::advance ( result , std::distance (  m_vct.begin() , p ) ) ;
      return result ;
    }
    // ========================================================================
  private:
    // ========================================================================
    /// the underlying sorted vector of (key,mapped) pairs
    _vector      m_vct ; // the underlying sorted vector of (key,mapped) pairs
    // ========================================================================
  };
  // ==========================================================================
} //                                               end of namespace GaudiUtils 
// ============================================================================
namespace std
{
  // ==========================================================================
  /** the definition of specialized algorithm for swapping
   *  @param left  object to be swapped
   *  @param right object to be swapped
   */
  template
  < class KEY        ,
    class VALUE      ,
    class KEYCOMPARE ,
    class ALLOCATOR  >
  inline void swap
  ( GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& left  ,
    GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& right )
  { left.swap( right ) ; }
 // ===========================================================================
} //                                                       end of namespace std 
// ============================================================================

// ============================================================================
// The END
// ============================================================================
#endif // GAUDIKERNEL_MAPS_H
// ============================================================================