CLHEP/HepPDT/MapVector.hh

00001 
00002 #ifndef STLUTIL_MAPVECTOR_H
00003 #define STLUTIL_MAPVECTOR_H 1
00004 
00005 #include "CLHEP/config/CLHEP.h"
00006 #include <memory>
00007 #include <algorithm>
00008 #include <functional>
00009 #include <vector>
00010 #include <utility>
00011 
00012 /*
00013         Author: Jim Kowalkowski
00014         Date:           8/20/2000
00015 
00016         $Id: MapVector.hh,v 1.4 2002/04/18 20:15:19 garren Exp $
00017 
00018         This class acts like an std::map, but can be populated like an
00019         std::vector.  Why? Filling a map with lots of data is time
00020         consuming.  Vectors fill very fast provided you reserve space.
00021         The search (find) in this class is binary_search (as good or
00022         better than std::map).  The trick is that the vector inside
00023         is sorted by key on first access so that binary_search can
00024         work.  So this class does not do well for problem that
00025         require adding an item, then searching for another, adding
00026         an item, then searching for another, and so on...
00027         
00028         There is still a minor problem to resolve here.  The KEY was not
00029         const, so one could perhaps modify it.  If I made it const
00030         in value_type, then one cannot sort it or insert items.
00031         So I made a class called MapVecPair to use instead of std::pair,
00032         but this means that one can still copy a new "pair" over an existing
00033         entry (bad thing to do), but one cannot modify the key.
00034         I still have not figured out a way to prevent copying except
00035         by priviledged classes (things in MapVector, like its std::vector)
00036         and prevent reassignment of the key.
00037 
00038 */
00039 
00044 template <class KEY, class DATA, class COMP=std::less<KEY>,
00045         class Allocator=std::allocator<std::pair<KEY,DATA> > >
00046 class MapVector
00047 {
00048 public:
00049         typedef std::pair<KEY,DATA> value_type;
00050         typedef DATA data_type;
00051         typedef KEY key_type;
00052         typedef COMP compare_type;
00053         typedef Allocator allocator_type;
00054         typedef std::vector<value_type,allocator_type> collection_type;
00055         typedef typename collection_type::iterator iterator;
00056         typedef typename collection_type::const_iterator const_iterator;
00057         typedef typename collection_type::reference reference;
00058         typedef typename collection_type::const_reference const_reference;
00059         typedef typename collection_type::size_type size_type;
00060 
00061         MapVector();
00062 
00063         iterator find(const key_type& key);
00064         const_iterator find(const key_type& key) const;
00065 
00066         /*
00067         The choice was made here to give this operator map-like
00068         behavior instead of vector-like behavior.  This present
00069         performance problems depending on the type DATA.
00070         There is also the problem that if the object does not exist,
00071         it is created.  This causes a search, which could cause a sort
00072         or resize of the underlying container, which could cause all the
00073         elements to move position, so the iterators are not valid and
00074         the references are not likely to be valid.  Be careful about
00075         holding onto the reference, it is not guarenteed to be correct
00076         about a search or insert.
00077         */
00078 
00079         DATA& operator[](const key_type& key);
00080 
00081         // here is the vector-like access to elements
00082         reference at(size_type s) { cont.at(s); }
00083         const_reference at(size_type s) const { cont.at(s); }
00084 
00085         iterator end() { return cont.end(); }
00086         const_iterator end() const { return cont.end(); }
00087         iterator begin() { return cont.begin(); }
00088         const_iterator begin() const { return cont.begin(); }
00089 
00090         void add(const key_type& key, const data_type& data);
00091         void push_back(const value_type& newitem);
00092 
00093         iterator insert(iterator i,const value_type& newitem)
00094                 { push_back(newitem); return i;}
00095 
00096         void reserve(typename collection_type::size_type x) { cont.reserve(x); }
00097 
00098         size_type size() const { return cont.size(); }
00099 
00100 private:
00101         friend class MapVectorTest;
00102         void sort_() const;
00103         iterator find_(const key_type& key) const;
00104 
00105         struct comp
00106         {
00107                 bool operator()(const value_type& a, const value_type& b)
00108                 {
00109                         compare_type c;
00110                         return c(a.first,b.first);
00111                 }
00112         };
00113 
00114         struct comp2
00115         {
00116                 bool operator()(const value_type& a, const key_type& b)
00117                 {
00118                         compare_type c;
00119                         return c(a.first,b);
00120                 }
00121         };
00122 
00123         mutable collection_type cont;
00124         mutable bool is_sorted_;
00125 };
00126 
00127 // -------------------- implementation details -------------------------
00128 
00129 template <class KEY,class DATA,class COMP,class Allocator>
00130 inline MapVector<KEY,DATA,COMP,Allocator>::MapVector():is_sorted_(true) { }
00131 
00132 template <class KEY,class DATA,class COMP,class Allocator>
00133 inline void MapVector<KEY,DATA,COMP,Allocator>::sort_() const
00134 {
00135         if(is_sorted_==false)
00136         {
00137                 std::sort(cont.begin(),cont.end(),comp());
00138                 is_sorted_=true;
00139         }
00140 }
00141 
00142 template <class KEY,class DATA,class COMP,class Allocator>
00143 inline DATA& MapVector<KEY,DATA,COMP,Allocator>::operator[](const key_type& key)
00144 {
00145         if (cont.size() == 0) {
00146                 push_back( value_type(key,data_type()) );
00147                 return cont.back().second;
00148         }
00149 
00150         if (is_sorted_) {
00151 
00152             COMP comp;
00153 
00154             if (comp(cont.back().first, key)) {
00155                 push_back(value_type(key, data_type()));
00156             }
00157 
00158             if (! comp(key, cont.back().first)) {
00159                 return cont.back().second;
00160             }
00161         }
00162 
00163         iterator i = find(key);
00164 
00165         if(i!=end())
00166                 return i->second;
00167         else
00168         {
00169                 push_back( value_type(key,data_type()) );
00170                 return cont.back().second;
00171         }
00172 }
00173 
00174 template <class KEY,class DATA,class COMP,class Allocator>
00175 inline typename MapVector<KEY,DATA,COMP,Allocator>::iterator
00176 MapVector<KEY,DATA,COMP,Allocator>::find(const key_type& key)
00177 {
00178         return find_(key);
00179 }
00180 
00181 template <class KEY,class DATA,class COMP,class Allocator>
00182 inline typename MapVector<KEY,DATA,COMP,Allocator>::const_iterator
00183 MapVector<KEY,DATA,COMP,Allocator>::find(const key_type& key) const
00184 {
00185         return find_(key);
00186 }
00187 
00188 template <class KEY,class DATA,class COMP,class Allocator>
00189 inline typename MapVector<KEY,DATA,COMP,Allocator>::iterator
00190 MapVector<KEY,DATA,COMP,Allocator>::find_(const key_type& key) const
00191 {
00192                 sort_();
00193                 iterator x(std::lower_bound(cont.begin(),cont.end(),key,comp2()));
00194                 if(x==cont.end()) return x;
00195                 if(x->first!=key) return cont.end();
00196                 return x;
00197 }
00198 
00199 template <class KEY,class DATA,class COMP,class Allocator>
00200 inline void MapVector<KEY,DATA,COMP,Allocator>::push_back(const value_type& newitem)
00201 {
00202         COMP comp;
00203         if (cont.size() > 0 &&
00204             comp(newitem.first, cont.back().first)) is_sorted_ = false;
00205         cont.push_back(newitem);
00206 }
00207 
00208 template <class KEY,class DATA,class COMP,class Allocator>
00209 inline void
00210 MapVector<KEY,DATA,COMP,Allocator>::add(const key_type& key, const data_type& data)
00211 {
00212         push_back(value_type(key,data));
00213 }
00214 
00215 #endif

Class Library for High Energy Physics (version 1.8)