C++98でvectorを再実装する

42Tokyo の課題でSTLコンテナの1つ、vectorを再実装しました。

この記事では、vectorの再実装で学んだことを書きます。

課題の概要と基礎知識について説明した後、vectorの実装で調査した内容、実装でハマったことについて説明します。

課題の概要

• 規格
  • C++98。後の規格で非推奨になっても実装が必要。
• 実装する内容
  • STLコンテナ：vector、map、stack（+ set）
    • カッコ内のコンテナを実装するとクリア時にボーナスが付きます。
    • イテレータも実装が必要になります。
    • vector<bool> を実装する必要はありません。
  • STLコンテナ以外：iterators_traits、reverse_iterator、equal、pairなど
    • この記事ではSTLコンテナ以外の詳細な実装は取り上げません。
• 実行速度の制限
  • 実装元のSTLコンテナの20倍まで許容されます。
    • コンパイルをclang++で行うので、ClangのSTLコンテナと比較します。
• リファレンス
  • cplusplus.com、 cppreference.com を参照することができます。

基礎知識

基礎知識の項目では、コンテナ、イテレータ、アルゴリズムについて説明します。

mapの記事 で説明したのとほぼ同じ内容です。すでにご存じの方は読み飛ばして問題ありません。

コンテナとイテレータとアルゴリズム

C++では以下の機能を使ってデータの扱いを共通化しています。

• データの格納：コンテナ
• 要素へのアクセス：イテレータ
• データの操作：アルゴリズム

コンテナ、イテレータ、アルゴリズムの関係を図にすると、以下のようになります。

コンテナ

コンテナは動的配列、連結リスト、辞書などのデータ構造を使ってオブジェクトを保持します。

コンテナには次の分類があります。

• シーケンスコンテナ
  • 配列のような直線的なデータ構造。例：vector、list
• 連想コンテナ
  • キーに基づいて探索可能なデータ構造。例：map、set
• コンテナアダプタ
  • 他のコンテナを元にインターフェースを提供。例：stack

今回実装するのはシーケンスコンテナのvectorです。

イテレータ

コンテナの各要素には添字演算子やイテレータを使ってアクセスします。

イテレータがあることで、コンテナを使う側はコンテナの内部実装を知ることなくコンテナの各要素を操作できます。

操作方法

• ポインタのように *iterator と * をつけるとその要素を参照できます。
• ++iterator とすると、現在の要素から次の要素に進みます。
• 後述するカテゴリによって、使える操作は異なります。

イテレータには5つのカテゴリがあり、それぞれで使える演算子が異なります。

• 入力イテレータ
• 出力イテレータ
• 前方向イテレータ
• 双方向イテレータ
• ランダムアクセスイテレータ

vectorはランダムアクセスイテレータが提供されます。

ランダムアクセスイテレータは以下の操作を行えます。

操作	式
次の要素に進む	++iter, iter++
前の要素に戻る	--iter, iter--
n個後/前の要素に進む/戻る	iter+n, n+iter, iter-n, n-iter, iter+=n, iter-=n
イテレータの距離を返す	iter-iter
n番目の要素にアクセスする	iter[n]
要素の読み込み、書き込み（非constなら）	*iter
クラスメンバの参照	iter->m
イテレータの比較	iter==iter, iter!=iter, iter<iter, iter>iter, iter<=iter, iter>=iter

アルゴリズム

アルゴリズムはイテレータを介してコンテナを操作できる関数を提供します。

例えば、以下の関数があります。

• 2つのイテレータの要素が同じか判定する equal
• 2つのイテレータの要素を入れ替える swap
• 2つのイテレータの区間で検索する find

実装の流れ

まず、江添亮の入門C++ の「vectorの実装」を読んで実装の大まかな流れを掴みました。

江添亮の入門C++では、イテレータがポインタになっているため、イテレータの実装について調査しました。イテレータの実装は、reverse_iterator の実装が参考になりました。

各関数については、リファレンスと Clang、GCCのソースを参考に実装しました。

実装した内容

データ構造

vectorは固定長の配列にデータを追加・削除していきます。

データの数が配列の長さを超える場合、配列を再確保します。 再確保する長さは、現在の配列の長さ * 2 になります。

メンバ変数

3つのポインタとAllocatorを持ちます。

3つのポインタは、以下の要素へのポインタです。

1. 配列の先頭要素（first）
2. データの末尾 + 1の要素（last）
3. 確保した領域 + 1の要素（capacity_last）

ポインタにすることで、引き算によって、データの要素数と領域を確保してる要素数を求められます。

