string

この記事は陳腐化しました。C++11 から Copy on Write は実装禁止になりました。g++4.5 以降でも消えました。但し、終端文字を必要とする仕様は健在です。

(2013/08/25 追記)

std::stringを参照渡しにすると高速化した。何を言っているのか（ｒｙ

なんて記事を見ると改めてstringの扱いはハマるとこ多いよなあと感じる。結論から言うと可能な限りconst&やiterator-pairを使えばいいんですが。

stringは一つの文字列プールを指す文字列クラスで、vectorと次の点で似ています。

連続したアドレス上に保管される
メモリは自動で管理される（大抵は一定量から倍々）
要素に’\0’（NULL文字）を使用可能

但し、その実装は処理系によって結構違います。細かいところまでは読んでいませんが、大まかにvcとgccの実装の特徴を紹介します。

g++4.3.4

実装の特徴は、

格納する文字列に必要なプールは常にアロケータから確保
プールにCopy on Write(CoW)の実装

stringのコピーの際に文字列プールを共有（参照カウント）して不要な複製をコストを削減しています。以下捕捉です。

sizeof(string)がプールへのポインタ一つ分なので引数の受け渡しなどで有利
非constの添字アクセスはほんのちょっと余計な処理が入るかも
空文字列は専用のプールが用意されており領域の確保は起きない
文字列定数は必ずコピーされる
常に終端文字が入っている

実際に変更しなくても、非constで要素にアクセスしたときプール全体のコピーが発生するので、コピーを回避するにはconst必須です。

VC2010

実装の特徴は、

終端文字を含めて16B以下はstringのインスタンス内に入る
それ以上はアロケータから確保

16B以下（15文字/wstringなら7文字）の文字列の生成や結合が高速です。短い文字列を大量に扱う場合特に効果を発揮します。以下捕捉です。

sizeof(string)は16B+3ポインタ分と大きめ（Debugビルドでは+1ポインタ）
文字列定数は必ずコピーされる
常に終端文字が入っている

主観的な意見

コピーを回避したいならconst&やshared_ptrを使うので、CoWは余計なお節介だと思います。しかもゲームなど応答性が必要な場合、遅延実行の発動タイミングを意識する必要あります。というか長い文字列を扱う場合は別のクラスを使った方が無難です。個人的にはメモリプールの管理と文字列ポリシーを分けてアダプタで繋ぐような実装が欲しいです。

どちらも常に終端文字が入っていますが、本来C形式である必要はなく、それ故data()とc_str()が用意されています。Cと親和性が必要でない限りc_str()は使わなくていいので、特にvcで16文字格納できないのはちょっと勿体無く感じます。またCの関数にdata()を突っ込んでも動くので誤解される原因でもあります。実際は仕様上の制約でデメリットが大きいため終端文字を付けない実装は見たことがありませんが。

ついでに検査用のソースも載せておきます。でも細かい実装は読んだ方が分かり易いです。

#include <iostream>
#include <string>
using namespace std;
int main() {
	string s1, s2 = "a";

	cout << "size of string: "
	     << sizeof(s1) << endl;
	cout << "initial capacity: "
	     << s1.capacity() << endl;

	while ((char*)&s1 <= s1.data() && s1.data() < (char*)(&s1 + 1))
		s1 += s2;
	cout << "capacity inside of string: "
	     << (int)s1.size()-1 << endl;

	s1 = s2;
	cout << "copy on write: "
	     << (s1.data() == s2.data()) << endl;

	return 0;
}

周知のGo言語、Google社員によって作られた変だけど実用的な言語。と思ってます。公式サイトに十分に情報が乗っているので参考書には困りません。英語が難しいなら日本語訳している情報サイトもあります。プログラミング言語Goの情報サイト
これからちょくちょく勉強して行くつもりです。Go言語はアルゴリズムの記述や速度が必要なWebシステムなんかに持って来いな気がします。因みにgcではC++とリンク不可で、Cのみ可だそうです（gccgoは両方可）。尚、GoからC++に、C++からGoに引っ張るのは”まだ”できないそうです。ｗｋｔｋ

主観的に特徴を書くとこんな感じです。

ステートメントが少ない
構文の制約が厳しい（表現の統一）
ビルトイン型/関数が必要十分
動的言語のような柔軟な記述
独特で便利な機構
コンパイルが超高速
実行も速い
並列処理が簡単
豊富な標準パッケージ

正確に知りたい方は他を参照してください。

処理系はgo-windowsもあるけど何かうまい使い方が分からないから今はlinux上のgcで試してみました。

Codeforces #23 A. Youre Given a String…
文字列の中から2回以上出現する部分文字列の最大長を求める。

package main
import "fmt"
func main() {
	var s string
	fmt.Scanln(&s)
	g := 0
	for i := 0; i < len(s); i++ {
		for j := i+1; j < len(s); j++ {
			k := 0
			for j+k < len(s) && s[i+k] == s[j+k] { k++ }
			if g < k { g = k }
		}
	}
	fmt.Println(g)
}

特に変な機構も使ってないので構文しか分かりませんが。。次に比較用にC++で、

#include <iostream>
#include <string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int g = 0;
	for(int i = 0; i < s.size(); ++i)
		for(int j = i+1; j < s.size(); ++j)
		{
			int k = 0;
			while(j+k < s.size() && s[i+k] == s[j+k]) k++;
			g = max(g, k);
		}
	cout << g << endl;
	return 0;
}

IDEで書けると非常に楽しそうです。特にパースが速いなら快適な補完が利きそう。でもデバッガは難しそうですね。

ぬるてく

[obsolete] stringの実装(vc,g++)と扱い方

g++4.3.4

VC2010

主観的な意見

Go言語使いたい