STLのイテレータインタフェース再考

C++

STLイテレータは、コンテナとアルゴリズムをつなぐ中間インタフェース。STLではそのイテレータ自体のインタフェースとして、ポインタの構文を採用している。

ここではそのポインタの構文を、好んで使いたい構文ではないものとし、演算子ではなく名前のついた関数によるインタフェースで、イテレータを再設計してみる。

コード全体は以下を参照:

新しいイテレータインタフェースによるアルゴリズムの実装

まず、新しいイテレータインタフェースを使用しているところ、すなわちアルゴリズムの中身から見てみる。

namespace my_stl {
…
template <class Iterator, class F>
void for_each(Iterator first, Iterator last, F f)
{
    using traits = my_stl::iterator_traits<Iterator>;
 
    // no use raw pointer interface
    Iterator it = first;
    while (!traits::equal(it, last)) {
        f(traits::dereference(it));
        it = traits::next(it);
    }
}

} // namespace my_stl

ここでは、iterator_traitsというクラスが、イテレータのインタフェースとなっている(標準ライブラリに同名のクラスがあるが、それとは別物)。

このクラスは、以下の静的メンバ関数で、イテレータを操作する:

関数 説明
dereference() イテレータが指している要素を間接参照する
next() イテレータをひとつ進める
equal() 2つのイテレータを等値比較する

これらは、STLイテレータインタフェースとしてはそれぞれ、operator*()operator++()operator==()に相当する。

イテレータインタフェースの実装

このイテレータは、これらのメンバ名前による操作を直接サポートするイテレータクラスのみならず、従来のSTLと同様に、ポインタもサポートする。iterator_traitsクラスの実装は以下のようになっている:

namespace my_stl {
 
template <class Iterator>
struct iterator_traits {
    static typename Iterator::reference dereference(Iterator& it)
    {
        return it.dereference();
    }
 
    static Iterator next(const Iterator& it)
    {
        return it.next();
    }
 
    static bool equal(const Iterator& a, const Iterator& b)
    {
        return a.equal(b);
    }
};
 
template <class T>
struct iterator_traits<T*> {
    static T& dereference(T* it)
    {
        return *it;
    }
 
    static T* next(T* it)
    {
        return ++it;
    }
 
    static bool equal(const T* a, const T* b)
    {
        return a == b;
    }
};

} // namespace my_stl

iterator_traitsは、デフォルト実装としてのインタフェースのほかに、ポインタに対する特殊化を行っている。これによって、ポインタもイテレータとして振る舞えるようにしてある。

また、これと同じように、自分が使っているコンテナのイテレータが、デフォルトのインタフェースを持っておらず、ポインタでもない場合は、iterator_traitsクラスを特殊化してアダプトすれば、そのイテレータもまたアルゴリズムに適用可能になる。

今回用意したコンテナクラスは、singly_linked_listという名前の単方向リンクリスト。このコンテナクラスには、デフォルト実装の、dereference()next()equal()というメンバ関数を持つイテレータを持たせている。

ユーザーコード

コンテナとイテレータの実装は簡単なものなので省略して、コンテナと配列(ポインタ)をアルゴリズムに適用できているところを確認する。

#include <iostream>
int main()
{
    my_stl::singly_linked_list<int> ls;
    ls.push_front(3);
    ls.push_front(2);
    ls.push_front(1);
 
    my_stl::for_each(ls.begin(), ls.end(), [](int& x) {
        std::cout << x << std::endl;
    });
 
    int ar[3] = {4, 5, 6};
    my_stl::for_each(ar, ar + 3, [](int& x) {
        std::cout << x << std::endl;
    });
}

出力:

1
2
3
4
5
6

まとめ

ここでは、STLの「ポインタもイテレータとして振る舞えるようにする」という設計方針を維持したまま、イテレータのインタフェースを見直してみた。近年、データ構造とアルゴリズムをつなぐ中間インタフェースを用意するライブラリが増えてきた。Boost.Graph、Boost.Geometryなどが参考になる。これらのライブラリによって、中間インタフェースの設計がさらに洗練されたので、それを大元であるSTLの設計に適用した、というのが今回の試みだ。

Rangeが出てくると話はまた違ってくるのだが、いまイテレータを再設計するならこうなる、というのを示してみた。

参照


書籍『プログラミング言語C++ 第4版』

C++

C++の創始者Bjarne Stroustrupによる『プログラミング言語C++』の第4版、その日本語版が出ます。この版では、C++11への対応が行われています。

SBクリエイティブ社のページはまだないようですが、Amazonでは、2015年1月26日発売になっています。

Emscriptenへのpull requestレポート

Emscriptenにpull requestをして取り込んでもらえたので、そのレポートです。

Emscriptenとは

C言語C++で書いたコードを、LLVMを使ってJavaScriptコンパイルするコンパイラです。 標準ライブラリの範囲だけでなく、OpenGLのコードを書くとWebGLに、OpenALSDLAPIでオーディオ関係のコードを書くとWeb Audioにコンパイルされたりもします。

pull requestの内容

直した内容としては、たったの1行です。

Emscriptenのドキュメントを眺めていたら、リリースノートへのリンクが切れていたので、正しいリンクに直しました。

詳細なやりとり