Allocator（alloc）はメモリの確保/解放、オブジェクトの構築/破棄を行うためのクラスです。ユーザが独自に実装できるよう、クラスになっています。

関数の実装

リファレンス、ソースを参考に関数を実装していきます。

関数の実装にあたりハマった点について書きます。

コンストラクタの引数

C++98において vectorのコンストラクタの定義 は以下です。

// default
explicit vector (const allocator_type& alloc = allocator_type());
// fill
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());
// range
template <class InputIterator>
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());
// copy
vector (const vector& x);

このまま実装すると、fillコンストラクタとrangeコンストラクタの引数が区別が付きません。

（テンプレート引数InputIteratorはイテレータでなくても良いため）

このため、課題で実装を指定されている enable_if と is_integral を使い、引数が整数型でないときだけ、rangeコンストラクタがオーバーロードの候補に入るようにしました。

• Clang では enable_if を使っています。
  GCC では __is_integer という is_integral 相当の構造体を使って処理を切り替えています。

vector::insertでのconstruct or コピー

vector::insert でconstructするかコピーするかがありました。

配列の再確保が必要な場合、各要素をconstructします。 再確保が不要な場合、すでにconstructした要素はコピーし、constructしていない要素のみconstructします。

• 42Tokyoの学生 dai65527 さんのテストを試しに実行してみて、このことに気づきました。

  github.com

要素追加/削除による実行速度

Clangではコンパイルフラグに -std=c++98 と指定しても、insert/eraseによる要素の移動に std::move を使用するようです。

今回の再実装では、規格がC++98と指定されておりstd::moveを使えません。要素の移動が多く発生すると実装元との速度差が20倍を超えてしまいます。

これはどうしようもない……と思うので、速度差が出ないようなテストを書きました。
具体的には、begin() ではなく end()/end()-1 にinsert/eraseするようにしました。

終わりに

vectorを実装して、コンテナとデータ構造の理解が深まりました。

C++98でvectorを実装することは課題以外にあまり無いと思うのですが、この記事が参考になれば幸いです。

42Tokyoでの2021年10月振り返り

エンジニア養成機関、42Tokyo での活動について知ってもらうために、10月に42Tokyoであったことについて振り返る記事です。

自分が取り組んでいる課題や、行われたイベント、課題外の活動について振り返ります。

やったこと

42Tokyoの課題

C++98でコンテナクラスの再実装をする課題

8月からC++98でvector, map, stackなどのコンテナクラスを再実装する課題に取り組んでいます。

10月はstackとボーナスのsetを実装しました。

ここまでにかかった時間は約108時間（10月で10時間）です。後述するリファクタリングの課題をやっていたので、この課題にあまり取り組めていません。

与えられたコードをリファクタリングする課題

オランダの42、Codamで開催されたイベント「Masterclass: Clean Code」の動画を見てリファクタリングの手法を学び、与えられたコードをリファクタリングする課題です。

www.youtube.com

42ではリファクタリングが主目的の課題が無かったので、良かったなあと思います。

イベント

植山類さんの第2回講演

10/02にYouTube Liveにて行われた植山類さんの講演に参加しました。

講演は全2回で、9月に第1回が行われました。

今回の講演のテーマは「並行プログラミングとリンカの最適化」について。

植山さんが作られたリンカ mold の高速化手法について教えてくださいました。

詳細な内容は、りょうさんが記事にまとめられています。

ryo-manba.hatenablog.com

また、YouTubeでアーカイブ動画が公開されていますので、そちらを参照いただければと思います。

www.youtube.com www.youtube.com

その他の活動

統計WEBの輪読会

10月から始まった 統計WEB の輪読会に参加しています。

毎週3-4人で集まって、学んだことを毎週交代で発表しています。

自分の発表週では、相関係数について発表しました。相関係数は『人工知能のための数学がわかる本』でも学んだので、良い復習になりました。

Discord bot

42TokyoのDiscordサーバで以前からDiscord botを稼働させています。

学生から、Discord botに犬の画像を投稿するコマンドを追加してほしいと要望があり、実装しました。

就活

そろそろ就活しないと……という気持ちになって始めています。

以下のことを行いました。

• ポートフォリオ的なサイト を作成しました。
• 42Tokyoの学生が作った自己分析の課題をして自分を見つめ直しました。

まだ応募活動はしていません。

就活をいつ本格的に始めるか、正直悩んでいます。

