demonstrate 的 blog

minmax

我们知道从 个元素取 min 和 max 都是需要 次比较，更精确来说，最少需要 次比较。但是同时取最小和最大并不需要 次比较，因为一次比较中大的那个不可能是最小，而小的不可能是最大。可以证明， 次比较是次数最少的（先两两比较，然后大的里面取 max，小的里面取 min）。boost.minmax 提供了这种功能。可以直接用 boost/algorithm/minmax.hpp 里面的  boost::minmax 返回一个 const 类型的 tuple；也可以用 boost/algorithm/minmax_element.hpp 里面的 minmax_element 在 iterator 指定的范围里面返回一个 iterator 的 std::pair。下面是文档里面的例子。

#include <iostream>
#include <list>
#include <algorithm>
#include <cstdlib>
#include <cassert>

#include <boost/tuple/tuple.hpp>
#include <boost/algorithm/minmax.hpp>
#include <boost/algorithm/minmax_element.hpp>

int
main (int, char**) {
  using namespace std;
  boost::tuple<int const&, int const&> result1 = boost::minmax (1, 0);

  assert( result1.get<0>() == 0 );
  assert( result1.get<1>() == 1 );

  list<int> L;
  generate_n (front_inserter (L), 1000, rand) ;

  typedef list<int>::const_iterator iterator;
  pair< iterator, iterator > result2 = boost::minmax_element (L.begin (), L.end ()) ;
  cout << "The smallest element is " << *(result2.first) << endl;
  cout << "The largest element is  " << *(result2.second) << endl;

  assert (result2.first  == std::min_element(L.begin(), L.end())) ;
  assert (result2.second == std::max_element(L.begin(), L.end())) ;

  return 0 ;
}

bimap

这是对 std::map 这类关联容器的一种扩展，允许双向的映射，可以用 .left 和 right 然后就和 STL 的关联容器一样使用了。下面是一个 boost 提供的简单例子：

#define _CRT_SECURE_NO_DEPRECATE
#define _SCL_SECURE_NO_DEPRECATE

#include <string>
#include <iostream>

#include <map>
#include <boost/bimap/bimap.hpp>

using namespace boost::bimaps;

template< class Map, class CompatibleKey, class CompatibleData > void
use_it (Map & m,
        const CompatibleKey  & key,
        const CompatibleData & data) {
  typedef typename Map::value_type value_type;
  typedef typename Map::const_iterator const_iterator;

  m.insert (value_type (key, data)) ;
  const_iterator iter = m.find (key) ;
  if (iter != m.end()) {
    assert (iter->first  == key ) ;
    assert (iter->second == data) ;

    std::cout << iter->first << " --> " << iter->second << std::endl ;
  }
  m.erase (key);
}

int
main(int, char**) {
  typedef bimap< set_of<std::string>, set_of<int> > bimap_type;
  bimap_type bm;

  // Standard map
  {
    typedef std::map< std::string, int > map_type;
    map_type m;

    use_it (m, "one", 1) ;
  }

  // Left map view
  {
    typedef bimap_type::left_map map_type;
    map_type & m = bm.left;

    use_it (m, "one", 1) ;
  }

  // Reverse standard map
  {
    typedef std::map< int, std::string > reverse_map_type;
    reverse_map_type rm;

    use_it (rm, 1, "one") ;
  }

  // Right map view
  {
    typedef bimap_type::right_map reverse_map_type;
    reverse_map_type & rm = bm.right;

    use_it (rm, 1, "one") ;
  }

  return 0;
}

事实上可以用 set_of、multiset_of、unordered_set_of、unordered_multiset_of、list_of、vector_of 和 unconstrained_set_of 标明映射关系。

——————
And he sent forth a raven, which went forth to and fro, until the waters were dried up from off the earth.