最初のpull request。

  • 私の修正としては、リンク切れを直して、ChangeLogChangeLog.markdownのように拡張子を直しただけです。
  • その修正に対していろいろなコメントが入りました。
    • 「これは問題を完全には解決しない。ドキュメントはいまMarkdownからreStructuredTextに移行してるところだ。」
    • 「んー、changelogを管理してるのはぼくじゃないからよくわからないな。」
    • ここでchangelogを管理しているjujさんが登場して、「ここでの問題はリンク切れだから、その問題を直すだけならこのpull requestで必要十分だ」と言ってくれて、取り込んでもらえることになりました。
  • jujさんから、「AUTHORS(作者たち)に名前を載せるから、AUTHORSに名前を追加するpull requestをください。pull requestの練習だと思ってやってみて。」と言われ、いろいろ調べながらpull requestしたブランチに追加のコミットをした。
  • pull request先がmasterブランチになっていたので、「開発ブランチはincomingだからそっちにpull requestし直してほしい」と言われた。

やり直したpull requestが以下:

これを送ったら、10分後くらいにすぐ取り込んでもらえました。

まとめ

Emscriptenでのpull requestでまず感じたのは、開発者を育てる文化があっていいな、ということでした。pull requestにさらに修正を依頼するのはコントリビュートのハードルを上げることになるので、pull requestに多少問題があっても、開発者がマージしてから手直しをする、ということが事例として多いです。しかし、実際に修正を依頼されてやってみて、自分の成長が感じられたのでやってよかったと思います。

また、AUTHORSに名前を載せてもらえたこともうれしかったです。1行コミットしかしていないのに恐縮ですが、Emscriptenはコントリビュータを大事にしていることがわかりました。

もし今後Emscriptenにコントリビュートする方がいたら、何らかの参考になれば幸いです。

C++17の新機能予定

C++

C++17、およびTechnical Speficicationに採択された提案文書。

コア言語

template<typename... Args>
bool f(Args... args) { 
    return (true + ... + args);
} 

ライブラリ

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);

Parallelism TS

Library Fundamentals TS

Library Fundamentals TS 2

Transactional Memory TS

その他、承認された変更

  • N4230で、入れ子になった名前空間の定義を、namespace A::B::C {}と書けるようにする。意味としてはnamespace A { namespace B { namespace C { }}}を短く書けるようにしただけ。
  • N3922で、よく落とし穴になっていたauto x{y};の意味を変更し、yの型を推論するようにした。これまでは驚くことに、xinitializer_listと推論されていた。
  • N4086で、トライグラフを 削除する ことにした。
  • N4190で、非推奨になっていた機能をC++17の標準ライブラリから 削除する
    • auto_ptrbind1st/bind2ndptr_fun/mem_fun/mem_fun_refrandom_shuffle、その他いくつか。

boostjp/cpprefjpサイトを、GitHub Pagesに移行します

C++

これまで、boostjpとcpprefjpの両サイトはGoogle Sites上で運営を行っていましたが、GitHub Pagesに移行しようと思います。

旧サイト (Google Sites):

新サイト (GitHub Pages):

編集用のGitHubリポジトリ

GitHubリポジトリでMarkdownドキュメントを編集すると、GitHub Pagesのhtmlに即時変換して反映されるようにしてあります。 その運営ツールは、cpprefjpのGitHubリポジトリにあります。用意してくれた id:melpon に感謝です。

移行の詳細は、cpprefjp GitHubリポジトリのアナウンスIssueを参照してください。

また、それに伴い、boostjp Google Groupの運営を終了しました。

今後とも、boostjp、cpprefjpの両サイトをよろしくお願いします。皆さまのコントリビュートをお待ちしております。

Effective Modern C++の予約開始

C++

Scott Meyersの著書『Effective C++』のC++11とC++14対応である『Effective Modern C++ (略称EMC++)』の予約が開始しました。発売は12月4日になっています。

副題は「42 Specific Ways to Improve Your Use of C++11 and C++14」、日本語だと「C++11とC++14の使い方を改善する42の方法」といったところでしょうか。

書籍『From Mathematics to Generic Programming』

C++

おもしろそうな本が出るなぁと思ってなんとなく読んでいたら、共著者の一人がAlexander Stepanovでした。STLの設計者です。

そういえば彼の著書である『Elements of Programming (邦訳:プログラミング原論)』もまだ読んでなかった。

Boost 1.57.0リリース

C++

Boost 1.57.0がリリースされました。

リリースノートの日本語訳を、boostjpのGitHubリポジトリで公開しています。(boostjpのGoogle Siteには未反映)

今回は大きな変更はありませんが、以下の機能拡張がうれしいですね。

  • Boost.Moveに、C++03でも使えるunique_ptrが入った。(元々Interprocessにあったものを正式化)
  • Boost.Containerに、std::initializer_listのサポートが入った。

Boost 1.57.0のリリースノート翻訳を開始します

C++

Boost 1.57.0のBetaがリリースされ、本リリースが近づいてきているので、恒例のリリースノート翻訳を開始します。

現在、boostjpサイトは作業環境をGitHubに移行中のため、まだサイトの方に反映はできないのですが、ひとまずboostjp/siteリポジトリにMarkdownでリリースノートを書き、GitHub上のプレビューで読めるようにしようと思います。

リポジトリは以下です:

Boost 1.57.0のリリースノートは以下です:

push権限を持っていない方は、pull requestをいただければ、そのあとに権限をお渡しします。GitHub上でこのファイルを直接編集するとpull requestを作成できるので、GitとGitHubに慣れていない方でも、気軽に編集していただければと思います。

1文字の誤字修正から、気軽にご参加ください。