42のメインのカリキュラムには、First Circle、Second Circleという2つの段階があります。
最初のFirst Circleでは学生共通で基礎的なことを学びます。
First Circleの課題を全て終えた後、Second Circleに入ります。Second Circleでは自由に課題を選択できるようです。

カリキュラムでは、Second Circleに入ってから就活を開始するのを想定しているように思います。
というのも、Second Circleにパートタイムやインターンをする課題があるからです。

ただ42Tokyoでは2020年6月の開校以来、Second Circleに到達した学生はまだいません。
自分はFirst Circleの課題があと3つ残っており、Second Circle到達には少なくとも半年かかると思っています。
この先のFirst Circleの課題には、NginxのようなWebサーバをC++で実装する課題、オールTypeScriptでオンラインゲームを作成する課題があって、とても面白そうなのですが、これ以上職歴に空白期間が開くのもなあと思い、悩んでいます。

とりあえず、課題と並行して少しずつ就活を進めていきたいと思います。

アウトプット

はてなブログに3つ、Qiitaに1つ記事を書きました。

nafuka.hatenablog.com nafuka.hatenablog.com nafuka.hatenablog.com qiita.com

コミット時間

今月のコミット時間は179時間44分、1日平均5時間47分でした。

コミット時間の推移は以下です。

その他（ボイスチャットなど）が増えて課題のコミット時間が減ってるので、課題に取り組む時間をもっと増やしていきたいと思います。

今後やること

11月上旬までにコンテナクラスの再実装を終わらせ、その後NginxのようなWebサーバの実装課題に取り組む予定です。

Discord botで犬の画像を送信するコマンドを作成しました

はじめに

先日、Discordサーバのユーザから、自作のDiscord botに犬の画像を送信するコマンドを追加してほしいと要望があり、実装することにしました。

この記事では、API選定、実装について簡単に紹介します。

API選定

Dog API にしました。

候補

Dog API

• 良いところ：画像を PullRequest で受け付けている。フォーマットが誤ってる場合Closeされるようなので、画像の質が保たれていると思う。
• 気になるところ：Rate limitについて書かれていない。

The Dog API

• 良いところ：リクエストをどれだけ受け付けるか書いてある（Freeで10000リクエスト/月）。
• 気になるところ：画像を気軽にアップロードできるので、Dog APIより質が低そう。
  • 系列？のサービス The Cat API を使っているが時々、色を反転しただけの外れ画像があったりする。

Rate limitについては、Discord側でも連投制限があるので多分大丈夫だろう……ということで、Dog APIを使ってみることにしました。

実装

自作Discord botはPython + discord.pyで作られています（discord.pyは 開発を停止 していますが、一旦様子見でdiscord.pyを使っています）。

犬画像を送信するコマンドを作成するため、discord.py に犬画像送信コマンド用の Cog を追加しました。

既存のコマンドに猫画像を送信するコマンドがあり、動物くくりでCogをまとめることも可能でした。
しかし、個別でコマンドをdisableしたい可能性を考え、Cogを別にしています。

犬画像も猫画像も、やることはほぼ同じなため、BaseとなるCogを作成し、それぞれ継承しました。

コード例

BaseとなるCogは以下のような感じです。message.send_image は指定チャンネルに画像を送信する関数です。

src/utils/message.py にメッセージ関係の関数をまとめることで、一括でフォーマットを変更しやすくしています。

import aiohttp
from typing import Any
import discord
from discord.ext import commands
from src.utils import message


class RandomImageBaseCog(commands.Cog):
    def __init__(self, bot: commands.Bot):
        self.bot = bot

    async def send_image(self, channel: discord.channel, url: str, **kwargs: Any) -> None:
        """APIから画像URLを取得しchannelに送信する"""
        json = await self.fetch_url(url, **kwargs)
        image_url = self.get_image_url_from_json(json)
        await message.send_image(channel, image_url)

    async def fetch_url(self, url: str, **kwargs: Any) -> Any:
        """URLをfetchしjsonを返す"""
        async with aiohttp.ClientSession(raise_for_status=True) as session:
            async with session.get(url, **kwargs) as response:
                json = await response.json()
                return json

    def get_image_url_from_json(self, json: Any) -> str:
        """レスポンスのjsonから画像URLを返す"""
        raise NotImplementedError

RandomImageBaseCog を継承する DogCog はこんな感じです。

from typing import Any
import discord
from discord.ext import commands
from src.cogs.random_image_base import RandomImageBaseCog


