Mastering the C++17 STL

Info

• 書名: Mastering the C++17 STL
• 著者: Arthur O'Dwyer
• 読んだ時期: 2021.07~08

Motivation

c++14, 17以降のモダンな機能をあまりよく知らず、コードを読むときも抵抗感が生まれていたため、モダンなSTLへの理解を深めるために読んだ。

Contents

1. Classical Polymorphism and Generic Programming

アルゴリズムのふるまいをParametrizeするために導入された概念であるところのPolymorophismとGeneric Programming。

• Concreteな単一型に対する関数の例

class array_of_ints {
    int data[10] = {};
    public:
        int size() const { return 10; }
        int& at(int i) { return data[i]; }
};

void double_each_element(array_of_ints &arr) {
    for (std::size_t i = 0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
    }。
これだと`array_of_ints`型にしか対応していない。配列だけでなく、他の様々なコンテナに対して使えるようにしたいので、Class継承によりPolymorphismを実現する。

```cpp
class container_of_ints {
    public:
        virtual std::size_t size() const = 0;
        virtual int &at(std::size_t) = 0;
};

class array_of_ints: public container_of_ints {
    int data[10] = {};
    public:
        std::size_t size() const override { return 10; }
        int &at(std::size_t i) override { return data[i]; }
};
// linked list
class list_of_ints: public container_of_ints {
    struct node {
        int data;
        node* next;
    };
    node* head_ = nullptr;
    std::size_t size_ = 0;
    public:
        std::size_t size() const override { return size_; }
        int &at(std::size_t i) override {
            if (i >= size_) throw std::out_of_range("at");
            node *p = head_;
            for (std::size_t j = 0; j < i; ++j) {
                p = p->next;
            }
            return p->data;
        }
        ~list_of_ints();
};

こうすると、基底クラスであるcontainer_of_intsを用いて

void double_each_element(container_of_ints &arr) {
    for (std::size_t i = 0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
    }
}

と書ける。これでコンテナの種類をParametrizeしたことになる。

これをModern C++のTemplateを使うと、このように書ける:

template<class ContainerModel>
void double_each_element(ContainerModel& arr) {
    for (std::size_t i = 0; i < arr.size(); ++i) {
        arr.at(i) *= 2;
    }
}

void test() {
    array_of_ints arr;
    double_each_element(arr);
    list_of_ints lst;
    double_each_element(lst);
    // and other many kinds of containers !!
}

Templateの引数として指定することで、関数が”生成”されるとも言える。

こうするメリットとして、

• virtualなメソッドなどを使わないので、コンパイル時にInline化できる機会が増える
• Classicalな方法では様々なクラスの振る舞いを、不変なインタフェースとなるメソッド(例えば.at())の裏に隠蔽していることになる。このインタフェース自体を弄ろうとすると、途端に扱いが大変になる。 などがある。

ただし、Classicalな方法の良い点として、

• コンパイラが吐く機械語とソースコードの関数が一対一に対応している(double_each_element関数はただ１つであり、関数ポインタとしてアドレスを取り出したりできる)

などがある。

2. Iterators and Ranges, 3. The Iterator-Pair Algorithms

Iteratorの解説と、それを用いて基本アルゴリズムを整理する話。

• Indexだけでは限界がある。例えば1. では、配列やVectorなら良いが、連結リストだけ振る舞いがかなり異なる。
• ポインタを使えばデータ構造を一般的に扱えるはず。しかし生ポインタは、例えば連結リストにおいて”次の要素”を指したいときに、単なる加算だけでは想定通りに振る舞わない場合がある。
• そこで、Iteratorは生ポインタの抽象化をし、Increment=次の要素を指す、といった直感に沿う操作を可能にしている。
• Iteratorが2つペアになると、それはRangeを定義していることになる。どこからどこまで、その間はいくつ空いている、といったことがIteratorに対する演算で実現できる。

4. The Container Zoo

STLのコンテナの話。競プロである程度知っていた。

各論を書いてもアレなので一般的な知見として、

• STLのコンテナは、要素の”所有権”を管理していて、Allocatorを指定することでメモリ管理方法を決められる。
• 比較の基準のためのComparator型を渡せば、比較演算もParametrizeできる
• STLは効率的な方法を自然にユーザーが使用するように作られている。
• 困ったらDocumentを読もう！

全体的に、挙動をParametrizeして多相性を持たせたいという思想を感じた。そのような機能であることを念頭に置いたコーディングをしたい。

5. Vocabulary Types

std::stringなどのポピュラーな型から、std::Any, Optional, Variantといった(個人的に)あまり馴染みのなかった型まで解説されていた。

std::string

• 極力char*ではなくstd::stringを使う。これはOwnershipとLifetimeの管理を任せるため。

std::reference_wrapper

implicitにreferenceへ変換してくれるやつ。使いどころがわからなかったのだが、例えば以下のように使うらしい。

• container of references 出典 (opens new window)

// 連結リストをシャッフルしたいとき
std::list<int> lst(10);
std::iota(lst.begin(), lst.end(), -4);
// lst: -4 -> -3 -> -2 -> ... -> 5
// std::shuffleはrandom access可能なコンテナにのみ使える -> referenceを要素に持つvector使おう
std::vector<std::reference_wrapper<int>> vec(lst.begin(), lst.end());
std::random_device rd;
std::mt19937 mt(rd());
std::shuffle(vec.begin(), vec.end(), rd);

for (int num: lst) {
    std::cout << num << " ";
}
std::cout << std::endl;
for (int num: vec) {
    std::cout << num << " ";
}
std::cout << std::endl;
for (int& num: lst) {
    num *= 2;
}
for (int num: vec) {
    std::cout << num << " ";
}
std::cout << std::endl;
}

Output:

-4 -3 -2 -1 0 1 2 3 4 5 
0 2 -3 1 3 5 -4 4 -1 -2 
0 4 -6 2 6 10 -8 8 -2 -4 

std::variant

std::unionとほとんど同じだが、std::variantは今どの型を保持しているかが明示された挙動をする。

std::optional<T>

"Maybe I have an object, maybe I don't."の気持ち

std::function

関数, lambda, 関数オブジェクト、クラスのメソッドを統一的に扱う

// 関数
int my_abs(int x) {
    return x < 0 ? -x: x;
}
// class
class MyFoo {
    int num_;
public:
    MyFoo(const int num): num_(num) { }
    void display_num() const {
        std::cout << "number = " << num_ << std::endl;
    }
}
// 関数オブジェクト
struct SumOfSquare {
    float operator()(const float x, const float y) {
        return x * x + y * y;
    }
}

void test() {
    std::function<int(int)> f = my_abs;
    assert(f(-2) == 2);
    std::function<void(const MyFoo&)> f_class = &MyFoo::display_num;
    f_class(123);
    std::function<float(float, float)> f_func_obj = SumOfSquare;
    assert(f_func_obj(1.0, 2.0) == 5.0);
}

6. SmartPointer

あるインターンでnew/deleteを咎め(?)られたのをきっかけに頻繁に使うようになったので、既知事項だった。 これ無しでは生きていけませんという感じの章。

7. Concurrency

8. Allocators

自分でCustom Allocatorを書いたことが無く、ちょっと取っつきづらかったのでこの動画 (opens new window)を見た。

Allocatorを書くにはこうすればいいというのを、思考の過程を呟きながら書いてくれるので本当に良い。チャンネル登録しました。

Resource/Allocatorの違い、Allocatorを作る部分は理解できたが、その他の部分はちょっと消化不良なので頭にしまっておいて熟成を待つ。

9. Iostreams

知りたかった事項だった。

まずI/Oには次の2つの段階がある。

• Buffering: input deviceからBytesデータを受け取る/Output DeviceへBytesデータを渡す、あくまでBinaryとして見た処理。
• Formatting: Bytesデータを型付けされたデータに変換する、言語的な処理。

POSIX API

C/C++のI/Oは全てPOSIX (opens new window) Standardに基づいている構成されている。POSIXはシステムコールレベルでの非常に低レベルな規格。 I/Oを理解するにはこれを理解、とまでは言わなくても概要を掴むことが大事、ということのよう。

”File”は記憶媒体上にある実体のことであり、プログラムで扱うのは”File Descriptor”へのポインタ。だが実際はInt型になっている。

ex) int fd = open("test.txt", O_RDONLY);

第2引数はBit Maskであり、ファイルに対するモードを表す。

• Required: O_RDONLY(read only), O_WRONLY(write only), O_RDWR(both read and write)
• Optionally: O_CREAT(if not exist, create new one), O_EXCL(if already exists, return failure), O_TRUNC(truncateする)
• Optionally: O_APPEND(append)

おおよそ、特にReadOnly, WriteOnly, Appendなどは普段色々な言語でファイルを扱う際に出てくるものに対応している。

さらに操作として

• read(fd, buffer, count)
• write(fd, buffer, count)
• lseek(fd, offset, SEEK_SET)
• lseek(fd, offset, SEEK_CUR)
• lseek(fd, offset, SEEK_END) がある。

Buffer管理がユーザに任されているし、それが全面に出ている。

しかも、例えばクソデカデータを送りたいといったときには、1byteずつwriteしていたら非常に効率が悪いので、4096bytesまとめて確保し一回でWriteに送るという行為が必要になる。 つまり、そのプログラムは大きなBufferに関して責任を持つことになっている。

Buffer管理を抽象化するとC APIになる。

The Standard C API

モードは"r", "w", "a"などのユーザーフレンドリーなやつ。

File DescriptorをFILE *fp = ...というようにファイルポインタとして扱うので、C++のスマートポインタと組み合わせるとこんなことができる。

struct fcloser {
    void operator()(FILE *fp) const {
        fclose(fp);
    }
    static auto open(const char *name, const char *mode) {
        return std::unique_ptr<FILE, fcloser>(fopen(name, mode));
    }
};

void test() {
    auto f = fcloser::oepn("test.txt", "w");
    fprintf(f.get(), "hello world");
    // deleterであるfcloserが呼ばれる。
}

std::unique_ptrのDeleterとしてFile Closerを指定するというやつで、ほえ〜となった。

Bufferに関しては、POSIX的なことも引き継いでいるが、一般的にはLarge Dataをガバっと扱うより、1byteずつ扱いたいね。

ということでgetc(fp)などを使うとこういうことができる。

wcコマンドのようなことをする実装

int wc(FILE *fp) {
    int res = 0;
    bool in_space = true;
    while (true) {
        int ch = getc(fp);
        if (ch == EOF) break;
        ++res;
        in_space = isspace(ch);
    }
    return res;
}

ここから標準出力みが出てきますね。

POSIXではFormattingが出てこなかったが、printf("hello %d\n", 1);みたいなFormattingができるようになる。

Iostreams

C++ streamでは、主にBufferの周りで問題のあったC APIのStreambufに対して、ユーザーが可能な操作を制限したstd::ostreamやstd::istream、そこからさらに StringなのかFileなのかでstd::istringstream, std::ifstreamなどと、”何に何をするのか”が明瞭な体系になっている。

こちらの記事 (opens new window)でも触れられているが、iostreamの継承関係を知っておくと忘れにくそう。

(図を貼るのは憚られたのでリンクだけにしておきます。) https://stackoverflow.com/questions/33972164/why-were-the-iostream-withassign-ostream-withassign-istream-withassign-classe

この話によらず、こういう普遍的な構造を頭に入れておくのはコンピュータのことを勉強する上で大事そうだと思っていて、意識的にやっているが、結局ドキュメントを見ちゃう。

11. Random Numbers

疑似乱数(Pseudo-random numbers)

rand()など、アルゴリズムによって生成されたRandomに見える数のことで、あくまでDeterministicである。 疑似乱数のSeedとして考えられるのは

• ユーザーが決める。実験の再現性担保など。
• time()など、ランダムではないが変動するものを使う。
• truly randomなSeed値を使う。

rand()の欠点

• rand() % kは均一でない
• global変数であるstateを使うので、thread-safeでない

<random>

• std::random_deviceは真の乱数
• 頻繁に使うのがメルセンヌ・ツイスタstd::mt19937で、これは疑似乱数

Adaptors

生成結果のフィルタリングをする。

std::vector<uint32_t> raw(10), filtered(10);

std::discard_block_engine<std::mt19937, 3, 2> g2;  // 3 block中先頭2blockのみ使う
std::mt19937 g1 = g2.base();  // 元のmtを取り出す

std::generate(raw.begin(), raw.end(), g1);
std::generate(filtered.begin(), filtered.end(), g2);

assert(raw[0] == filtered[0]);
assert(raw[1] == filtered[1]);
assert(raw[3] == filtered[2]);
assert(raw[4] == filtered[3]);

これは初見だった...。まあそうそう使わないと思われる(多分)。

ほかは各種確率分布のインタフェースや活用例、shuffleの話だった。

12. File System

C++でファイルシステムを扱うライブラリ<filesystem>について。boost由来らしい。

部分的にググってでてきたので使うってレベルでしかBoost使ったこと無いが、もはや標準ライブラリみたいな地位らしいので、一度は包括的に見ておくべきなのかなぁと思っている。 POSIX APIではPathは文字列として扱っていた。が、プラットフォーム・Encodingの問題が多かった。

C++ではpath型として扱える。Pythonみたい(どっちが先か知らんけど)

std::filesystem::path p("/path/to/somewhere");

const std::filesystem::path::value_type *a = p.c_str();
const char *b = p.c_str();
std::string s = p.u8string();
const char *c = s.c_str();

これに対する演算として、比較や/による結合などができる。

directory_iterator

文字通りディレクトリをIteratorによりWalk throughできるやつ。 例えば

void test() {
    fs::path p = fs::current_path();
    for (fs::directory_entry entry : fs::directory_iterator(p)) {
        std::cout << entry.path().string() << std::endl;
    }
}

Modify

copy, mkdir, symlink, remove, rename, resizeなどは一通り揃っている。POSIX Command-line Utilitiesに沿っている設計らしい。 その都度調べる系かな。

Disk Usage

これは意外と使いそうな気がしたのでメモ。 std::filesystem::space("path")でfilesystemのUsageなどが分かる。

struct space_info {
    uintmax_t capacity;
    uintmax_t free;
    uintmax_t available;
}

と思ったけどファイルシステムの管理をしたいだけならdf -hコマンドで良くて、それをC++から実現したい気持ちになる日が来るのか...?

以上！

Comment

STL、というかC++はあまりにも言語機能が巨大なので、その都度ググるといっても指標が必要な気がしていました。

この本は割とC++の思想やPOSIXからの歴史のことを書いていて、別にそういった周辺知識自体に興味があったわけではなかったものの、STLのOverviewを掴み、各機能を根っこから理解しようというスタンスだったのでとても勉強になりました。一生C++を書くわけではないと思いますが、やっぱり広く使われている言語だと思いますし、やや時間をかけてでも学生のうちに根幹を掴みたいです。C/C++が死んでも知識は活かせるはずなので。