std::stringの実装に学ぶC++入門

#概要
　タイトルの通りです。C言語の標準ライブラリでstd::string(に近いもの)を実装することによって、C++の様々なエッセンスがわかりやすく伝わるのではないかと思って書きました。
　なお、参考資料として、次のページを参照しています。

[C++ 文字列クラス std::string 入門](http://vivi.dyndns.org/tech/cpp/string.html)

#データ構造を決める
　何にせよまず、データ構造をどうするかを決めないといけません。**中がどうなっていようと、ライブラリとして使う分には構わない**というのがカプセル化のご利益ですが、ライブラリを作成する際はそういった**生臭い部分**に触れる必要があります。
　仕様上、**c_str()が呼ばれた際はchar配列の先頭アドレスを返す**必要があります。これは旧来のC言語形式のデータとの互換性を求められたことによるものですが、別形式から変換するよりchar配列をあらかじめ用意した方が**遥かに楽**なので、次のような実装としました。

```sample1.cpp
class String{
// メンバ変数
	size_t m_capacity;	//最大容量
	size_t m_size;		//文字数
	char *m_data;		//文字列
};
```
　なお、m_が付く変数は元々m_を付けていなかったのですが、そうすると**size()やcapacity()やdata()を実装した際に名前が被ってコンパイルできない**という**糞な事態**が起きるので、それを回避するために付けています。

#コンストラクタを実装する
　まず、std::stringの各種コンストラクタを書き出してみます。

|記法|意味|
|---|----|
|省略|空文字列|
|(n,'x')|'x'がn個並んだ文字列|
|char &c|char配列|
|char &f,char &l|[f, l)の範囲のchar配列|
|std::string|**コピーコンストラクタ**|
　その上で、上記を1つづつ実装していきます。

```sample2.cpp
#include <cstring>	//実装用
// コンストラクタ
String::String(){	//省略
	m_capacity = m_size = 0;
	m_data = new char[m_size + 1];
	m_data[0] = '\0';
}
String::String(const size_t n, const char c){	//(n,'x')
	m_capacity = m_size = n;
	m_data = new char[m_size + 1];
	for(size_t i = 0; i < m_size; ++i)
		m_data[i] = c;
	m_data[m_size] = '\0';
}
String::String(const char *c){	//char* c
	m_capacity = m_size = strlen(c);
	m_data = new char[m_size + 1];
	strcpy(m_data, c);
}
String::String(const char *f, const char *l){	//char* f,char* l
	m_capacity = m_size = l - f;
	m_data = new char[m_size + 1];
	strncpy(m_data, f, m_size);
	m_data[m_size] = '\0';
}
String::String(const String &s){	//コピーコンストラクタ
	m_capacity = s.m_capacity;
	m_size = s.m_size;
	m_data = new char[m_size + 1];
	strcpy(m_data, s.m_data);
}
```
#各種演算子を実装する
　std::stringの場合、[]演算子を使ってchar型として1文字づつアクセスすることが出来ます。また、+や+=演算子で文字列を結合することも可能です。
　それらをどう実装するかですが、C++では[演算子のオーバーロード]を使えば可能です。イメージとしては、「plus(a, b)」を「a + b」と置き換えられると考えて下さい。

```sample3.cpp
const char& String::operator[](const size_t n) const{
	return m_data[n];
}
char & String::operator [](const size_t n){
	return m_data[n];
}
String String::operator + (const char *c){
	String retval(*this);
	retval += c;
	return retval;
}
String String::operator + (const String &str){
	String retval(*this);
	retval += str.m_data;
	return retval;
}
String& String::operator += (const char *c){
	size_t new_size = this->m_size + strlen(c);
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	strcpy(this->m_data + this->m_size, c);
	this->m_size = new_size;
	return *this;
}
String& String::operator += (const String &str){
	size_t new_size = this->m_size + str.m_size;
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	strcpy(this->m_data + this->m_size, str.m_data);
	this->m_size = new_size;
	return *this;
}
void String::push_back(const char c){
	size_t new_size = this->m_size + 1;
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	this->m_data[this->m_size]= c;
	this->m_data[this->m_size + 1] = '\0';
	this->m_size = new_size;
}
bool String::operator == (const char *c){
	return m_size == strlen(c) && (memcmp(this->m_data, c, m_size) == 0);
}
```
　なお、+=演算子でcapacityを2倍にしているのは、std::vectorと同じく、**[何度も+=する場合にその方が効率が良い](http://chasen.org/~taku/blog/archives/2007/02/_o1.html)**からです。
#各種メンバ関数を実装する
　以上を実装すれば、とりあえずそこそこ使える文字列クラスになります(機能としては結構端折っているので注意)。後は、各種メンバ関数を実装してみましょう。

```sample4.cpp
bool String::empty() const{
	return (m_size == 0);
}
size_t String::size() const{
	return m_size;
}
size_t String::length() const{
	return m_size;
}
size_t String::capacity() const{
	return m_capacity;
}
const char& String::front() const{
	return m_data[0];
}
const char& String::back() const{
	return m_data[m_size - 1];
}
char& String::front(){
	return m_data[0];
}
char& String::back(){
	return m_data[m_size - 1];
}
String String::substr(const size_t index, const size_t size) const{
	String retval(this->m_data + index, this->m_data + index + size);
	return retval;
}
const char* String::c_str() const{
	return this->m_data;
}
const char* String::data() const{
	return this->m_data;
}
size_t String::find(const char *c, const size_t index) const{
	char *pos = strstr(this->m_data + index, c);
	if(pos == NULL) return String::npos;
	return pos - this->m_data;
}
```
　ちなみに、find関数を使用する際によく見るstd::string::nposは、std::stringクラスでstaticに定義された「-1」なのだそうで。

#まとめ
　もちろん、単に**文字列を効率的に扱いたい際は素直にSTLのstd::stringを利用しましょう**。ただ、こうして再実装してみると、細やかなところまで決められるC++の強みが改めて感じられます。気になる人は、本当のstd::stringの実装を開発環境から読んでみると良いかと(IDEだと関数定義まで簡単にジャンプできるので)。

#おまけ(今回の記事で使用したソース)
```String.cpp
#include <iostream>
#include <cstring>	//実装用
using namespace std;

class String{
// メンバ変数
	size_t m_capacity;	//最大容量
	size_t m_size;		//文字数
	char *m_data;		//文字列
public:
// 定数
	static const size_t npos = -1;
// メンバ関数
	// コンストラクタ
	String();
	String(const size_t n, const char);
	String(const char*);
	String(const char*, const char*);
	String(const String&);
	// デストラクタ
	~String(){
		delete[] m_data;
	}
	// 演算子
	char &operator [](const size_t);
	const char& operator[](const size_t) const;
	String operator + (const char*);
	String operator + (const String&);
	String& operator += (const char*);
	String& operator += (const String&);
	void push_back(const char);
	bool operator==(const char*);
	// 各種メンバ関数
	bool empty() const;
	size_t size() const;
	size_t length() const;
	size_t capacity() const;
	const char& front() const;
	const char& back() const;
	char& front();
	char& back();
	String substr(const size_t, const size_t) const;
	const char* c_str() const;
	const char* data() const;
	size_t find(const char*, const size_t) const;

	void put();
};
// コンストラクタ
String::String(){	//省略
	m_capacity = m_size = 0;
	m_data = new char[m_size + 1];
	m_data[0] = '\0';
}
String::String(const size_t n, const char c){	//(n,'x')
	m_capacity = m_size = n;
	m_data = new char[m_size + 1];
	for(size_t i = 0; i < m_size; ++i)
		m_data[i] = c;
	m_data[m_size] = '\0';
}
String::String(const char *c){	//char* c
	m_capacity = m_size = strlen(c);
	m_data = new char[m_size + 1];
	strcpy(m_data, c);
}
String::String(const char *f, const char *l){	//char* f,char* l
	m_capacity = m_size = l - f;
	m_data = new char[m_size + 1];
	strncpy(m_data, f, m_size);
	m_data[m_size] = '\0';
}
String::String(const String &s){	//コピーコンストラクタ
	m_capacity = s.m_capacity;
	m_size = s.m_size;
	m_data = new char[m_size + 1];
	strcpy(m_data, s.m_data);
}
// 演算子
const char& String::operator[](const size_t n) const{
	return m_data[n];
}
char & String::operator [](const size_t n){
	return m_data[n];
}
String String::operator + (const char *c){
	String retval(*this);
	retval += c;
	return retval;
}
String String::operator + (const String &str){
	String retval(*this);
	retval += str.m_data;
	return retval;
}
String& String::operator += (const char *c){
	size_t new_size = this->m_size + strlen(c);
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	strcpy(this->m_data + this->m_size, c);
	this->m_size = new_size;
	return *this;
}
String& String::operator += (const String &str){
	size_t new_size = this->m_size + str.m_size;
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	strcpy(this->m_data + this->m_size, str.m_data);
	this->m_size = new_size;
	return *this;
}
void String::push_back(const char c){
	size_t new_size = this->m_size + 1;
	if(this->m_capacity < new_size){
		while(this->m_capacity < new_size){
			this->m_capacity *= 2;
		}
		char *new_m_data = new char[this->m_capacity + 1];
		memcpy(new_m_data, this->m_data, this->m_size);
		this->m_data = new_m_data;
	}
	this->m_data[this->m_size]= c;
	this->m_data[this->m_size + 1] = '\0';
	this->m_size = new_size;
}
bool String::operator == (const char *c){
	return m_size == strlen(c) && (memcmp(this->m_data, c, m_size) == 0);
}
// 各種メンバ関数
bool String::empty() const{
	return (m_size == 0);
}
size_t String::size() const{
	return m_size;
}
size_t String::length() const{
	return m_size;
}
size_t String::capacity() const{
	return m_capacity;
}
const char& String::front() const{
	return m_data[0];
}
const char& String::back() const{
	return m_data[m_size - 1];
}
char& String::front(){
	return m_data[0];
}
char& String::back(){
	return m_data[m_size - 1];
}
String String::substr(const size_t index, const size_t size) const{
	String retval(this->m_data + index, this->m_data + index + size);
	return retval;
}
const char* String::c_str() const{
	return this->m_data;
}
const char* String::data() const{
	return this->m_data;
}
size_t String::find(const char *c, const size_t index) const{
	char *pos = strstr(this->m_data + index, c);
	if(pos == NULL) return String::npos;
	return pos - this->m_data;
}

void String::put(){
	cout << m_capacity << "|" << m_size << "|" << m_data << "|\n";
}
int main(){
	// コンストラクタ
	String str; str.put();
	String a10(10, 'a'); a10.put();
	String labo_men1("Okabe"); labo_men1.put();
	char assist[] = "Christina"; String labo_men2(assist, assist + 5); labo_men2.put();
	String l1(labo_men1); l1.put();
	// 演算子
	//[]
	String code(10, ' ');
	for(int i = 0; i < 10; ++i)
		code[i] = static_cast<char>('0' + i);
	code.put();
	//+
	String labo_men3("Mayushi"), ttr(" TTR"); String l3 = labo_men3 + ttr; l3.put();
	String labo_men4("Daru"), sh("SuperHacker"); String l4 = labo_men4 + " is " + sh; l4.put();
	//+=
	String test("t");
	test.put();
	test += "es";
	test.put();
	test.push_back('t');
	test.put();
	if(test == "test"){
		cout << "test == \"test\"" << endl;
	}
	// 各種メンバ関数
	cout << str.empty() << endl;
	cout << labo_men4.size() << endl;
	labo_men4 += ".";
	cout << labo_men4.length() << endl;
	cout << labo_men4.capacity() << endl;
	labo_men4.put();
	cout << labo_men4.front() << " " << labo_men4.back() << endl;
	cout << labo_men4.substr(1, 3).c_str() << endl;
	cout << labo_men3.find("us", 1) << endl;
}
```