class DogCog(RandomImageBaseCog):
    ENDPOINT_URL = "https://dog.ceo/api/breeds/image/random"

    @commands.command()
    async def dog(self, ctx: commands.Context) -> None:
        """犬の画像を表示します

        [Dog API](https://dog.ceo/dog-api/) から画像のURLを取得し、表示します"""
        if ctx.author == ctx.bot:
            return
        await self.execute_command(ctx.channel)

    async def execute_command(self, channel: discord.Channel) -> None:
        await self.send_image(channel, self.ENDPOINT_URL)

    def get_image_url_from_json(self, json: Any) -> str:
        return json.get("message")

終わりに

今までは猫画像だけだったのが、犬画像も見られるようになって、より癒されるようになりました。

コマンドを追加して良かったです。

C++98でmapを再実装する

42Tokyo の課題でSTLコンテナの1つ、mapを再実装しました。

この記事では、mapの再実装で学んだことを書きます。

課題の概要、コンテナ・イテレータ・アルゴリズムの基礎的知識について説明した後、mapの実装について説明します。

課題の概要

• 規格
  • C++98。後の規格で非推奨になっても実装が必要。
• 実装する内容
  • STLコンテナ：vector、map、stack（+ set）
    • カッコ内のコンテナを実装するとクリア時にボーナスが付きます。
    • イテレータも実装が必要になります。
  • STLコンテナ以外：iterators_traits、reverse_iterator、equal、pairなど
    • この記事ではSTLコンテナ以外の詳細な実装は取り上げません。
• リファレンス
  • 実装にあたり、cplusplus.com と cppreference.com を参照することができます。

基礎知識

C++では以下の機能を使ってデータの扱いを共通化しています。

• データの格納：コンテナ
• 要素へのアクセス：イテレータ
• データの操作：アルゴリズム

コンテナ

コンテナは動的配列、連結リスト、辞書などのデータ構造を使ってオブジェクトを保持します。

コンテナには次の分類があります。

• シーケンスコンテナ
  • 配列のような直線的なデータ構造。例：list、vector
• 連想コンテナ
  • キーに基づいて探索可能なデータ構造。例：map、set
• コンテナアダプタ
  • 他のコンテナを元にインターフェースを提供。例：stack

今回実装するのは連想コンテナの1つ、mapです。

mapはkeyとvalueのpairを持ち、keyからvalueを取り出すことができます。

イテレータ

コンテナの各要素には添字演算子やイテレータを使ってアクセスします。

イテレータがあることで、コンテナを使う側はコンテナの内部実装を知ることなくコンテナの各要素を操作できます。

操作方法

• ポインタのように *iterator と、 * をつけるとその要素を参照できます。
• ++iterator とすると、現在の要素から次の要素に進みます。
• 後述するカテゴリによって、使える操作は異なります。

イテレータには5つのカテゴリがあり、それぞれで使える演算子が異なります。

• 入力イテレータ
• 出力イテレータ
• 前方向イテレータ
• 双方向イテレータ
• ランダムアクセスイテレータ

mapは双方向イテレータが提供されます。

双方向イテレータは以下の操作を行えます。

操作	式
次の要素に進む	++iter, iter++
前の要素に戻る	--iter, iter--
要素の読み込み、（非constなら）書き込み	*iter
クラスメンバの参照	iter->m
イテレータの比較	iter==iter, iter!=iter

アルゴリズム

アルゴリズムはイテレータを介してコンテナを操作できる関数を提供します。

例えば、以下の関数があります。

• 2つのイテレータの要素が同じか判定する equal
• 2つのイテレータの要素を入れ替える swap
• 2つのイテレータの区間で検索する find

やったこと

データ構造

データ構造は課題で特に指定がありません。

今回はClang、GCCと同じく赤黒木にしました。

実装の詳細はスライドにまとめましたので、こちらを参照ください。
『アルゴリズムイントロダクション』を参考に実装しています。

赤黒木は左と右を間違えると簡単にバグります。
bashの再実装の課題 の時と同じくdotファイルを生成して、ノードの色と位置関係を確認するようにしました。

mapを実装するには単に赤黒木を実装するだけでなく、イテレータにも対応する必要があります。

イテレータ

実装方法

イテレータは iterator を継承して実装しました（iteratorはC++17から非推奨）。

リファレンスを見ても、イテレータは実装依存なため詳しく書かれていません。このため、reverse_iterator を参考に実装しました。

インクリメントとデクリメント

++ で次の要素、-- で前の要素に進みます。

mapは要素を順序づけており、先頭の要素はキーが最小、末尾の要素はキーが最大になります。

