競技プログラミング風 C++問題集【第8回】


目次

文字列クラス(難易度:★★★★☆)

問題

標準C++ライブラリにある文字列クラス string は最もよく使われるクラスのひとつだ。 本問題では、その string の一部の機能をもった MyString 実装していただく。

MyString のデータ構造を下図に示す。

競技プログラミング風C++問題集【第8回】_01

配列要素を格納するデータ領域は new で確保され、m_data がその先頭アドレスを指す。
文字列データの最後には番人として ‘¥0’ が入っているものとする。
文字を追加し、データ領域に文字が入りきれなくなった場合は、より大きいデータ領域を確保しなおし、そこに文字データをコピーする。
それが頻繁に行われないように、データ領域は多めに確保される。 確保された要素数を m_dataSize に、実際に格納されている文字数を m_size で保持する。

上記を理解した上で、テストコードの ToDo 部分にコードを記述し、以下を実装しなさい。

1.MyString のデフォルトコンストラクタ
2.指定キャパシティ+1のサイズまでのデータ領域を確保する void reserve(size_t capa)
3.1文字を末尾に追加するメンバ関数 void push_back(char ch)
4.ix 番目文字の参照を返す char& operator[](int ix)
5.要素数を返すメンバ関数 size_t size()

なお、コンストラクタでは要素が空の文字列オブジェクトを生成するが、確保するデータ領域サイズは INIT_CAPA+1 とする。 また、要素追加時にデータ領域が足りなくなった場合は、 データ領域サイズ(m_dataSize)を以前の倍にするものとする。 ただし、このときメモリ不足になった場合の処理は特に行わないものとする。

#include <iostream>       //  標準入出力ライブラリ
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
#define     INIT_CAPA       7       //  キャパシティ初期値
class MyString {  //  文字列クラス
public:
    MyString() {   //  デフォルトコンストラクタ
        //  ToDo: ここに MyString の初期化コードを記述
    }
    void    reserve(size_t capa) {
        //  ToDo: ここにデータ領域サイズを確保するコードを追加
    }
    void    push_back(char ch) {
        //  ToDo: ここにコードを追加し、文字 ch を末尾に追加
    }
    char&   operator[](int ix) {
        //  ToDo: ここに ix 番目文字への参照を返すコードを記述
        return m_data[0];
    }
    size_t  size() const {
        //  ToDo: ここに要素数を返すコードを記述
        return 0;
    }
    size_t  capacity() const {
        return m_dataSize - 1;
    }
private:
    char*   m_data;         //  データ領域へのポインタ
    size_t  m_size;         //  文字(バイト)数
    size_t  m_dataSize;     //  データ領域サイズ - 1
    
    friend int main();
};
int main() {
    //  デフォルトコンストラクタのテスト
    MyString txt;
    DO_TEST( txt.m_size == 0 );
    DO_TEST( txt.m_dataSize == INIT_CAPA + 1 );
    DO_TEST( txt.m_data != nullptr );
    DO_TEST( txt.m_data[0] == '\0' );
    //  reserve のテスト
    DO_TEST( txt.capacity() == INIT_CAPA);
    txt.reserve(INIT_CAPA/2);
    DO_TEST( txt.capacity() == INIT_CAPA );     //  キャパを減らしても変化しない
    txt.reserve(127);
    DO_TEST( txt.capacity() == 127);
    //  push_back のテスト
    txt.push_back('a');
    DO_TEST( txt.m_size == 1 );
    txt.push_back('x');
    DO_TEST( txt.m_size == 2 );
    DO_TEST( strcmp(txt.m_data, "ax") == 0 );
    for(int i = 0; i < 10; ++i) txt.push_back('A'+i);	//	'A', 'B', ... 'J' を追加
    DO_TEST( strcmp(txt.m_data, "axABCDEFGHIJ") == 0 );
    //	operator[] のテスト
    DO_TEST( txt[2] == 'A' );
    DO_TEST( strcmp(&txt[0], "axABCDEFGHIJ") == 0 );
    txt[2] = '-';
    DO_TEST(strcmp(&txt[0], "ax-BCDEFGHIJ") == 0);
    //  size() のテスト
    DO_TEST( txt.size() == 12 );
    //
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 C++問題集【第16回】

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

競技プログラミング風 C++問題集【第15回】

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

競技プログラミング風 C++問題集【第14回】

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第13回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

競技プログラミング風 C++問題集【第12回】

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

競技プログラミング風 C++問題集【第11回】

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

競技プログラミング風 C++問題集【第10回】

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

競技プログラミング風 C++問題集【第9回】

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

競技プログラミング風 C++問題集【第8回】

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

競技プログラミング風 C++問題集【第7回】

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP