← Back to branch summary

~ubuntu-branches/ubuntu/maverick/asc/maverick

« back to all changes in this revision

Viewing changes to source/libs/loki/Reference/AssocVector.h

  • Committer: Bazaar Package Importer
  • Author(s): Barry deFreese, Eddy Petrișor, Gonéri Le Bouder, Cyril Brulebois, Barry deFreese
  • Date: 2008-01-08 19:54:18 UTC
  • mfrom: (1.1.4 upstream)
  • Revision ID: james.westby@ubuntu.com-20080108195418-n19fc4eobhhqxcy5
Tags: 2.0.1.0-1
[ Eddy Petrișor ]
* fixed Homepage semifield

[ Gonéri Le Bouder ]
* add a watchfile
* move homepage from the description to the new Homepage field

[ Cyril Brulebois ]
* Added Vcs-Svn and Vcs-Browser fields in the control file.

[ Barry deFreese ]
* Fix make-clean lintian warning
* New upstream release
* Bump debhelper build-dep to match compat
* Add desktop file
* Update watch file for new upstream naming
* Remove nostrip check from rules
* Bump Standards Version to 3.7.3
* Add myself to uploaders

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/libs/loki/Reference/AssocVector.h
 
1
////////////////////////////////////////////////////////////////////////////////
 
2
// The Loki Library
 
3
// Copyright (c) 2001 by Andrei Alexandrescu
 
4
// This code accompanies the book:
 
5
// Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design 
 
6
//     Patterns Applied". Copyright (c) 2001. Addison-Wesley.
 
7
// Permission to use, copy, modify, distribute and sell this software for any 
 
8
//     purpose is hereby granted without fee, provided that the above copyright 
 
9
//     notice appear in all copies and that both that copyright notice and this 
 
10
//     permission notice appear in supporting documentation.
 
11
// The author or Addison-Wesley Longman make no representations about the 
 
12
//     suitability of this software for any purpose. It is provided "as is" 
 
13
//     without express or implied warranty.
 
14
////////////////////////////////////////////////////////////////////////////////
 
15
 
 
16
#ifndef ASSOCVECTOR_INC_
 
17
#define ASSOCVECTOR_INC_
 
18
 
 
19
#include <algorithm>
 
20
#include <functional>
 
21
#include <vector>
 
22
#include <utility>
 
23
 
 
24
namespace Loki
 
