C++1z 標準イテレータ全般とarrayの変更操作にconstexprを追加

C++

C++1zでは、以下の機能にconstexprが付きます。

  • <iterator>
    • std::advance()関数
    • std::distance()関数
    • std::next()関数
    • std::prev()関数
    • std::reverse_iteratorクラスのメンバ関数、非メンバ関数すべて
    • std::move_iteratorクラスのメンバ関数、非メンバ関数すべて
    • コンテナに対するstd::begin()、std::end()関数
    • コンテナに対するstd::rbegin()、std::rend()関数
    • 配列に対するstd::rbegin()、std::rend()関数
    • std::initializer_listに対するstd::rbegin()、std::rend()関数
    • std::crbegin()、std::crend()関数
  • <array>
    • std::arrayの以下のメンバ関数
      • begin()、end()
      • rbegin()、rend()
      • cbegin()、cend()
      • crbegin()、crend()
      • operator[ ]
      • at()
      • front()
      • back()
      • data()

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z 連想コンテナ用のデフォルトの順序付け

C++

この機能はC++1z入りが取り消されました。

mapやsetのキーとなる型はデフォルトで、operator<で比較できる必要があります。連想コンテナのキーにできるようにするために、ユーザー定義型にoperator<を定義することもありますが、その比較演算を連想コンテナ以外の用途では使わないことが多々あります。

連想コンテナ用の比較演算とそうでない比較演算で用途を分けられるようにするために、C++1zではdefault_orderという中間インタフェースの型が定義されます。

// <functional>
namespace std {
    template <class T = void>
    struct default_order {
        using type = std::less<T>;
    };

    template <class T = void>
    using default_order_t = typename default_order<T>::type;
}

そして、連想コンテナの比較演算関数オブジェクトは、std::lessクラスを直接使用するのではなく、default_orderを介してstd::lessを使用するよう変更されます。これによるABIの破壊はありません。

// <map>
namespace std {
    template <class Key, class T, class Compare = default_order_t<Key>,
            class Allocator = allocator<pair<const Key, T>>>
    class map;

    template <class Key, class T, class Compare = default_order_t<Key>,
              class Allocator = allocator<pair<const Key, T>>>
    class multimap;
}

// <set>
namespace std {
    template <class Key, class Compare = default_order_t<Key>,
              class Allocator = allocator<Key>>
    class set;


    template <class Key, class Compare = default_order_t<Key>,
              class Allocator = allocator<Key>
    class multiset;
}

// <queue>
namespace std {
    template <class T, class Container = vector<T>,
              class Compare = default_order_t<typename Container::value_type>>
    class priority_queue;
}

型を連想コンテナのキーとして使用できるようにするためだけに順序付けしたい場合は、default_orderを特殊化して順序判定用の関数オブジェクトを使用するよう指定することになります。

namespace sales {
    struct account {
        int id;
        std::string name;
    };

    // 連想コンテナで順序付けするための関数オブジェクト
    struct order_accounts {
        bool operator()(const Account& lhs, const Account& rhs) const {
            return lhs.id < rhs.id;
        }
    };
}

namespace std {
    // sales::account型については、
    // sales::order_account関数オブジェクトでキーの順序付けをする
    template<>
    struct default_order<sales::account>
        using type = sales::order_accounts;
    };
}

int main()
{
    std::set<sales::account> s;
}

教科書的な説明がむずかしくなるので、ちょっと困りますね。advancedな用途と考えて、初心者向けには従来の方法を説明するのがよさそうです。

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z 連想コンテナの接合

C++

C++1zでは、2つの連想コンテナを接合(splice)する機能が入ります。対象は、map、set、unordered_map、unordered_setとそれらのmulti版すべてです。

まず、特定の要素を抽出する機能として、extract()メンバ関数が追加されます。

node_type extract(const_iterator position);
node_type extract(const key_type& x);

要素を抽出する操作にともない、すべての連想コンテナに、node_typeという入れ子型が追加されます。その実装となる型は、標準ライブラリの機能としては定義されず、連想コンテナの要件としてnode_typeができることが定義されます。

次に、抽出した要素をほかのコンテナに挿入する機能として、insert()メンバ関数にnode_typeを受け取るオーバーロードが追加されます。

insert_return_type insert(node_type&& nh);
iterator insert(const_iterator hint, node_type&& nh);

この挿入機能のために、非multi連想コンテナにinsert_return_typeという入れ子型が追加されます。multi連想コンテナはiteratorを返します。insert_return_type型も標準ライブラリの機能としてではなく、要件として定義されます。この型は、以下のメンバ変数を持ちます：

bool inserted;        // 挿入が成功したか
X::iterator position; // 挿入した要素を指すイテレータ
X::node_type node;    // 指定されたノード

