Status List for Library Proposals

C++

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3371.html
C++11の次の改訂に向けたライブラリの提案を読んでみた．C++11もろくに知らないのでいろいろ読み間違いがあるかもしれない．

A minimal std::range

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3350.html

Overview

Ranges are ubiquitous in programs that use STL algorithms, but they're always written as adjacent iterator arguments, which makes them hard to use. Several groups have proposed a new set of range concepts that would allow ranges to be passed around as single objects. Two notable examples are the Boost.Range library and Andrei Alexandrescu's range concepts in D.

？？？

そもそもrangeが何なのか良くわからないのでそこから調べた．ということで，boost::rangeのドキュメントがこちら．
http://www.boost.org/doc/libs/1_49_0/libs/range/doc/html/index.html

下のコードは，mapから値を取り出していって，偶数だけを，逆順に，targetに追加する．

using namespace boost;
using namespace boost::adaptors;
// Assume that is_even is a predicate that has been implemented elsewhere...
push_back(target, my_map | map_values | filtered(is_even()) | reversed);
Range Concept

RangeとはSTLコンテナーコンセプトに似たコンセプトである．範囲にアクセスするためのイテレータと要素数を持つ．しかし，Rangeはコンテナより少ない要件を持つ．
今のところboost::rangeでは下の3つがサポートされている．

  • standard-like containers
  • std::pair
  • built-in arrays
Range Adapter

Range AdapterはRangeをラップして違うふるまいをする新しいRangeを提供するクラスである．

#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <iostream>
#include <vector>

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed,
             std::ostream_iterator<int>(std::cout) );

このboost::adaptors::reverseはAdopter Generatorと呼ばれる．

演算子|をキモいと思う人は，下のようにも書ける．このコードは，vecの要素を逆順にして，ユニークして，標準出力に出力する．

std::vector<int> vec;
boost::copy( boost::adaptors::unique( boost::adaptors::reverse( vec ) ),
             std::ostream_iterator<int>(std::cout) );

でも，こう書いた方がたぶんきれい．

std::vector<int> vec;
boost::copy( vec | boost::adaptors::reversed
                 | boost::adaptors::uniqued,
             std::ostream_iterator<int>(std::cout) );
Range Algorithm

Range Alogrithmの最も単純な例としては，2つのイテレータを渡すイテレータベースのアルゴリズムが1つで済むようになる．

#include <boost/range/algorithm.hpp>
#include <vector>

std::vector<int> vec = ...;
boost::sort(vec);  //std::sort(vec.begin(), vec.end());

しかし，戻り値の型が普通のイテレータベースのアルゴリズムとはたいてい異なる．どういうことかというと，boost::sortの戻り値はrangeなので，下のように，別のrangeアルゴリズムにそのまま渡すことが出来る．

boost:unique(boost::sort(vec));

Hashing User-Defined Types in C++1y

ユーザー定義型のハッシュ関数を定義しやすくしようという話．

namespace my_namespace {
  struct OtherType { ... };
  struct MyType {
    OtherType field1;
    int field2;
    char field3[500];
    float field4;  // Does not contribute to equality.
  };
  std::hash_code hash_value(const MyType& val) {
    return std::hash_combine(val.field1,
                             val.field2,
                             val.field3);
  }
}

このhash::combineに似たものはboostにあるけど，C++11には入っていない．

Hashing vs Fingerprinting

標準ライブラリの使い道は，現在のプロセスからしか使われないハッシュテーブルの検索に限る．つまり，異なるプロセスにある2つのオブジェクトのハッシュ値は同じ値を返すとは限らない．あと，ハッシュ値をディスクに保存したり，セキュリティに関連した使い方もすべきでない．

ハッシュテーブルは，std::hash()(object)がそのプログラムの実行中のみ同じ値を返すことを要求する．そのため，標準ライブラリは実装を変更してもいいはずである．しかし，Googleでは，きちんとしたドキュメントなかったこと，ハッシュの実装の変更があまりにまれだったために，開発者がハッシュ値をディスクに保存して，実装の変更により既存のコードが壊れるということがあった．そこで，ハッシュ関数は違うプロセスでは違う値を返すことを提案する．それにより，誤りに早く気付けるようになる．また，ハッシュ値を前もって計算するdenial-of-service攻撃も防ぎやすくなる．

Hashing Ranges

コンテナーなどハッシュ値の計算は以下のようにできるが，hash_combineの中でいちいち初期化が走るので効率的ではない．そこで専用の

hash_code hash_value(const MyType& val) {
  hash_code result = 0;
  for (const auto& v : val) {
    result = hash_combine(result, c);
  }
  return result;
}
Hashing objects as byte arrays

オブジェクトをバイト列としてみなすと高速に計算可能．ただしパディングがないことが条件．