次の要素は今よりもキーが大きい要素、前の要素は今よりもキーが小さい要素です。

次の要素の探索（ ++ ）は、今の要素に右の子があるかどうかで処理が異なります。

• 右の子がある場合：右の子から最小（左端）の要素が次の要素です。

  

• 右の子がない場合：今の要素が親の右の子である限り、親をたどります。たどった要素の親が次の要素です。

  

-- は、 ++ の左右を逆にした処理です。

beginとend

mapは begin()、end()で先頭の要素、末尾 + 1の要素を参照するイテレータを返します。

begin() と end() の計算量は定数時間である必要があります。このため木がbeginとendに相当するノードを覚えておく必要があります。

ClangとGCCで実現方法が異なります。

Clang

Clangでは、endはダミーノードで、ダミーノードの左の子がrootになります。

end-1¹ からイテレータを ++ すると、右の子がないので、親をたどってendに到達します。

GCC

GCCでは、headerというダミーノードを持ち、親がroot、左の子がbegin、右の子がend-1を指します。headerがendに相当します。

Clangのように、rootの親をendにすることで、end-1から ++ するとendにたどり着きます。

面白いのはendの親はrootであることです。
これにより、ClangとGCCでは end() を ++ した時の挙動が異なります。

Clangでは、endの親はNULLなのでSegmentation Faultになります。

GCCでは、endから右の子end-1へ行き、そこから最小（左端）の要素になります。

ハマったこと

allocator::rebind

mapのテンプレート引数で指定できるallocatorは pair<const Key, T> を確保するために使われます。

木のノードではありません。木のノードを確保するためには、allocator::rebind を使って異なる型を確保するクラスを取り出す必要があります。

実装するために以下のことをしました。

1. 赤黒木のクラスに、 allocator<pair> から allocator<赤黒木のノード> にallocatorをrebindする型を宣言する
   以下のように定義しました。

   typedef typename Allocator::template rebind<rb_node<T> >::other node_allocator_type;
   

   rb_node は赤黒木のノードのクラスです。

   typedef、typename、template について説明します。

   • typedef：typedef を使うと型の別名（エイリアス）を宣言することができます。
   • typename：テンプレート引数に依存する型は、コンパイル時に型どうか判断できません。typename を使って型であることを明示します。
   • template：allocator::rebind がテンプレートであることを明示するため、 template を使います。

2. 赤黒木のコンストラクタで allocator<pair> を受け取って allocator<赤黒木のノード> にrebindした型のオブジェクトをメンバ変数にセットする。

insert with hint

insert with hintは map::insert のオーバーロードです。

cplusplus.com によると以下のように定義されています。

iterator insert (iterator position, const value_type& val);

C++98とC++11以降の動作

insert with hintはC++98とC++11以降で動作が異なります。

C++98では、positionが挿入する要素の前の場合、挿入時間が最適化されます。

C++11以降では、挿入要素に続く要素をpositionが指している場合、挿入時間が最適化されます。

何故そのような変更がされたかは以下のページが分かりやすいです。

www.open-std.org

C++98の実装だと、multimapのような重複要素を許すコンテナの場合、先頭要素の前に要素を挿入できない問題があったそうです。

実装方法

GCCのソース を参考に実装しました。

valとposition及びposition前後の要素の大小関係を比較し、挿入できるなら挿入します。挿入できない場合、通常のinsertになります。
おそらくこれはC++11な実装なのかなと思います。

C++98な実装が見つけられたら良かったのですが、今回見つけられませんでした。

keyとvalueの比較

lower_boundなどkeyからiteratorを取り出す際、keyとvalue（pair）の比較が必要になります。

ClangとGCCで対処方法が異なります。

• Clangは、keyとvalueを比較できる関数オブジェクト（ __map_value_compare ）を使って比較。

• GCCは、pairからkeyを取り出す関数オブジェクト（ _Select1st ）を使い、pairからkeyを取り出してkey_compare。

GCCの実装だとset等、別のコンテナを実装するときに新たな関数オブジェクトを実装する必要があるため、Clangを参考にした実装をすることにしました。

参考URL・書籍

github.com

github.com

赤黒木

アルゴリズムイントロダクション 第3版 第1巻: 基礎・ソート・データ構造・数学 (世界標準MIT教科書)

GCCの赤黒木の実装について

stackoverflow.com

allocator::rebind

in-neuro.hatenablog.com

stackoverflow.com

---

1. 双方向イテレータでは iter-1 は実装されてないので、あまり良い表現ではないのですが、キーの最大値の要素です。↩