_map.h revision e46c9386c4f79aa40185f79a19fc5b2a7ef528b3 
1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
23 *
24 */
25
26/* NOTE: This is an internal header file, included by other STL headers.
27 *   You should not attempt to use it directly.
28 */
29
30#ifndef _STLP_INTERNAL_MAP_H
31#define _STLP_INTERNAL_MAP_H
32
33#ifndef _STLP_INTERNAL_TREE_H
34#  include <stl/_tree.h>
35#endif
36
37_STLP_BEGIN_NAMESPACE
38
39//Specific iterator traits creation
40_STLP_CREATE_ITERATOR_TRAITS(MapTraitsT, traits)
41
42template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
43          _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
44class map
45#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
46          : public __stlport_class<map<_Key, _Tp, _Compare, _Alloc> >
47#endif
48{
49  typedef map<_Key, _Tp, _Compare, _Alloc> _Self;
50public:
51
52// typedefs:
53
54  typedef _Key                  key_type;
55  typedef _Tp                   data_type;
56  typedef _Tp                   mapped_type;
57  typedef pair<_STLP_CONST _Key, _Tp> value_type;
58  typedef _Compare              key_compare;
59
60  class value_compare
61    : public binary_function<value_type, value_type, bool> {
62  friend class map<_Key,_Tp,_Compare,_Alloc>;
63  protected :
64    //c is a Standard name (23.3.1), do no make it STLport naming convention compliant.
65    _Compare comp;
66    value_compare(_Compare __c) : comp(__c) {}
67  public:
68    bool operator()(const value_type& __x, const value_type& __y) const
69    { return comp(__x.first, __y.first); }
70  };
71
72protected:
73  typedef _STLP_PRIV _MapTraitsT<value_type> _MapTraits;
74
75public:
76  //Following typedef have to be public for __move_traits specialization.
77  typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
78                              value_type, _STLP_SELECT1ST(value_type, _Key),
79                              _MapTraits, _Alloc> _Rep_type;
80
81  typedef typename _Rep_type::pointer pointer;
82  typedef typename _Rep_type::const_pointer const_pointer;
83  typedef typename _Rep_type::reference reference;
84  typedef typename _Rep_type::const_reference const_reference;
85  typedef typename _Rep_type::iterator iterator;
86  typedef typename _Rep_type::const_iterator const_iterator;
87  typedef typename _Rep_type::reverse_iterator reverse_iterator;
88  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
89  typedef typename _Rep_type::size_type size_type;
90  typedef typename _Rep_type::difference_type difference_type;
91  typedef typename _Rep_type::allocator_type allocator_type;
92
93private:
94  _Rep_type _M_t;  // red-black tree representing map
95  _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
96
97public:
98  // allocation/deallocation
99  map() : _M_t(_Compare(), allocator_type()) {}
100#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
101  explicit map(const _Compare& __comp,
102               const allocator_type& __a = allocator_type())
103#else
104  explicit map(const _Compare& __comp)
105    : _M_t(__comp, allocator_type()) {}
106  explicit map(const _Compare& __comp, const allocator_type& __a)
107#endif
108    : _M_t(__comp, __a) {}
109
110#if defined (_STLP_MEMBER_TEMPLATES)
111  template <class _InputIterator>
112  map(_InputIterator __first, _InputIterator __last)
113    : _M_t(_Compare(), allocator_type())
114    { _M_t.insert_unique(__first, __last); }
115
116  template <class _InputIterator>
117  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp,
118      const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
119    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
120
121#  if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
122  template <class _InputIterator>
123  map(_InputIterator __first, _InputIterator __last, const _Compare& __comp)
124    : _M_t(__comp, allocator_type()) { _M_t.insert_unique(__first, __last); }
125#  endif
126
127#else
128  map(const value_type* __first, const value_type* __last)
129    : _M_t(_Compare(), allocator_type())
130    { _M_t.insert_unique(__first, __last); }
131
132  map(const value_type* __first,
133      const value_type* __last, const _Compare& __comp,
134      const allocator_type& __a = allocator_type())
135    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
136
137  map(const_iterator __first, const_iterator __last)
138    : _M_t(_Compare(), allocator_type())
139    { _M_t.insert_unique(__first, __last); }
140
141  map(const_iterator __first, const_iterator __last, const _Compare& __comp,
142      const allocator_type& __a = allocator_type())
143    : _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
144#endif /* _STLP_MEMBER_TEMPLATES */
145
146  map(const _Self& __x) : _M_t(__x._M_t) {}
147
148#if !defined (_STLP_NO_MOVE_SEMANTIC)
149  map(__move_source<_Self> src)
150    : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
151#endif
152
153  _Self& operator=(const _Self& __x) {
154    _M_t = __x._M_t;
155    return *this;
156  }
157
158  // accessors:
159  key_compare key_comp() const { return _M_t.key_comp(); }
160  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
161  allocator_type get_allocator() const { return _M_t.get_allocator(); }
162
163  iterator begin() { return _M_t.begin(); }
164  const_iterator begin() const { return _M_t.begin(); }
165  iterator end() { return _M_t.end(); }
166  const_iterator end() const { return _M_t.end(); }
167  reverse_iterator rbegin() { return _M_t.rbegin(); }
168  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
169  reverse_iterator rend() { return _M_t.rend(); }
170  const_reverse_iterator rend() const { return _M_t.rend(); }
171  bool empty() const { return _M_t.empty(); }
172  size_type size() const { return _M_t.size(); }
173  size_type max_size() const { return _M_t.max_size(); }
174  _STLP_TEMPLATE_FOR_CONT_EXT
175  _Tp& operator[](const _KT& __k) {
176    iterator __i = lower_bound(__k);
177    // __i->first is greater than or equivalent to __k.
178    if (__i == end() || key_comp()(__k, (*__i).first))
179      __i = insert(__i, value_type(__k, _STLP_DEFAULT_CONSTRUCTED(_Tp)));
180    return (*__i).second;
181  }
182  void swap(_Self& __x) { _M_t.swap(__x._M_t); }
183#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
184  void _M_swap_workaround(_Self& __x) { swap(__x); }
185#endif
186
187  // insert/erase
188  pair<iterator,bool> insert(const value_type& __x)
189  { return _M_t.insert_unique(__x); }
190  iterator insert(iterator __pos, const value_type& __x)
191  { return _M_t.insert_unique(__pos, __x); }
192#ifdef _STLP_MEMBER_TEMPLATES
193  template <class _InputIterator>
194  void insert(_InputIterator __first, _InputIterator __last)
195  { _M_t.insert_unique(__first, __last); }
196#else
197  void insert(const value_type* __first, const value_type* __last)
198  { _M_t.insert_unique(__first, __last); }
199  void insert(const_iterator __first, const_iterator __last)
200  { _M_t.insert_unique(__first, __last); }
201#endif /* _STLP_MEMBER_TEMPLATES */
202
203  void erase(iterator __pos) { _M_t.erase(__pos); }
204  size_type erase(const key_type& __x) { return _M_t.erase_unique(__x); }
205  void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
206  void clear() { _M_t.clear(); }
207
208  // map operations:
209  _STLP_TEMPLATE_FOR_CONT_EXT
210  iterator find(const _KT& __x) { return _M_t.find(__x); }
211  _STLP_TEMPLATE_FOR_CONT_EXT
212  const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
213  _STLP_TEMPLATE_FOR_CONT_EXT
214  size_type count(const _KT& __x) const { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }
215  _STLP_TEMPLATE_FOR_CONT_EXT
216  iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
217  _STLP_TEMPLATE_FOR_CONT_EXT
218  const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
219  _STLP_TEMPLATE_FOR_CONT_EXT
220  iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
221  _STLP_TEMPLATE_FOR_CONT_EXT
222  const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
223
224  _STLP_TEMPLATE_FOR_CONT_EXT
225  pair<iterator,iterator> equal_range(const _KT& __x)
226  { return _M_t.equal_range_unique(__x); }
227  _STLP_TEMPLATE_FOR_CONT_EXT
228  pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
229  { return _M_t.equal_range_unique(__x); }
230};
231
232//Specific iterator traits creation
233_STLP_CREATE_ITERATOR_TRAITS(MultimapTraitsT, traits)
234
235template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_Compare, less<_Key> ),
236          _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
237class multimap
238#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
239               : public __stlport_class<multimap<_Key, _Tp, _Compare, _Alloc> >
240#endif
241{
242  typedef multimap<_Key, _Tp, _Compare, _Alloc> _Self;
243public:
244
245// typedefs:
246
247  typedef _Key                  key_type;
248  typedef _Tp                   data_type;
249  typedef _Tp                   mapped_type;
250  typedef pair<_STLP_CONST _Key, _Tp> value_type;
251  typedef _Compare              key_compare;
252
253  class value_compare : public binary_function<value_type, value_type, bool> {
254    friend class multimap<_Key,_Tp,_Compare,_Alloc>;
255  protected:
256    //comp is a Standard name (23.3.2), do no make it STLport naming convention compliant.
257    _Compare comp;
258    value_compare(_Compare __c) : comp(__c) {}
259  public:
260    bool operator()(const value_type& __x, const value_type& __y) const
261    { return comp(__x.first, __y.first); }
262  };
263
264protected:
265  //Specific iterator traits creation
266  typedef _STLP_PRIV _MultimapTraitsT<value_type> _MultimapTraits;
267
268public:
269  //Following typedef have to be public for __move_traits specialization.
270  typedef _STLP_PRIV _Rb_tree<key_type, key_compare,
271                              value_type, _STLP_SELECT1ST(value_type, _Key),
272                              _MultimapTraits, _Alloc> _Rep_type;
273
274  typedef typename _Rep_type::pointer pointer;
275  typedef typename _Rep_type::const_pointer const_pointer;
276  typedef typename _Rep_type::reference reference;
277  typedef typename _Rep_type::const_reference const_reference;
278  typedef typename _Rep_type::iterator iterator;
279  typedef typename _Rep_type::const_iterator const_iterator;
280  typedef typename _Rep_type::reverse_iterator reverse_iterator;
281  typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
282  typedef typename _Rep_type::size_type size_type;
283  typedef typename _Rep_type::difference_type difference_type;
284  typedef typename _Rep_type::allocator_type allocator_type;
285
286private:
287  _Rep_type _M_t;  // red-black tree representing multimap
288  _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
289
290public:
291  // allocation/deallocation
292  multimap() : _M_t(_Compare(), allocator_type()) { }
293  explicit multimap(const _Compare& __comp,
294                    const allocator_type& __a = allocator_type())
295    : _M_t(__comp, __a) { }
296
297#ifdef _STLP_MEMBER_TEMPLATES
298  template <class _InputIterator>
299  multimap(_InputIterator __first, _InputIterator __last)
300    : _M_t(_Compare(), allocator_type())
301    { _M_t.insert_equal(__first, __last); }
302# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
303  template <class _InputIterator>
304  multimap(_InputIterator __first, _InputIterator __last,
305           const _Compare& __comp)
306    : _M_t(__comp, allocator_type()) { _M_t.insert_equal(__first, __last); }
307#  endif
308  template <class _InputIterator>
309  multimap(_InputIterator __first, _InputIterator __last,
310           const _Compare& __comp,
311           const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
312    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
313#else
314  multimap(const value_type* __first, const value_type* __last)
315    : _M_t(_Compare(), allocator_type())
316    { _M_t.insert_equal(__first, __last); }
317  multimap(const value_type* __first, const value_type* __last,
318           const _Compare& __comp,
319           const allocator_type& __a = allocator_type())
320    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
321
322  multimap(const_iterator __first, const_iterator __last)
323    : _M_t(_Compare(), allocator_type())
324    { _M_t.insert_equal(__first, __last); }
325  multimap(const_iterator __first, const_iterator __last,
326           const _Compare& __comp,
327           const allocator_type& __a = allocator_type())
328    : _M_t(__comp, __a) { _M_t.insert_equal(__first, __last); }
329#endif /* _STLP_MEMBER_TEMPLATES */
330
331  multimap(const _Self& __x) : _M_t(__x._M_t) {}
332
333#if !defined (_STLP_NO_MOVE_SEMANTIC)
334  multimap(__move_source<_Self> src)
335    : _M_t(__move_source<_Rep_type>(src.get()._M_t)) {}
336#endif
337
338  _Self& operator=(const _Self& __x) {
339    _M_t = __x._M_t;
340    return *this;
341  }
342
343  // accessors:
344
345  key_compare key_comp() const { return _M_t.key_comp(); }
346  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
347  allocator_type get_allocator() const { return _M_t.get_allocator(); }
348
349  iterator begin() { return _M_t.begin(); }
350  const_iterator begin() const { return _M_t.begin(); }
351  iterator end() { return _M_t.end(); }
352  const_iterator end() const { return _M_t.end(); }
353  reverse_iterator rbegin() { return _M_t.rbegin(); }
354  const_reverse_iterator rbegin() const { return _M_t.rbegin(); }
355  reverse_iterator rend() { return _M_t.rend(); }
356  const_reverse_iterator rend() const { return _M_t.rend(); }
357  bool empty() const { return _M_t.empty(); }
358  size_type size() const { return _M_t.size(); }
359  size_type max_size() const { return _M_t.max_size(); }
360  void swap(_Self& __x) { _M_t.swap(__x._M_t); }
361#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
362  void _M_swap_workaround(_Self& __x) { swap(__x); }
363#endif
364
365  // insert/erase
366  iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
367  iterator insert(iterator __pos, const value_type& __x) { return _M_t.insert_equal(__pos, __x); }
368#if defined (_STLP_MEMBER_TEMPLATES)
369  template <class _InputIterator>
370  void insert(_InputIterator __first, _InputIterator __last)
371  { _M_t.insert_equal(__first, __last); }
372#else
373  void insert(const value_type* __first, const value_type* __last)
374  { _M_t.insert_equal(__first, __last); }
375  void insert(const_iterator __first, const_iterator __last)
376  { _M_t.insert_equal(__first, __last); }
377#endif /* _STLP_MEMBER_TEMPLATES */
378  void erase(iterator __pos) { _M_t.erase(__pos); }
379  size_type erase(const key_type& __x) { return _M_t.erase(__x); }
380  void erase(iterator __first, iterator __last) { _M_t.erase(__first, __last); }
381  void clear() { _M_t.clear(); }
382
383  // multimap operations:
384
385  _STLP_TEMPLATE_FOR_CONT_EXT
386  iterator find(const _KT& __x) { return _M_t.find(__x); }
387  _STLP_TEMPLATE_FOR_CONT_EXT
388  const_iterator find(const _KT& __x) const { return _M_t.find(__x); }
389  _STLP_TEMPLATE_FOR_CONT_EXT
390  size_type count(const _KT& __x) const { return _M_t.count(__x); }
391  _STLP_TEMPLATE_FOR_CONT_EXT
392  iterator lower_bound(const _KT& __x) { return _M_t.lower_bound(__x); }
393  _STLP_TEMPLATE_FOR_CONT_EXT
394  const_iterator lower_bound(const _KT& __x) const { return _M_t.lower_bound(__x); }
395  _STLP_TEMPLATE_FOR_CONT_EXT
396  iterator upper_bound(const _KT& __x) { return _M_t.upper_bound(__x); }
397  _STLP_TEMPLATE_FOR_CONT_EXT
398  const_iterator upper_bound(const _KT& __x) const { return _M_t.upper_bound(__x); }
399  _STLP_TEMPLATE_FOR_CONT_EXT
400  pair<iterator,iterator> equal_range(const _KT& __x)
401  { return _M_t.equal_range(__x); }
402  _STLP_TEMPLATE_FOR_CONT_EXT
403  pair<const_iterator,const_iterator> equal_range(const _KT& __x) const
404  { return _M_t.equal_range(__x); }
405};
406
407#define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _Compare, class _Alloc>
408#define _STLP_TEMPLATE_CONTAINER map<_Key,_Tp,_Compare,_Alloc>
409#include <stl/_relops_cont.h>
410#undef  _STLP_TEMPLATE_CONTAINER
411#define _STLP_TEMPLATE_CONTAINER multimap<_Key,_Tp,_Compare,_Alloc>
412#include <stl/_relops_cont.h>
413#undef  _STLP_TEMPLATE_CONTAINER
414#undef  _STLP_TEMPLATE_HEADER
415
416#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
417template <class _Key, class _Tp, class _Compare, class _Alloc>
418struct __move_traits<map<_Key,_Tp,_Compare,_Alloc> > :
419  _STLP_PRIV __move_traits_aux<typename map<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
420{};
421
422template <class _Key, class _Tp, class _Compare, class _Alloc>
423struct __move_traits<multimap<_Key,_Tp,_Compare,_Alloc> > :
424  _STLP_PRIV __move_traits_aux<typename multimap<_Key,_Tp,_Compare,_Alloc>::_Rep_type>
425{};
426#endif
427
428_STLP_END_NAMESPACE
429
430#endif /* _STLP_INTERNAL_MAP_H */
431
432// Local Variables:
433// mode:C++
434// End:
435
436