source: trunk/yat/utility/stl_utility.h @ 3404

Last change on this file since 3404 was 3404, checked in by Peter, 4 years ago

new function to reduce capacity in a vector

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 24.1 KB
Line 
1#ifndef _theplu_yat_utility_stl_utility_
2#define _theplu_yat_utility_stl_utility_
3
4// $Id: stl_utility.h 3404 2015-04-03 07:36:12Z peter $
5
6/*
7  Copyright (C) 2004 Jari Häkkinen
8  Copyright (C) 2005 Jari Häkkinen, Peter Johansson, Markus Ringnér
9  Copyright (C) 2006 Jari Häkkinen
10  Copyright (C) 2007, 2008 Jari Häkkinen, Peter Johansson
11  Copyright (C) 2009, 2010, 2011, 2012, 2013, 2014 Peter Johansson
12
13  This file is part of the yat library, http://dev.thep.lu.se/yat
14
15  The yat library is free software; you can redistribute it and/or
16  modify it under the terms of the GNU General Public License as
17  published by the Free Software Foundation; either version 3 of the
18  License, or (at your option) any later version.
19
20  The yat library is distributed in the hope that it will be useful,
21  but WITHOUT ANY WARRANTY; without even the implied warranty of
22  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23  General Public License for more details.
24
25  You should have received a copy of the GNU General Public License
26  along with yat. If not, see <http://www.gnu.org/licenses/>.
27*/
28
29///
30/// \file stl_utility.h
31///
32/// There are a number of useful functionality missing in the Standard
33/// Template Library, STL. This file is an effort to provide
34/// extensions to STL functionality.
35///
36
37#include "concept_check.h"
38#include "DataWeight.h"
39#include "Exception.h"
40
41#include <boost/concept_check.hpp>
42#include <boost/iterator/transform_iterator.hpp>
43#include <boost/mpl/if.hpp>
44#include <boost/type_traits/add_const.hpp>
45#include <boost/type_traits/is_const.hpp>
46#include <boost/type_traits/remove_reference.hpp>
47
48#include <algorithm>
49#include <cmath>
50#include <exception>
51#include <functional>
52#include <iterator>
53#include <map>
54#include <ostream>
55#include <sstream>
56#include <string>
57#include <utility>
58#include <vector>
59
60// We are intruding standard namespace, which might cause
61// conflicts. Let the user turn off these declarations by defining
62// YAT_STD_DISABE
63#ifndef YAT_STD_DISABLE
64namespace std {
65
66  ///
67  /// Print out a pair
68  ///
69  // This is in namespace std because we have not figured out how to have
70  // pair and its operator<< in different namespaces
71  template <class T1, class T2>
72  std::ostream& operator<<(std::ostream& out, const std::pair<T1,T2>& p)
73  { out << p.first << "\t" << p.second; return out; }
74
75}
76#endif
77
78namespace theplu {
79namespace yat {
80namespace utility {
81
82  /**
83     Functor class taking absolute value
84  */
85  template<typename T>
86  struct abs : std::unary_function<T, T>
87  {
88    /**
89       \return absolute value
90     */
91    inline T operator()(T x) const
92    { return std::abs(x); }
93  };
94
95
96  /**
97     \brief Adaptor between pointer and pointee interface
98
99     Functor takes a pointer and returns a reference to the instance
100     pointer is pointing to. Return type is decided by <a
101     href=http://www.sgi.com/tech/stl/iterator_traits.html>
102     std::iterator_traits<Pointer>::reference </a>. Pointer must have
103     an \c operator*, i.e., \c Pointer can be a traditional pointer or
104     an \input_iterator.
105
106     The class is designed to be used with boost::transform_iterator
107
108     \code
109     std::vector<MyClass*> vec;
110     ...
111     Dereferencer<MyClass*> dereferencer;
112     std::set<MyClass> s;
113     s.insert(boost::make_transform_iterator(vec.begin(), dereferencer),
114              boost::make_transform_iterator(vec.end(), dereferencer))
115     \endcode
116
117     where elements in vec<MyClass*> are copied in to set<MyClass>.
118
119     \since New in yat 0.7
120   */
121  template<typename Pointer>
122  struct Dereferencer :
123    public std::unary_function<Pointer,
124                               typename std::iterator_traits<Pointer>::reference>
125  {
126    /**
127       \brief constructor
128     */
129    Dereferencer(void)
130    { BOOST_CONCEPT_ASSERT((TrivialIterator<Pointer>)); }
131
132    /**
133       \return * \a ti
134     */
135    typename std::iterator_traits<Pointer>::reference
136    operator()(Pointer ti) const { return *ti; }
137  };
138
139
140  /**
141     See The C++ Standard Library - A Tutorial and Reference by
142     Nicolai M. Josuttis
143
144     If f is a binary functor, both g and h are unary functors, and
145     return type of g (and h) is convertible to F's argument type,
146     then compose_f_gx_hy can be used to create a functor equivalent
147     to \f$ f(g(x), h(y)) \f$
148
149     - F must be an <a
150     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
151     AdaptableBinaryFunction</a>
152     - G must be an <a
153     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
154     AdaptableUnaryFunction</a>
155     - H must be an <a
156     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
157     AdaptableUnaryFunction</a>
158     - \c G::result_type is convertible to \c F::first_argument_type
159     - \c H::result_type is convertible to \c F::second_argument_type
160
161     \see compose_f_gxy, compose_f_gx, and compose_f_gx_hx
162   */
163  template<class F, class G, class H>
164  class compose_f_gx_hy :
165    public std::binary_function<typename G::argument_type,
166                                typename H::argument_type,
167                                typename F::result_type>
168  {
169  public:
170    /**
171       \brief default constructor
172
173       Requires that F, G, and H have default constructors
174    */
175    compose_f_gx_hy(void) {}
176
177    /**
178       \brief Constructor
179     */
180    compose_f_gx_hy(F f, G g, H h)
181      : f_(f), g_(g), h_(h)
182    {
183    }
184
185    /**
186       \brief Does the work
187     */
188    typename F::result_type operator()(typename G::argument_type x,
189                                       typename H::argument_type y) const
190    {
191      return f_(g_(x), h_(y));
192    }
193
194  private:
195    F f_;
196    G g_;
197    H h_;
198  };
199
200  /**
201     Convenient function to create a compose_f_gx_hy.
202
203     \relates compose_f_gx_hy
204
205     \see std::make_pair
206  */
207  template<class F, class G, class H>
208  compose_f_gx_hy<F, G, H> make_compose_f_gx_hy(F f, G g, H h)
209  {
210    return compose_f_gx_hy<F,G,H>(f,g,h);
211  }
212
213
214  /**
215     See The C++ Standard Library - A Tutorial and Reference by
216     Nicolai M. Josuttis
217
218     If f is a unary functor, g is a binary functor, and return type
219     of g is convertible to F's argument type, then
220     compose_f_gxy can be used to create a functor equivalent to
221     \f$ f(g(x,y)) \f$
222
223     - F must be an <a
224     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
225     AdaptableUnaryFunction</a>
226     - G must be an <a
227     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
228     AdaptableBinaryFunction</a>
229     - \c G::result_type is convertible to \c F::argument_type
230
231     \see compose_f_gx_hy, compose_f_gx, and compose_f_gx_hx
232
233     \since New in yat 0.7
234   */
235  template<class F, class G>
236  class compose_f_gxy :
237    public std::binary_function<typename G::first_argument_type,
238                                typename G::second_argument_type,
239                                typename F::result_type>
240  {
241  public:
242    /**
243       \brief default constructor
244
245       Requires that F, G, and H have default constructors
246    */
247    compose_f_gxy(void) {}
248
249    /**
250       \brief Constructor
251     */
252    compose_f_gxy(F f, G g)
253      : f_(f), g_(g)
254    {
255    }
256
257    /**
258       \brief Does the work
259     */
260    typename F::result_type
261    operator()(typename G::first_argument_type x,
262               typename G::second_argument_type y) const
263    {
264      return f_(g_(x,y));
265    }
266
267  private:
268    F f_;
269    G g_;
270  };
271
272  /**
273     Convenient function to create a compose_f_gxy.
274
275     \relates compose_f_gxy
276
277     \see std::make_pair
278
279     \since New in yat 0.7
280  */
281  template<class F, class G>
282  compose_f_gxy<F, G> make_compose_f_gxy(F f, G g)
283  {
284    return compose_f_gxy<F,G>(f,g);
285  }
286
287
288  /**
289     See The C++ Standard Library - A Tutorial and Reference by
290     Nicolai M. Josuttis
291
292     If f is a unary functor, g is a unary functor, and return type of
293     g is convertible to F's argument type, then compose_f_gx can be
294     used to create a functor equivalent to \f$ f(g(x)) \f$
295
296     - F must be an <a
297     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
298     AdaptableBinaryFunction</a>
299     - G must be an <a
300     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
301     AdaptableUnaryFunction</a>
302     - \c G::result_type is convertible to \c F::argument_type
303
304     \see compose_f_gx_hy, compose_f_gxy, and compose_f_gx_hx
305
306     \see <a href="http://www.sgi.com/tech/stl/unary_compose.html">
307     unary_compose</a> (SGI extension)
308
309     \since New in yat 0.7
310   */
311  template<class F, class G>
312  class compose_f_gx : public std::unary_function<typename G::argument_type,
313                                                  typename F::result_type>
314  {
315  public:
316    /**
317       \brief default constructor
318
319       Requires that F and G have default constructors
320    */
321    compose_f_gx(void) {}
322
323    /**
324       \brief Constructor
325     */
326    compose_f_gx(F f, G g)
327      : f_(f), g_(g)
328    {
329    }
330
331    /**
332       \brief Does the work
333     */
334    typename F::result_type
335    operator()(typename G::argument_type x) const
336    {
337      return f_(g_(x));
338    }
339
340  private:
341    F f_;
342    G g_;
343  };
344
345  /**
346     Convenient function to create a compose_f_gx.
347
348     \relates compose_f_gx
349
350     \see std::make_pair
351
352     \since New in yat 0.7
353  */
354  template<class F, class G>
355  compose_f_gx<F, G> make_compose_f_gx(F f, G g)
356  {
357    return compose_f_gx<F,G>(f,g);
358  }
359
360
361  /**
362     If f is a binary functor, g and h a unary functors, return
363     type of g is convertible to F's first argument type, and return
364     type of h is convertible to F's second argument type, then
365     compose_f_gx_hx can be used to create a functor equivalent to \f$
366     f(g(x), h(x)) \f$
367
368     - F must be an <a
369     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
370     AdaptableBinaryFunction</a>
371     - G must be an <a
372     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
373     AdaptableUnaryFunction</a>
374     - H must be an <a
375     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
376     AdaptableUnaryFunction</a>
377     - \c G::result_type is convertible to \c F::first_argument_type
378     - \c H::result_type is convertible to \c F::second_argument_type
379
380     \see compose_f_gx_hy, compose_f_gxy, and compose_f_gx
381
382     \see <a href="http://www.sgi.com/tech/stl/binary_compose.html">
383     binary_compose</a> (SGI extension)
384
385     \since New in yat 0.11
386   */
387  template<class F, class G, class H>
388  class compose_f_gx_hx : public std::unary_function<typename G::argument_type,
389                                                     typename F::result_type>
390  {
391  public:
392    /**
393       \brief default constructor
394
395       Requires that F, G, and H have default constructors
396    */
397    compose_f_gx_hx(void) {}
398
399    /**
400       \brief Constructor
401     */
402    compose_f_gx_hx(F f, G g, H h)
403      : f_(f), g_(g), h_(h)
404    {
405    }
406
407    /**
408       \brief Does the work
409     */
410    typename F::result_type operator()(typename G::argument_type x) const
411    {
412      return f_(g_(x), h_(x));
413    }
414
415  private:
416    F f_;
417    G g_;
418    H h_;
419  };
420
421  /**
422     Convenient function to create a compose_f_gx_hx.
423
424     \relates compose_f_gx_hx
425
426     \see std::make_pair
427
428     \since New in yat 0.11
429  */
430  template<class F, class G, class H>
431  compose_f_gx_hx<F, G, H> make_compose_f_gx_hx(F f, G g, H h)
432  {
433    return compose_f_gx_hx<F,G,H>(f,g,h);
434  }
435
436
437  /**
438     Functor class to exponentiate values using std::exp
439
440     T should be either \c float, \c double, or \c long \c double
441
442     \since New in yat 0.5
443  */
444  template<typename T>
445  struct Exp : std::unary_function<T, T>
446  {
447    /**
448       \return exponentiated value
449     */
450    inline T operator()(T x) const
451    { return std::exp(x); }
452  };
453
454  /**
455     \brief Identity functor that returns its argument
456
457     \since New in yat 0.7
458   */
459  template<typename T>
460  struct Identity : public std::unary_function<T, T>
461  {
462    /// \return \a arg
463    T operator()(T arg) const { return arg; }
464  };
465
466
467  /**
468     \brief reduce size and capacity to zero
469
470     The standard provides a member function clear(void), which clears
471     the contents of the vector i.e. sets the size to zero. However,
472     the member function might leave the capacity unchanged and
473     sometimes, when it's desiribale to save memory usage e.g., it
474     preferable to use this function, which reduces the capacity to zero.
475
476     \since new in yat 0.13
477   */
478  template<typename T>
479  void clear(std::vector<T>& vec)
480  {
481    std::vector<T> other;
482    vec.swap(other);
483  }
484
485
486  /**
487     Same functionality as map::operator[] but the function does not
488     modify the map and the function throws if key does not exist in
489     the map.
490
491     Type Requirment:
492     - \a Key2 is convertible to Key
493
494     \return const reference to m[k]
495
496     \throw get_error if key \a k does not exist in map \a m
497
498     \since New in yat 0.7
499   */
500  template <typename Key, typename Tp, typename Compare, typename Alloc,
501            typename Key2>
502  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key2& k);
503
504  /**
505     \brief error class used in
506     get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k)
507
508     \since yat 0.13
509   */
510  template<typename Key>
511  class get_error : public runtime_error
512  {
513  public:
514    /// \brief constructor
515    get_error(const std::string& msg, const Key& key)
516      : runtime_error(msg), key_(key) {}
517    /// \brief destructor
518    virtual ~get_error(void) throw () {}
519    /// access the key object
520    const Key& key(void) const { return key_; }
521  private:
522    Key key_;
523  };
524
525  /**
526     Creating a map from a range [first, last) such that m[key]
527     returns a vector with indices of which element in [first, last)
528     that is equal to \a key, or more technically: m[element].size()
529     returns number of elements equal to \a element, and
530     m[*element][i] = distance(first, element) for every \a element in
531     [first, last) and \a i smaller than m[element].size().
532
533     Requirement: InputIterator's value type is assignable to Key
534
535     \since New in yat 0.5
536   */
537  template<typename InputIterator, typename Key, typename Comp>
538  void inverse(InputIterator first, InputIterator last,
539               std::map<Key, std::vector<size_t>, Comp >& m)
540  {
541    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
542    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
543    m.clear();
544    for (size_t i=0; first!=last; ++i, ++first)
545      m[*first].push_back(i);
546  }
547
548  /**
549     In the created multimap each element e will fulfill: \f$ *(first
550     + e->second) == e->first \f$
551
552     Requirement: InputIterator's value type is assignable to Key
553
554     \since New in yat 0.5
555   */
556  template<typename Key, typename InputIterator, typename Comp>
557  void inverse(InputIterator first, InputIterator last,
558               std::multimap<Key, size_t, Comp>& m)
559  {
560    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
561    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
562    m.clear();
563    for (size_t i=0; first!=last; ++i, ++first)
564      m.insert(std::make_pair(*first, i));
565  }
566
567
568  /**
569     Create a map mapping from values in range [first, last) to the
570     distance from first.
571
572     Post-condition: m[first[i]] == i (for all i that correspond to a
573     unique element). For non-unique element behaviour is undefined.
574
575     Requirement: InputIterator's value type is assignable to Key
576
577     \since New in yat 0.10
578   */
579  template<typename InputIterator, typename Key, typename Comp>
580  void inverse(InputIterator first, InputIterator last,
581               std::map<Key, size_t, Comp >& m)
582  {
583    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
584    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
585    m.clear();
586    for (size_t i=0; first!=last; ++i, ++first)
587      m[*first] = i;
588  }
589
590  /**
591     \brief Functor that behaves like std::less with the exception
592     that it treats NaN as a number larger than infinity.
593
594     This functor is useful when sorting ranges with NaNs. The problem
595     with NaNs is that std::less always returns \c false when one of
596     the arguments is NaN. That together with the fact that std::sort
597     only guarantees that an element \c i is never less than previous
598     element \c --i. Therefore {10, NaN, 2} is sorted according to
599     this definition, but most often it is desired that the 2 is
600     located before the 10 in the range. Using this functor, less_nan,
601     this can easily be achieved as std::sort(first, last, less_nan)
602
603     The default implementation uses std::isnan(T), which consequently
604     must be supported.
605
606     There is a specialization less_nan<DataWeight>
607
608     \since New in yat 0.6
609  */
610  template<typename T>
611  struct less_nan : std::binary_function<T, T, bool>
612  {
613    /**
614       \return \c true if x is less than y. NaNs are treated as a number
615       larger than infinity, which implies \c true is returned if y is
616       NaN and x is not.
617     */
618    inline bool operator()(T x, T y) const
619    {
620      if (std::isnan(x))
621        return false;
622      if (std::isnan(y))
623        return true;
624      return x<y;
625    }
626  };
627
628
629  /**
630     \brief Specialization for DataWeight.
631   */
632  template<>
633  struct less_nan<DataWeight>
634    : std::binary_function<DataWeight, DataWeight, bool>
635  {
636    /**
637       \return less_nan<double>(x.data(), y.data())
638     */
639    inline bool operator()(const DataWeight& x, const DataWeight& y) const
640    {
641      less_nan<double> compare;
642      return compare(x.data(), y.data());
643    }
644  };
645
646
647  /**
648     Functor class to take logarithm
649
650     T should be either \c float, \c double, or \c long \c double
651
652     \since New in yat 0.5
653  */
654  template<typename T>
655  class Log : std::unary_function<T, T>
656  {
657  public:
658    /**
659       Default constructor using natural base \f$ e \f$
660     */
661    Log(void)
662      : log_base_(1.0) {}
663
664    /**
665       \param base Taking logarithm in which base, e.g. 2 or 10.
666    */
667    explicit Log(double base) : log_base_(std::log(base)) {}
668
669    /**
670       \return logarithm
671     */
672    inline T operator()(T x) const
673    { return std::log(x)/log_base_; }
674
675  private:
676    double log_base_;
677  };
678
679  /**
680     \return max of values
681   */
682  template <typename T>
683  T max(const T& a, const T& b, const T& c)
684  {
685    return std::max(std::max(a,b),c);
686  }
687
688
689  /**
690     \return max of values
691   */
692  template <typename T>
693  T max(const T& a, const T& b, const T& c, const T& d)
694  {
695    return std::max(std::max(a,b), std::max(c,d));
696  }
697
698
699  /**
700     \return max of values
701   */
702  template <typename T>
703  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
704  {
705    return std::max(max(a,b,c,d), e);
706  }
707
708
709  /**
710     \return max of values
711   */
712  template <typename T>
713  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
714  {
715    return std::max(max(a,b,c,d), std::max(e,f));
716  }
717
718
719  ///
720  /// @brief Functor comparing pairs using second.
721  ///
722  /// STL provides operator< for the pair.first element, but none for
723  /// pair.second. This template provides this and can be used as the
724  /// comparison object in generic functions such as the STL sort.
725  ///
726  template <class T1,class T2>
727  struct pair_value_compare
728  {
729    ///
730    /// @return true if x.second<y.second or (!(y.second<y.second) and
731    /// x.first<y.first)
732    ///
733    inline bool operator()(const std::pair<T1,T2>& x,
734                           const std::pair<T1,T2>& y) {
735      return ((x.second<y.second) ||
736              (!(y.second<x.second) && (x.first<y.first)));
737    }
738  };
739
740  /**
741     \brief Functor that return std::pair.first
742
743     \see pair_first_iterator
744
745     \since New in yat 0.5
746   */
747  template <class Pair>
748  struct PairFirst
749  {
750    /**
751       The type returned is Pair::first_type& with the exception when
752       Pair is const and Pair::first_type is non-const, in which case
753       const Pair::first_type& is return type.
754     */
755    typedef typename boost::mpl::if_<
756                  typename boost::is_const<Pair>::type,
757                  typename boost::add_const<typename Pair::first_type>::type&,
758                  typename Pair::first_type&>::type result_type;
759
760    /**
761       The argument type is Pair&.
762     */
763    typedef Pair& argument_type;
764
765    /**
766       \return p.first
767     */
768    inline result_type operator()(argument_type p) const
769    { return p.first; }
770
771  };
772
773
774  /**
775     \brief Functor that return std::pair.second
776
777     \see pair_second_iterator
778
779     \since New in yat 0.5
780   */
781  template <class Pair>
782  struct PairSecond
783  {
784    /**
785       The type returned is Pair::second_type& with the exception when
786       Pair is const and Pair::second_type is non-const, in which case
787       const Pair::first_type& is return type.
788     */
789    typedef typename boost::mpl::if_<
790                  typename boost::is_const<Pair>::type,
791                  typename boost::add_const<typename Pair::second_type>::type&,
792                  typename Pair::second_type&>::type result_type;
793
794    /**
795       The argument type is Pair&.
796     */
797    typedef Pair& argument_type;
798
799    /**
800       \return p.first
801     */
802    inline result_type operator()(argument_type p) const
803    { return p.second; }
804
805  };
806
807
808  /**
809     Creates a transform_iterator that transforms an iterator with
810     value type std::pair to an iterator with value type
811     std::pair::first_type. This can be used, for example, to
812     communicate between a std::map and std::vector
813
814     \code
815     std::map<std::string, int> map;
816     ...
817     std::vector<std::string> vec;
818     vec.resize(map.size());
819     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
820               vec.begin());
821     \endcode
822
823     \since New in yat 0.5
824   */
825  template<class Iter>
826  boost::transform_iterator<
827    PairFirst<typename boost::remove_reference<
828                 typename std::iterator_traits<Iter>::reference
829                 >::type>,
830    Iter> pair_first_iterator(Iter i)
831  {
832    // We are going via ::reference in order to remain const info;
833    // ::value_type does not contain const information.
834    typedef typename std::iterator_traits<Iter>::reference ref_type;
835    typedef typename boost::remove_reference<ref_type>::type val_type;
836    typedef PairFirst<val_type> PF;
837    return boost::transform_iterator<PF, Iter>(i, PF());
838  }
839
840
841  /**
842     Creates a transform_iterator that transforms an iterator with
843     value type std::pair to an iterator with value type
844     std::pair::second_type. This can be used, for example, to
845     communicate between a std::map and std::vector
846
847     \code
848     std::map<std::string, int> map;
849     ...
850     std::vector<int> vec(map.size(),0);
851     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
852     \endcode
853
854     \since New in yat 0.5
855   */
856  template<class Iter>
857  boost::transform_iterator<
858    PairSecond<typename boost::remove_reference<
859                 typename std::iterator_traits<Iter>::reference
860                 >::type>,
861    Iter> pair_second_iterator(Iter i)
862  {
863    // We are going via ::reference in order to remain const info;
864    // ::value_type does not contain const information.
865    typedef typename std::iterator_traits<Iter>::reference ref_type;
866    typedef typename boost::remove_reference<ref_type>::type val_type;
867    typedef PairSecond<val_type> PS;
868    return boost::transform_iterator<PS, Iter>(i, PS());
869  }
870
871
872  /**
873     Convenient function that creates a binary predicate that can be
874     used to compare pointers when you want to compare them with
875     respect to the objects they point to.
876
877     Example:
878     \code
879     std::vector<MyClass*> vec(18);
880     ...
881     std::sort(vec.begin(), vec.end(),
882               make_ptr_compare(vec[0], std::greater<MyClass>()));
883     \endcode
884
885
886     Type Requirement:
887     - \a compare must be a <a
888     href="http://www.sgi.com/tech/stl/AdaptableBinaryPredicate.html">Adaptable
889     Binary Predicate</a>.
890     - value_type of Pointer must be convertible to argument_type of
891       compare
892
893     \return a compose_f_gx_hy in which \c F is defined by \a compare
894     and both \c G and \c H are \c Dereferencer functors.
895
896     \see compose_f_gx_hy
897
898     \since New in yat 0.7
899   */
900  template<typename Pointer, class Compare>
901  compose_f_gx_hy<Compare, Dereferencer<Pointer>, Dereferencer<Pointer> >
902  make_ptr_compare(Pointer p, Compare compare)
903  {
904    return make_compose_f_gx_hy(compare, Dereferencer<Pointer>(),
905                                Dereferencer<Pointer>());
906  }
907
908  /**
909     Same as make_ptr_compare(2) except that std::less is used to
910     compare pointers.
911
912     \since New in yat 0.7
913   */
914  template<typename Pointer>
915  compose_f_gx_hy<std::less<typename std::iterator_traits<Pointer>::value_type>,
916                  Dereferencer<Pointer>, Dereferencer<Pointer> >
917  make_ptr_compare(Pointer p)
918  {
919    typedef typename std::iterator_traits<Pointer>::value_type value_type;
920    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<value_type>));
921    std::less<value_type> compare;
922    return make_ptr_compare(p, compare);
923  }
924
925
926  ///
927  /// @brief Function converting a string to lower case
928  ///
929  std::string& to_lower(std::string& s);
930
931  ///
932  /// @brief Function converting a string to upper case
933  ///
934  std::string& to_upper(std::string& s);
935
936
937  // template implementations
938
939  template <typename Key, typename Tp, typename Compare, typename Alloc,
940            typename Key2>
941  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key2& key)
942  {
943    BOOST_CONCEPT_ASSERT((boost::Convertible<Key2, Key>));
944    typename std::map<Key, Tp, Compare,Alloc>::const_iterator iter(m.find(key));
945    if (iter==m.end()) {
946      // Avoid throw exception with Key2 because we do not want to
947      // require that Key2 is copy constructible. We know that Key is
948      // copy constructible from std::map requirement.
949      throw
950        get_error<Key>("utility::get(const Map&, const Key&): key not found",
951                       key);
952    }
953    return iter->second;
954  }
955
956}}} // of namespace utility, yat, and theplu
957#endif
Note: See TracBrowser for help on using the repository browser.