ryo-manba / ft_containers

Reimplementation of STL containers.

👋 Hi there, I'm Ryo Matsukawa

• Frontend Developer.
• Team member at NextUI.
• X(Twitter): @ryo_manba
• LinkedIn: ryo-manba

ft_containers's Issues

[2pt]vector.resize()の実行速度改善

概要

stlの20倍以上かかっている。

対応

• 機能の改善

[1pt]atの例外メッセージ修正

概要

std::out_of_range("vector"); に修正する

[8pt]mapのイテレーター実装

[2pt]InputIteratorを受け取るコンストラクタの作成(vector)

概要

フォワードイテレータの受け取りしか考えていなかった。

対応

InsertなどのInputIteratorを受け取るメソッドに投げる。

[8pt]stdと自作コンテナーの時間を比較するテスト作成

[3pt] mapのヒント付きインサートを挿入先からルートまで辿るように修正する

な…　何を言っているのか　わからねーと思うが　
おれも　何をされたのか　わからなかった…

[5pt]pairの実装

[13pt]mapの木構造実装

AVL or RB どっちにしようか考え中。

[3pt]mapのベンチマークテスト作成

[2pt]subjectのmainを追加する

[8pt]mapの実装

AVL木やイテレーターを用いて各機能を実装する。
リファレンスはこちら

[1pt]ft::swapの削除

std::swapを使って良いから。

[3pt]reverse_iteratorとconst_reverse_iteratorの比較演算ができない

概要

templateで受け取る比較演算が必要

[2pt]vector.data()がない

概要

vector.data()というメソッドがあるらしい。

対応

• 機能の調査
• 実装

[5pt]mapのテスト作成

[3pt]イテレーターを引数に受け取る関数でinput iteratorが来た場合も正しく処理できるか確認する

vectorのinsertが怪しそう。

[1pt]vectorのstd::swap作成

[3pt]vectorのベンチマークテスト作成

[3pt]vector.insert()の実行速度改善

概要

stlの20倍以上かかっている。

対応

• 機能の改善

**Submit前最終チェック**

Submit前確認リスト

• subjectの要件チェック
• vectorの実装漏れチェック
• stackの実装漏れチェック
• mapの実装漏れチェック
• 使用不可の関数を使ってないか？
• leakしてないか？
• guacamoleで動くか？
• 42のリポジトリに提出しているか？

[2pt]InputItを受けるvector.assignの実装忘れ

対応

実装しましょう。

[2pt]vectorの機能テストリファクタ

[5pt]AVL木のイテレーターを実装する。

[1pt]ローカルとGitHub Actionsでvector.capacity()の結果が異なる

対応

• 直接比較しないようにする
• capacityの初期値や増加率などの値は仕様で定められていない

[1pt]pairの機能テストリファクタ

[1pt]insertで複数要素を追加する場合に一括でメモリ確保するよう変更

実効速度早くなる。

[2pt]map.at()の実行速度改善

概要
stlの20倍以上かかっている。

対応

• 機能の改善

[2pt]vector.erase()の実行速度改善

概要

stlの20倍以上かかっている。

対応

• 機能の改善

[2pt]stackのベンチマークテスト作成

[5pt]vectorクラスのリファクタ

概要

可読性が低いのでリファクタする

対応

• https://en.cppreference.com/w/cpp/container/vector を元にメソッドを並び替える
• メソッドの説明を書く
• コメントを書く

[2pt]ベンチマークテストの結果を分かりやすく表示するスクリプトの作成

[1pt]mapのstd::swapの名前空間がftになってる

概要

名前空間 std内に作る必要がある

[1pt]練習用イテレーターの削除

[3pt]mapのoperator=でheap-use-after-freeになる

概要

treeのコピーが上手く行ってなさそう

対応

• operator=の改修

stackのテスト作成

[3pt]pairのテスト作成

[3pt]vectorの仕様確認する

[2pt]第2引数ありのvector.resizeを呼ぶと要素数が1つ多くなる

概要

vector.resize(10);
vector.resize(15, 42);

vector.size(); // 16になる

対応

• 事前に値がある状態でresizeを呼び出した時の挙動調査

[3pt]mapの仕様確認する

[1pt]練習用のツリー削除

[2pt]map.operator[]の実行速度改善

概要

• stlの20倍以上かかっている。

対応

• 機能の改善

[2pt]stackの仕様確認する

[1pt]operator[]、operatorのテスト名を変更する

概要

• operator[] -> operator_at
• operator -> operator_cmp

cpp referenceのURIを見て気づいた。

[1pt]upper_bound、lower_boundをルートから辿るように修正する

概要

現状begin()から見ている。当然遅い。

[3pt]mapの機能テストリファクタ

Iteratorの比較をequalとlexicographical_compareで行うようにする。

friendを使わなくてよくなる。

現在はbase()でcurrentの比較を行っている。
ここで使わないと実装必須のequalとlexicographical_compareの出番がなくなる。

[1pt]vectorのinsert(v.begin(), val)でセグフォする

事例

iterator insert(const_iterator pos, const value_type& value);
そのままposにvalueを代入する処理があった。
capacityがない場合に要素の確保が必要。

対応

その他のinsertと同じような実装に修正する。

[1pt]stackの機能テストリファクタ

[2pt]MakefileでベンチマークとUnitテストそれぞれコンパイルできるようにする

stackの実装