25
{
 
26
////////////////////////////////////////////////////////////////////////////////
 
27
// class template AssocVectorCompare
 
28
// Used by AssocVector
 
29
////////////////////////////////////////////////////////////////////////////////
 
30
 
 
31
    namespace Private
 
32
    {
 
33
        template <class Value, class C>
 
34
        class AssocVectorCompare : public C
 
35
        {
 
36
            typedef std::pair<typename C::first_argument_type, Value>
 
37
                Data;
 
38
            typedef typename C::first_argument_type first_argument_type;
 
39
 
 
40
        public:
 
41
            AssocVectorCompare()
 
42
            {}
 
43
            
 
44
            AssocVectorCompare(const C& src) : C(src)
 
45
            {}
 
46
            
 
47
            bool operator()(const first_argument_type& lhs, 
 
48
                const first_argument_type& rhs) const
 
49
            { return C::operator()(lhs, rhs); }
 
50
            
 
51
            bool operator()(const Data& lhs, const Data& rhs) const
 
52
            { return operator()(lhs.first, rhs.first); }
 
53
            
 
54
            bool operator()(const Data& lhs, 
 
55
                const first_argument_type& rhs) const
 
56
            { return operator()(lhs.first, rhs); }
 
57
            
 
58
            bool operator()(const first_argument_type& lhs,
 
59
                const Data& rhs) const
 
60
            { return operator()(lhs, rhs.first); }
 
61
        };
 
62
    }
 
63
 
 
64
////////////////////////////////////////////////////////////////////////////////
 
65
// class template AssocVector
 
66
// An associative vector built as a syntactic drop-in replacement for std::map
 
67
// BEWARE: AssocVector doesn't respect all map's guarantees, the most important
 
68
//     being:
 
69
// * iterators are invalidated by insert and erase operations
 
70
// * the complexity of insert/erase is O(N) not O(log N)
 
71
// * value_type is std::pair<K, V> not std::pair<const K, V>
 
72
// * iterators are random
 
73
////////////////////////////////////////////////////////////////////////////////
 
74
 
 
75
    template
 
76
    <
 
77
        class K,
 
78
        class V,
 
79
        class C = std::less<K>,
 
80
        class A = std::allocator< std::pair<K, V> >
 
81
    >
 
82
    class AssocVector 
 
83
        : private std::vector< std::pair<K, V>, A >
 
84
        , private Private::AssocVectorCompare<V, C>
 
85
    {
 
86
        typedef std::vector<std::pair<K, V>, A> Base;
 
87
        typedef Private::AssocVectorCompare<V, C> MyCompare;
 
88
 
 
89
    public:
 
90
        typedef K key_type;
 
91
        typedef V mapped_type;
 
92
        typedef typename Base::value_type value_type;
 
93
 
 
94
        typedef C key_compare;
 
95
        typedef A allocator_type;
 
96
        typedef typename A::reference reference;
 
97
        typedef typename A::const_reference const_reference;
 
98
        typedef typename Base::iterator iterator;
 
99
        typedef typename Base::const_iterator const_iterator;
 
100
        typedef typename Base::size_type size_type;
 
101
        typedef typename Base::difference_type difference_type;
 
102
        typedef typename A::pointer pointer;
 
103
        typedef typename A::const_pointer const_pointer;
 
104
        typedef typename Base::reverse_iterator reverse_iterator;
 
105
        typedef typename Base::const_reverse_iterator const_reverse_iterator;
 
106
 
 
107
        class value_compare
 
108
            : public std::binary_function<value_type, value_type, bool>
 
109
            , private key_compare
 
110
        {
 
111
            friend class AssocVector;
 
112
        
 
113
        protected:
 
114
            value_compare(key_compare pred) : key_compare(pred)
 
115
            {}
 
116
 
 
117
        public:
 
118
            bool operator()(const value_type& lhs, const value_type& rhs) const
 
119
            { return key_compare::operator()(lhs.first, rhs.first); }
 
120
        };
 
121
        
 
122
        // 23.3.1.1 construct/copy/destroy
 
123
 
 
124
        explicit AssocVector(const key_compare& comp = key_compare(), 
 
125
            const A& alloc = A())
 
126
        : Base(alloc), MyCompare(comp)
 
127
        {}
 
128
        
 
129
        template <class InputIterator>
 
130
        AssocVector(InputIterator first, InputIterator last, 
 
131
            const key_compare& comp = key_compare(), 
 
132
            const A& alloc = A())
 
133
        : Base(first, last, alloc), MyCompare(comp)
 
134
        {
 
135
            MyCompare& me = *this;
 
136
            std::sort(begin(), end(), me);
 
137
        }
 
138
        
 
139
        AssocVector& operator=(const AssocVector& rhs)
 
140
        { 
 
141
            AssocVector(rhs).swap(*this); 
 
142
            return *this;
 
143
        }
 
144
 
 
145
        // iterators:
 
146
        // The following are here because MWCW gets 'using' wrong
 
147
        iterator begin() { return Base::begin(); }
 
148
        const_iterator begin() const { return Base::begin(); }
 
149
        iterator end() { return Base::end(); }
 
150
        const_iterator end() const { return Base::end(); }
 
151
        reverse_iterator rbegin() { return Base::rbegin(); }
 
152
        const_reverse_iterator rbegin() const { return Base::rbegin(); }
 
153
        reverse_iterator rend() { return Base::rend(); }
 
154
        const_reverse_iterator rend() const { return Base::rend(); }
 
155
        
 
156
        // capacity:
 
157
        bool empty() const { return Base::empty(); }
 
158
        size_type size() const { return Base::size(); }
 
159
        size_type max_size() { return Base::max_size(); }
 
160
 
 
161
        // 23.3.1.2 element access:
 
162
        mapped_type& operator[](const key_type& key)
 
163
        { return insert(value_type(key, mapped_type())).first->second; }
 
164
 
 
165
        // modifiers:
 
166
        std::pair<iterator, bool> insert(const value_type& val)
 
167
        {
 
168
            bool found(true);
 
169
            iterator i(lower_bound(val.first));
 
170
 
 
171
            if (i == end() || this->operator()(val.first, i->first))
 
172
            {
 
173
                i = Base::insert(i, val);
 
174
                found = false;
 
175
            }
 
176
            return std::make_pair(i, !found);
 
177
        }
 
178
 
 
179
        iterator insert(iterator pos, const value_type& val)
 
180
        {
 
181
            if (pos != end() && this->operator()(*pos, val) &&
 
182
                (pos == end() - 1 ||
 
183
                    !this->operator()(val, pos[1]) &&
 
184
                        this->operator()(pos[1], val)))
 
185
            {
 
186
                return Base::insert(pos, val);
 
187
            }
 
188
            return insert(val).first;
 
189
        }
 
190
       
 
191
        template <class InputIterator>
 
192
        void insert(InputIterator first, InputIterator last)
 
193
        { for (; first != last; ++first) insert(*first); }
 
194
        
 
195
        void erase(iterator pos)
 
196
        { Base::erase(pos); }
 
197
 
 
198
        size_type erase(const key_type& k)
 
199
        {
 
200
            iterator i(find(k));
 
201
            if (i == end()) return 0;
 
202
            erase(i);
 
203
            return 1;
 
204
        }
 
205
 
 
206
        void erase(iterator first, iterator last)
 
207
        { Base::erase(first, last); }
 
208
 
 
209
        void swap(AssocVector& other)
 
210
        {
 
211
            using std::swap;
 
212
            Base::swap(other);
 
213
            MyCompare& me = *this;
 
214
            MyCompare& rhs = other;
 
215
            swap(me, rhs);
 
216
        }
 
217
        
 
218
        void clear()
 
219
        { Base::clear(); }
 
220
 
 
221
        // observers:
 
222
        key_compare key_comp() const
 
223
        { return *this; }
 
224
 
 
225
        value_compare value_comp() const
 
226
        {
 
227
            const key_compare& comp = *this;
 
228
            return value_compare(comp);
 
229
        }
 
230
 
 
231
        // 23.3.1.3 map operations:
 
232
        iterator find(const key_type& k)
 
233
        {
 
234
            iterator i(lower_bound(k));
 
235
            if (i != end() && this->operator()(k, i->first))
 
236
            {
 
237
                i = end();
 
238
            }
 
239
            return i;
 
240
        }
 
241
 
 
242
        const_iterator find(const key_type& k) const
 
243
        {       
 
244
            const_iterator i(lower_bound(k));
 
245
            if (i != end() && this->operator()(k, i->first))
 
246
            {
 
247
                i = end();
 
248
            }
 
249
            return i;
 
250
        }
 
251
 
 
252
        size_type count(const key_type& k) const
 
253
        { return find(k) != end(); }
 
254
 
 
255
        iterator lower_bound(const key_type& k)
 
256
        {
 
257
            MyCompare& me = *this;
 
258
            return std::lower_bound(begin(), end(), k, me);
 
259
        }
 
260
 
 
261
        const_iterator lower_bound(const key_type& k) const
 
262
        {
 
263
            const MyCompare& me = *this;
 
264
            return std::lower_bound(begin(), end(), k, me);
 
265
        }
 
266
 
 
267
        iterator upper_bound(const key_type& k)
 
268
        {
 
269
            MyCompare& me = *this;
 
270
            return std::upper_bound(begin(), end(), k, me);
 
271
        }
 
272
 
 
273
        const_iterator upper_bound(const key_type& k) const
 
274
        {
 
275
            const MyCompare& me = *this;
 
276
            return std::upper_bound(begin(), end(), k, me);
 
277
        }
 
278
 
 
279
        std::pair<iterator, iterator> equal_range(const key_type& k)
 
280
        {
 
281
            MyCompare& me = *this;
 
282
            return std::equal_range(begin(), end(), k, me);
 
283
        }
 
284
 
 
285
        std::pair<const_iterator, const_iterator> equal_range(
 
286
            const key_type& k) const
 
287
        {
 
288
            const MyCompare& me = *this;
 
289
            return std::equal_range(begin(), end(), k, me);
 
290
        }
 
291
        
 
292
        friend bool operator==(const AssocVector& lhs, const AssocVector& rhs)
 
293
        {
 
294
            const Base& me = lhs;
 
295
            return me == rhs;
 
296
        } 
 
297
 
 
298
        bool operator<(const AssocVector& rhs) const
 
299
        {
 
300
            const Base& me = *this;
 
301
            const Base& yo = rhs;
 
302
            return me < yo;
 
303
        } 
 
304
 
 
305
        friend bool operator!=(const AssocVector& lhs, const AssocVector& rhs)
 
306
        { return !(lhs == rhs); } 
 
307
 
 
308
        friend bool operator>(const AssocVector& lhs, const AssocVector& rhs)
 
309
        { return rhs < lhs; }
 
310
 
 
311
        friend bool operator>=(const AssocVector& lhs, const AssocVector& rhs)
 
312
        { return !(lhs < rhs); } 
 
313
 
 
314
        friend bool operator<=(const AssocVector& lhs, const AssocVector& rhs)
 
315
        { return !(rhs < lhs); }
 
316
    };
 
317
 
 
318
    // specialized algorithms:
 
319
    template <class K, class V, class C, class A>
 
320
    void swap(AssocVector<K, V, C, A>& lhs, AssocVector<K, V, C, A>& rhs)
 
321
    { lhs.swap(rhs); }
 
322
    
 
323
} // namespace Loki
 
324
 
 
325
////////////////////////////////////////////////////////////////////////////////
 
326
// Change log:
 
327
// May 20,     2001: change operator= - credit due to Cristoph Koegl
 
328
// June 11,    2001: remove paren in equal_range - credit due to Cristoph Koegl
 
329
// June 20,    2001: ported by Nick Thurn to gcc 2.95.3. Kudos, Nick!!!
 
330
// January 22, 2002: fixed operator= - credit due to Tom Hyer
 
331
// June 25,    2002: fixed template insert() - credit due to Robert Minsk
 
332
// June 27,    2002: fixed member swap() - credit due to David Brookman
 
333
// February 2, 2003: fixed dependent names - credit due to Rani Sharoni
 
334
////////////////////////////////////////////////////////////////////////////////
 
335
 
 
336
#endif // ASSOCVECTOR_INC_