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

TsudaNobuhide

文字列クラス（難易度：★★★★☆）

問題

標準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．１文字を末尾に追加するメンバ関数 void push_back(char ch)
4．ix 番目文字の参照を返す char& operator[](int ix)
5．要素数を返すメンバ関数 size_t size()

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

[java] #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;
}
[/java]

ヒント

・コンストラクタではデータ領域を確保し、そのアドレスを m_data に格納するんだぞ。
・デフォルトのデータ領域サイズは INIT_CAPA + 1 だぞ。
・文字列の最後はヌルターミネイトされているので、データ領域の最初に ‘¥0’ を入れるのを忘れずに。
・m_size は 0 に、m_dataSize は確保したバイト数に初期化するんだぞ。
・reserve(size_t capa) では、最初に capa と現在の容量を比べ、capa がそれ以下であれば何もする必要はないぞ。
・capa が大きい場合は、データ領域を再確保し、旧データ領域からテキストデータをコピーするんだぞ。
・最後のヌルターミネイトを忘れずに。
・push_back(char ch) では、最初にデータ領域サイズをチェックし、足りない場合は reserve() で領域を確保するんだぞ。
・データ領域が足りていれば、文字列末尾に ch を追加する。このときヌルターミネイトを忘れずに。
・また、m_size の更新も忘れずに。
・operator[](int ix) は m_data[ix] を返すだけだぞ。
・size() 関数は m_size を返すだけだぞ。

解答例

[java] MyString() { // デフォルトコンストラクタ
m_size = 0; // 要素数を0に
m_data = new char[m_dataSize = INIT_CAPA + 1]; // データ領域作成
m_data[0] = ‘\0’; // ヌルターミネイト
}
void reserve(size_t capa) {
if( capa >= m_dataSize ) { // capa が現在の容量より大きい場合
auto ptr = m_data; // 現在の領域へのポインタを保存
m_data = new char[m_dataSize = capa + 1]; // データ領域再確保
for(int i = 0; i != m_size; ++i) m_data[i] = ptr[i]; // 元の文字列をコピー
m_data[m_size] = ‘\0’; // ヌルターミネイト
delete [] ptr; // 古いデータ領域メモリを開放
}
}
void push_back(char ch) {
if( m_size + 1 >= m_dataSize ) // データ領域サイズが足りない場合
reserve(m_dataSize * 2); // データ領域サイズを倍に
m_data[m_size++] = ch; // 末尾に文字を追加
m_data[m_size] = ‘\0’; // ヌルターミネイトを忘れずに
}
char& operator[](int ix) {
return m_data[ix];
}
size_t size() const {
return m_size; // メンバ変数で保持している要素数を返すだけ
}
[/java]

解説

デフォルトコンストラクタではデータ領域を確保し、そのアドレスを m_data に格納する。データ領域サイズのデフォルトは、ヌルターミネイトの分が必要なので INIT_CAPA+1 となる。
文字列データはヌルターミネイトさいれているので、領域の最初に ‘¥0’ 格納し、 m_size, m_dataSize の初期化を忘れずに行うようにする。

reserve(size_t capa) では、最初に capa と現在の容量を比べ、capa がそれ以下であれば何もする必要はない。
capa が大きい場合は、データ領域を再確保し、旧データ領域からテキストデータをコピーする。このとき、ヌルターミネイトの ‘¥0’ を忘れてはいけない。

push_back(char ch) では、最初にデータ領域サイズをチェックし、足りない場合は reserve() で領域を確保する。
上記処理でデータ領域は十分なはずなので、文字列末尾に ch を追加する。そして毎度のことだが、ヌルターミネイトの ‘¥0’ を忘れてはいけない。また、m_size のインクリメントも忘れないようにする。

char& operator[](int ix) は m_data[ix] を返すだけだ。

size() 関数は m_size を返すだけだ。