最後に、2つの連想コンテナをまるまる接合するmerge()メンバ関数が追加されます。このメンバ関数は、multi版と非multi版の両方のコンテナを受け取れます。たとえばmapの場合は、以下のメンバ関数を持ちます。

template <class C2>
void merge(map<Key, T, C2, Allocator>& source);

template <class C2>
void merge(map<Key, T, C2, Allocator>&& source);

template <class C2>
void merge(multimap<Key, T, C2, Allocator>& source);

template <class C2>
void merge(multimap<Key, T, C2, Allocator>&& source);

サンプルコード : 抽出と挿入

#include <map>
#include <string>

int main()
{
    std::map<int, std::string> src {{1,"one"}, {2,"two"}, {3,"buckle my shoe"}};
    std::map<int, std::string> dst {{3,"three"}};

    dst.insert(src.extract(src.find(1))); // イテレータ版
    dst.insert(src.extract(2)); // キー版

    // 挿入先にすでに同一キーの要素がある場合は、挿入されない
    auto r = dst.insert(src.extract(3));

//  src == {}
//  dst == {"one", "two", "three"}
//  r.position == dst.begin() + 2
//  r.inserted == false
//  r.node == "buckle my shoe"
}

サンプルコード : コンテナまるごとマージ

#include <set>

int main()
{
    std::set<int> src{1, 3, 5};
    std::set<int> dst{2, 4, 5};

    dst.merge(src); // srcをdstにマージ

    // マージできなかった要素はsrcに残る
//  src == {5}
//  dst == {1, 2, 3, 4, 5}
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z mapとunordered_mapに、挿入失敗時の動作を規定した新たなメンバ関数を追加

C++

一意なキーを持つstd::mapとstd::unordered_mapに対して、2種類のメンバ関数が追加されます。対象には、std::multimapやstd::unordered_multimapおよび集合コンテナは含みません。

  1. try_emplace()メンバ関数 : 挿入失敗時に、与えられたパラメータargs...を変更しないことが保証される
  2. insert_or_assign()メンバ関数 : 挿入に失敗したら上書きする (m[key] = value;と同じような動作)

元々はinsert()とemplace()の仕様を修正することが考えられていましたが、議論の結果、別名の関数が定義されることになりました。

std::map<std::string, std::unique_ptr<Foo>> m;
m["foo"] = nullptr;

std::unique_ptr<Foo> p(new Foo);
auto res = m.try_emplace("foo", std::move(p));
assert(p); // pは有効

insert_or_assign()は、これまでと同様にpair<iterator, bool>を戻り値として返します。挿入に失敗して上書き操作をするときに、second == falseとなります。

宣言

// mapとunordered_mapのメンバ関数
template <class... Args>
pair<iterator, bool> try_emplace(const key_type& k, Args&&... args);
template <class... Args>
pair<iterator, bool> try_emplace(key_type&& k, Args&&... args);
template <class... Args>
iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args);
template <class... Args>
iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args);

template <class M>
pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj);
template <class M>
pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj);
template <class M>
iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj);
template <class M>
iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z ロケール依存なし、フォーマット解析なしの高速な文字列・数値変換

C++

C++1zから、低レイヤーの文字列・数値間の変換関数が導入されます。これは、ハイパフォーマンスな文字列処理をするための基礎を提供することを目的としています。

数値から文字列への変換はto_chars()、文字列から数値への変換はfrom_chars()という関数です。これらの関数は、以下の特徴があります。

  • ロケールはCロケール (POSIXロケール) 固定
  • 関数内での動的メモリ確保なし
  • フォーマットはパラメータとして与え、自動的にフォーマットを解析することはない
  • 使用できるフォーマットも最小限
    • +符号の指定はできない
    • 文字列中のスペースは許容されない
    • #による小数点以下の桁数指定はできない
    • ゼロ埋めはできない
    • 小文字のみ許容し、大文字は扱えない
    • 16進数に0xは付けられない
  • 例外送出なし
#include <iostream>
#include <utility>
#include <limits>

int main()
{
    {
        char str[std::numeric_limits<int>::digits10 + 2] = {0}; // '-' + NULL
        int input = 123456;

        // 整数inputを10進数で文字列に変換し、strに出力
        std::to_chars(std::begin(str), std::end(str), input, 10);
        std::cout << str << std::endl; // 123456
    }
    {
        const char input[] = "-123456";
        int value = 0;

        // 10進数の整数が入った文字列を、intに変換
        std::from_chars(std::begin(input), std::end(input), value);
        std::cout << value << std::endl; // -123456
    }
}

宣言

// <utility>
namespace std {
    struct to_chars_result {
        char* ptr;
        error_code ec;
    };

    enum class chars_format {
        scientific = unspecified,
        fixed = unspecified,
        hex = unspecified,
        general = fixed | scientific
    };

    // 数値から文字列への変換
    to_chars_result to_chars(char* first, char* last, see below value, int base = 10); // 整数版
    to_chars_result to_chars(char* first, char* last, float       value);
    to_chars_result to_chars(char* first, char* last, double      value);
    to_chars_result to_chars(char* first, char* last, long double value);

    to_chars_result to_chars(char* first, char* last, float       value, chars_format fmt);
    to_chars_result to_chars(char* first, char* last, double      value, chars_format fmt);
    to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt);

    to_chars_result to_chars(char* first, char* last, float       value, chars_format fmt, int precision);
    to_chars_result to_chars(char* first, char* last, double      value, chars_format fmt, int precision);
    to_chars_result to_chars(char* first, char* last, long double value, chars_format fmt, int precision);


    // 文字列から数値への変換
    struct from_chars_result {
        const char* ptr;
        error_code ec;
    };

    from_chars_result from_chars(const char* first, const char* last, see below& value, int base = 10); // 整数版

    from_chars_result from_chars(const char* first, const char* last, float& value, chars_format fmt = chars_format::general);
    from_chars_result from_chars(const char* first, const char* last, double& value, chars_format fmt = chars_format::general);
    from_chars_result from_chars(const char* first, const char* last, long double& value,  chars_format fmt = chars_format::general);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z 最大公約数と最小公倍数

C++

C++1zから、2つの値の最大公約数(Greatest common divisor)を求めるgcd()関数と、最小公倍数(Least common multiple)を求めるlcm()関数が導入されます。

これらの関数は、<cmath>ではなく数値計算用のC++ヘッダ<numeric>で定義されます。bool以外の整数型ならなんでも扱えます。

#include <iostream>
#include <numeric>

int main()
{
    int x = std::gcd(12, 18);
    int y = std::lcm(3, 5);

    std::cout << x << std::endl;
    std::cout << y << std::endl;
}

出力：

6
15

宣言

// <numeric>
namespace std {
  template <class M, class N>
  constexpr common_type_t<M, N> gcd(M m, N n);

  template <class M, class N>
  constexpr common_type_t<M, N> lcm(M m, N n);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z タプルを任意の型のオブジェクトに変換するmake_from_tuple関数

C++

タプルを展開して関数呼び出しするapply()関数の導入に合わせて、タプルを任意の型に変換するmake_from_tuple()関数が導入されます。

apply()関数ではオブジェクトの構築までカバーができない(コンストラクタを呼び出せない)ので、そのコーナーケースをカバーするのが目的です。

この関数は、引数のタプルを展開して、テンプレートパラメータの型Tのコンストラクタ引数として渡し、T型のオブジェクトを構築して返します。

make_from_tuple()相当のことは、std::pairクラスのpiecewiseコンストラクタがすでに行っています。(参照 : 「pairのpiecewise construction」)

また、make_from_tuple()は、Boost.Fusionのcopy()アルゴリズムに相当します。ユースケースとして、構文解析の結果となる「異なる型が混在した値のシーケンス」を受け取りたい結果型に変換するためにも使用できるでしょう。

#include <iostream>
#include <string>
#include <tuple>

struct Person {
    int id;
    double bodyHeight;
    std::string name;

    Person(int id, double bodyHeight, const std::string& name)
        : id(id), bodyHeight(bodyHeight), name(name) {}
};

int main()
{
    std::tuple<int, double, std::string> t(1, 152.3, "Alice");
    Person p = std::make_from_tuple<Person>(t);

    std::cout << p.id << std::endl;
    std::cout << p.bodyHeight << std::endl;
    std::cout << p.name << std::endl;
}

宣言

// <tuple>
namespace std {
  template <class T, class Tuple>
  constexpr T make_from_tuple(Tuple&& t);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z タプルを展開して関数呼び出しするapply関数

C++

C++1zから、タプルを引数列に変換して関数適用するapply()関数が入ります。これは、C++14で追加されたコンパイル時整数シーケンスを使用した最初の標準ライブラリ実装になります。

#include <iostream>
#include <tuple>
#include <string>

void f(int a, double b, std::string c)
{
    std::cout << a << std::endl;
    std::cout << b << std::endl;
    std::cout << c << std::endl;
}

int main()
{
    std::tuple<int, double, std::string> args(1, 3.14, "hello");
    std::apply(f, args);
}

出力：

1
3.14
hello

宣言

// <tuple>
namespace std {
  template <class F, class Tuple>
  constexpr decltype(auto) apply(F&& f, Tuple&& t);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z ランダムサンプリングアルゴリズム

C++

C++1zでは<algorithm>ヘッダに、範囲の中から指定された個数の要素をランダムに抽出するsample()アルゴリズムが定義されます。

#include <iostream>
#include <string>
#include <iterator>
#include <random>
#include <algorithm>

int main()
{
    const std::string input = "abcdef";

    // inputから3要素を無作為抽出する。
    // デフォルトの乱数生成器を使用する
    {
        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3);
        std::cout << result << std::endl;
    }

