Быстрое сложение строк

Имеем, класс для строки символов. Достаточно простой класс, который может хранить и отдавать строку:

class S{
	int size;
	char *buff;
public:
	S() {buff=0;size=0;}
	S(const char *t) {size=strlen(t); buff=strdup(t);}
	~S() {free(buff);}
	char *data() {return buff;}
};

Нам хочется научится складывать разные строки друг с другом. Первая очевидная реализация которую можно нарисовать, может выглядеть приблизительно так:
class S{ ... public: ... S(const S& obj) { // copy size=obj.size; buff=strdup(obj.buff); } ~S() { // free free(buff); } friend S operator+(S &s1,S &s2) { // cond S res; res.size=s1.size+s2.size; res.buff=(char*)malloc(res.size+1); strcpy(res.buff,s1.buff); strcat(res.buff,s2.buff); return res; } };

Использовать полученные операции очень просто:

S s1("one!"); S s2("two!"); S s3("tree!"); S s=s1+s2+s3;

strcat1.cpp

Посмотрим внимательно на последовательность операций, которую выполняет программа. Серым помечены, создание исходных строк и уничтожение результата:

new: one! new: two! new: tree! con: one! + two! copy: one!two! del: one!two! con: one!two! + tree! copy: one!two!tree! del: one!two!tree! del: one!two! one!two!tree!

Довольно много лишних действий. Можестсво копирований, удалений и выделений памяти. Тем более что в 2003 Visual Studio и выше распределитель памяти был вырезан и выделение работает дико медленно.

Жуть?. Во многих реализациях STL всё на самом деле ещё хуже.

Эпизод первый - Ускорение

Попробуем избавиться лишних операций. Создадим некий класс 'конкатенатор', который накапливает информацию соединяемых строках и оптимизирует действия строк:

static Concat operator+(S &s1,S &s2) {return Concat(s1,s2);}
struct Concat{
	S &s1;
	S &s2;
	Concat(S &s1,S &s2):s1(s1),s2(s2) {}
};

class S{
	...
public:
	...
	void operator=(Concat &con) {
		size=con.s1.size+con.s2.size;
		buff=(char*)realloc(buff,size+1);
		memcpy(buff,con.s1.buff,con.s1.size);
		memcpy(buff+con.s1.size,con.s2.buff,con.s2.size);
		buff[size]=0;
	}
};

Пример использования всё такой же:
S s1("test1"); S s2("test2"); S s =s1+s2;
Итак класс Concat запоминает и отдаёт информацию о строчках, которые мы соединяем. Пока он работает только для двух строк и заметного преимущества у нас нет. Разве что избавились от копирующего конструктора строки. И результат соединения уже не копируется в строку s, а возникает там сразу.

strcat2.cpp

Действия для множества строк

В идеале и по возможности, запоминать данные хочется на этапе компиляции, не создавая в памяти всяких массивов и списков, которые тратят место и время того же алокатора памяти. Поэтому не обойдётся без противных шаблонов.

template<class T1,class T2>
struct Concat{
	T1 &p1; 
	T2 &p2;
	Concat(T1 &s1,T2 &s2):p1(s1),p2(s2) {}
	int size() {return p1.size()+p2.size();}
	char *set(char *t) {return p2.set(p1.set(t));}
};

class S{
	...
public:
	template<class T1,class T2>void operator=(Concat<T1,T2> &con) {
		sz=con.size();
		ref=(char*)realloc(ref,sz+1);
		*con.set(ref)=0;
	}
	char *set(char *d)
	{
		memcpy(d,ref,sz);
		return d+sz;
	}
};

Есть довольно плохая новость, gcc 3-4 версий, откомпилировать или собрать правильную программу из этого исходника не могут!

Пример использования:
String a("1"),b("22"),c("333"),d("4444"),e("55555"),f("666666"); String r=a+b+c+d+e+f; printf("%s\n",r.data());

Итого, в результате сложения шести строк возникает некий объект, который содержит в себе информацию о всех строках. Строка принимающая этот объект, сразу выделяет нужную память и собирает итоговую строку. Для того чтобы убедиться что всё работает красиво, можно заглянуть в дизасемблер [3.asm]. Если включить оптимизацию по размеру, всё выглядит ещё красивее. Совсем идеальный код получается с помощью gcc (если избавиться от шаблонов, для получения работающего варианта).

Эпизод 2 - Использование чужих строк

Допустим мы не хотим использовать свои строки, а хотим использовать строки из STL или Qt. Самый простой способ, который приходит в голову, создать свой объект, унаследованной от нужной строки. Такой вариант тоже допустим (не буду тратить время на его описание). Есть второй путь. Создадим объект который складывает чужие объекты, и приделаем к нему операцию преобразования в нужному объекту: Посмотрим что можно сделать в STL строкой:

template<class T1,class T2>
struct concatenator{
	typedef std::string::iterator itt;
	T1 &p1;
	T2 &p2;
	concatenator(T1 &s1,T2 &s2):p1(s1),p2(s2) {}
	int size() {return p1.size()+p2.size();}
	template<class T1,class T2>
	itt set(concatenator<T1,T2>*obj,itt it) { 
		return set(&obj->p2,set(&obj->p1,it));
	}
	itt set(std::string*s,itt it) {
		return std::copy(s->begin(),s->end(),it);
	}
	operator std::string() {
		std::string obj;
		obj.resize(p1.size()+p2.size());
		set(this,obj.begin());
		return obj;
	}
};

template<class T>static std::concatenator<T,std::string>operator+(T &a,std::string &b) {
	return std::concatenator<T,std::string>(a,b);
}

Пример использования:
std::string a("1"),b("22"),c("333"),d("4444"),e("55555"),f("666666"); std::string r=a+b+c+d+e+f;

Работает так же хорошо. Ни одного лишнего выделения памяти. Прилагается готовый вариант программы, а так же его усовершенствованный вариант (добавлена работа с char*). К сожалению ни один из них пока не заставил работать в gcc, последний так же не компилируется в Visual Studio 6.0.

Итог

В расширениях STL есть такой замечательный класс под назанием rope, который делает почти тоже самое (хотя совсем другое). Так что, напоследок, первый краткий полуфабрикат для применения STL строк:

concat.h

[Proteus 11.02.2009] icq:133575351 lawnmower-man@mail.ru