    // inputから3要素を無作為抽出する。
    // 乱数生成器を明示的に渡す
    {
        std::random_device seed_gen;
        std::mt19937 engine {seed_gen()};

        std::string result;
        std::sample(input.begin(),
                    input.end(),
                    std::back_inserter(result),
                    3,
                    engine);
        std::cout << result << std::endl;
    }
}

選ばれる確率は等確率になります。

範囲の要素数が、指定された抽出数よりも小さい場合、範囲の要素数だけ抽出されます。

乱数生成器を渡さない場合、スレッドローカルな乱数生成器が関数内で定義されます。この記事の執筆時点で実装がないので実際にどうなるかはわかりませんが、おそらくdefault_random_engineが使われることになるので、自分で乱数生成器を渡すのがよいと思います。

このアルゴリズムの最適化の余地として、以下の2つの実装がありえます：

  • 出力をランダムアクセスで行うバージョン : KnuthのAlgorithm R (Reservoir sampling)
  • 出力を前から順番に行うバージョン : KnuthのAlgorithm S (Selection sampling)

イテレータカテゴリによってこれらの実装が、コンパイル時に自動的に選択されるようになる可能性があります。

宣言

// <algorithm>
namespace std {
    template <class PopulationIterator, class SampleIterator, class Distance>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n);

    template <class PopulationIterator, class SampleIterator,
              class Distance, class UniformRandomNumberGenerator>
    SampleIterator sample(PopulationIterator first, PopulationIterator last,
                          SampleIterator out, Distance n,
                          UniformRandomNumberGenerator&& g);
}

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。

C++1z 文字列検索アルゴリズム

C++

C++1zでは、文字列内の文字列を高速に検索するためのアルゴリズムとして、「ボイヤー・ムーア法 (Boyer-Moore)」と「ボイヤー・ムーア・ホースプール法 (Boyer-Moore-Horspool)」が導入されます。

これは、既存のstd::search()アルゴリズムを拡張する形で行われ、検索アルゴリズムを外部から指定するためのパラメータが追加されます。

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>

int main()
{
    // ボイヤー・ムーア法で、文字列内の特定文字列を検索
    const std::string corpus = "…"; // 検索対象
    const std::string pattern = "…"; // 対象の中に見つけたい文字列

    auto it = std::search(
                corpus.begin(),
                corpus.end(),
                std::boyer_moore_searcher(
                    pattern.begin(),
                    pattern.end()
                ));
    if (it != corpus.end()) {
        std::cout << "found" << std::endl;
    }
    else {
        std::cout << "not found" << std::endl;
    }
}

検索アルゴリズムは以下の3つが用意されます。

  • default_searcher
  • boyer_moore_searcher
  • boyer_moore_horspool_searcher

default_searcherはこれまで通りのstd::search()の動作をします。

宣言

// <algorithm>
namespace std {
    template <class ForwardIterator, class Searcher>
    ForwardIterator search(ForwardIterator first, ForwardIterator last,
                           const Searcher& searcher);
}

// <functional>
namespace std {
    // 検索ポリシークラス
    template <class ForwardIterator, class BinaryPredicate = equal_to<>>
    class default_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_searcher;

    template <class RandomAccessIterator,
              class Hash = hash<
                      typename iterator_traits<RandomAccessIterator>::value_type
                    >,
              class BinaryPredicate = equal_to<>>
    class boyer_moore_horspool_searcher;
}

Boostと標準の差異

Boost 1.50.0でBoost Algorithm Libraryがリリースされ、そこに文字列検索のアルゴリズムが含まれています。Boost 1.61.0現在は、std::search()を拡張するようなポリシーベースの設計ではなく、アルゴリズムごとに別名の関数が定義されています。

Boostの方には、標準に追加される2つのアルゴリズムに加えて、knuth_morris_pratt_search()アルゴリズムがあります。これはKMP法という名前で知られているアルゴリズムです。(クヌース・モリス・プラット法)

参照

お断り

この記事の内容は、C++1zが正式リリースされる際には変更される可能性があります。正式リリース後には、C++日本語リファレンスサイトcpprefjpの以下の階層の下に解説ページを用意する予定です。