*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

пятница, 25 сентября 2009 г.

Эмулятор Радио-86РК на JavaScript

Первым компьютером, на котором я начал программировать, был Радио-86РК. Его собрал мой брат и... понеслась, и несется до сих пор.

Поэтому я до сих пор питаю слабость к данному раритету. К результат этой слабости я постоянно писал эмуляторы этого компьютера.

Первый был под ДОС. Оригинальный сайт сего творения я храню до сих пор в неизменном виде. Этот эмулятор был весьма неплох: там был и встроенный отладчик, и метода взлома игр и т.д. Но ДОС ушел, поэтому данный эмулятор работает теперь разве что в DosBox'e. Исходники творения можно скачать.

Вторая реинкарнация любимого РК была уже под Windows и работала через SDL. Тут уже не было встроенного отладчика, да и проект так и остался сырым (хотя и работающим), поэтому на публике лежит только бинарь с комплектом игр.

И вот, пару дней назад я наткнулся вот на это - эмулятор Спектрума на чистом JavaScript'е! - ни апплетов, ни activex'ов.

Так я от этой темы завелся, что за день-два оживил старого монстра РК на платформе JavaScript. Оказывается правильные браузеры дают весьма недурственную скорость скриптования. 2d графика реализуется через тэг canvas из HTML5.

Получился проект - Эмулятор Радио-86РК на JavaScript.

Эмулятор и набор игр живут в одном единственном файле radio86.html. Можно нажать на ссылку, и эмулятор запустится в браузере. Внизу есть селектор для выбора игры, и возможность поиграться со размерами экрана и скоростью.

Эмуляция происходит на уровне команд процессора Intel 8080.

Скриншот классической игры Volcano, сделанный в этом эмуляторе.



На текущий момент я проверял только в Google Chrome 4.*. Думаю, я не буду заморачиваться особо на тему совместимости с другими браузерами, хотя посмотрим, как пойдет. В IE точно работать не будет, а вот про FF и Оперу ничего сказать не могу, пока.

Волшебный мир Радио-86РК снова вернулся!

P.S. К слову сказать, лучший эмулятор РК (и множества совместимых моделей), что я видел - это эмулятор Виктора Пыхонина. Может и он мигрирует на модную платформу со временем.

Update: Обновил эмулятор до версии 0.2. Изменения незначительные: добавил некоторые системные программы (языки программирования, отладчики, редакторы и т.д.) и немного улучшил селектор выбора игры, который теперь срабатывает при нажатии кнопки "Run".

Update: Обновил эмулятор до версии 0.3. Отрисовка экране теперь работает значительно быстрее и не так грузит процессор.

Update: В версии 0.4 теперь встроенный ассемблер. Можно писать и ассемблировать прямо в окне эмулятора. После есть возможно загрузить результат в сам эмулятор и запустить командой "G" в Мониторе.

Скриншот этого ассемблера:



Update: В версии 0.6 теперь есть встроенный дизассемблер. Им можно просматривать не только программый код, но и данные.

Скриншот дизассемблера:

понедельник, 21 сентября 2009 г.

Двойная точка с запятой в разделе объявления переменных

Казалось бы, невинный пример (vs_double_semicolumn.c):
void main() {
int a;;
int b;
}
Компилируем (в режиме языка С, то есть без /TP):
cl vs_double_semicolumn.c
Результат:
vs_double_semicolumn.c
vs_double_semicolumn.c(3) : error C2143: syntax error : missing ';' before 'type'
Результат в Codegear/Borland примерно такой же (хотя описание ошибки более ясное):
CodeGear C++ 5.93 for Win32 Copyright (c) 1993, 2007 CodeGear
vs_double_semicolumn.c:
Error E2140 vs_double_semicolumn.c 3: Declaration is not allowed here in function main
*** 1 errors in Compile ***
Проблемка заключается в случайной опечатке в виде двойного символа ;. Кстати, пример абсолютно реальный, из жизни. Случайная опечатка - и сразу много вопросов.

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

Проверил на gcc, на родных компиляторах AIX, Solaris и HP-UX. Эти все съели пример без проблем.

Посты по теме:

суббота, 12 сентября 2009 г.

Ошибка в компиляторе Godegear (Borland) C++ при приведении типов указателей

Тривиальный пример (bcc32_5.93_cast_bug.cpp):
class A {};
class C {};
A* a;
A* b = static_cast<C*>(a);
Компилируем в bcc32.exe (версия 5.93) из Codegear RAD Studion 2007:
bcc32 -c bcc32_5.93_cast_bug.cpp
Падает c internal compiler error:
CodeGear C++ 5.93 for Win32 Copyright (c) 1993, 2007 CodeGear
bcc32_5.93_cast_bug.cpp:
Fatal F1004 bcc32_5.93_cast_bug.cpp 4: Internal compiler error at 0x44b34e with base 0x400000
Fatal F1004 bcc32_5.93_cast_bug.cpp 4: Internal compiler error
Люблю собирать падения компиляторов на стадии компиляции. А у вас есть что-нибудь подобное в загашнике?

четверг, 10 сентября 2009 г.

Виртуальные функции в конструкторе и деструкторе

Рассмотрим простой пример (virtual_funct_const.cpp):

#include <iostream>

class A {
public:
A() {
construct();
}

~A() {
destruct();
}

virtual void construct() {
std::cout << "A::construct()" << std::endl;
}

virtual void destruct() {
std::cout << "A::destruct()" << std::endl;
}
};

class B: public A {
public:
B() {
construct();
}

~B() {
destruct();
}

virtual void construct() {
std::cout << "B::construct()" << std::endl;
}

virtual void destruct() {
std::cout << "B::destruct()" << std::endl;
}
};

int main() {
B b;
return 0;
}
Что напечатает эта программа?

А вот что:
A::construct()
B::construct()
B::destruct()
A::destruct()
Получается, что конструкторы и деструкторы классов A и B при вызове объявленных виртуальными функций construct() и destruct() реально вызывали функции только своего класса.

В этом нет никакого секрета, а просто есть правило: виртуальная функция не является виртуальной, если вызывается из конструктора или деструктора.

Правило надо заучивать, что неудобно. Проще понять принцип. А принцип тут в краеугольном камне реализации наследования в C++: при создании объекта конструкторы в иерархии вызываются от базового класса к самому последнему унаследованному. Для деструкторов все наоборот.

Что получается: конструктор класса всегда работает в предположении, что его дочерние классы еще не созданы, поэтому он не имеет права вызывать функции, определенные в них. И для виртуальной функций ему ничего не остается, как только вызвать то, что определено в нем самом. Получается, что механизм виртуальных функций тут как-бы не работает. А он тут действительно не работает, так как таблица виртуальных функций дочернего класса еще не перекрыла текущую таблицу.

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

Итак, виртуальная функция не является виртуальной, если вызывается из конструктора или деструктора.

пятница, 4 сентября 2009 г.

Мультипотоковый отладчик TCP/IP соединений

Трассировка данных, передаваемых по TCP/IP, является весьма частой задачей при разработке сетевых приложений, особенно низкого уровня.

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

Несколько лет назад первые версии моей утилиты были на PHP, но текущая версия переписана на Питоне.

Итак, pyspy.

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

Ни разу не претендую на оптимальность или крутизну использования Питона, поэтому принимаю любую критику.

Основные особенности и возможности:
  • программа "слушает" на указанном порту и перенаправляет траффик на указанные адрес и порт
  • умеет сохранять лог в файл
  • программа является многопотоковой, то есть может принимать сразу несколько входящих содинений
  • механизм записи лога работает также в отдельном потоке, ускоряет работу
Пример использования (для работы по Windows есть специальный скрипт pyspy.cmd).

Запускаем сервер:
pyspy.cmd -a 10.44.5.138 -p 5467 -l 9999 -L trace.log
Запускаем клиента:
telnet localhost 9999
и вводим GET / HTTP/1.0<ENTER><ENTER>

В файле лога и в консоли получаем вот такое:
0000: Listen at port 9999, remote host ('10.44.5.138', 5467)
0000: Connection accepted from ('127.0.0.1', 15223), thread 1 launched
0001: Thread started
0001: Connecting to ('10.44.5.138', 5467)...
0001: Remote host: ('127.0.0.1', 15223)
0001: Recevied from ('127.0.0.1', 15223) (1)
0001: ----: 00-01-02-03-04-05-06-07-08-09-0A-0B-0C-0D-0E-0F
0001: ------------------------------------------------
0001: 0000: 47 | G
0001: Sent to ('10.44.5.138', 5467) (1)
0001: Recevied from ('127.0.0.1', 15223) (13)
0001: ----: 00-01-02-03-04-05-06-07-08-09-0A-0B-0C-0D-0E-0F
0001: ------------------------------------------------
0001: 0000: 45 54 20 2F 20 48 54 54 50 2F 31 2E 30 | ET / HTTP/1.0
0001: Sent to ('10.44.5.138', 5467) (13)
0001: Recevied from ('127.0.0.1', 15223) (2)
0001: ----: 00-01-02-03-04-05-06-07-08-09-0A-0B-0C-0D-0E-0F
0001: ------------------------------------------------
0001: 0000: 0D 0A | ..
0001: Sent to ('10.44.5.138', 5467) (2)
0001: Recevied from ('127.0.0.1', 15223) (2)
0001: ----: 00-01-02-03-04-05-06-07-08-09-0A-0B-0C-0D-0E-0F
0001: ------------------------------------------------
0001: 0000: 0D 0A | ..
0001: Sent to ('10.44.5.138', 5467) (2)
0001: Recevied from ('10.44.5.138', 5467) (379)
0001: ----: 00-01-02-03-04-05-06-07-08-09-0A-0B-0C-0D-0E-0F
0001: ------------------------------------------------
0001: 0000: 48 54 54 50 2F 31 2E 31 20 33 30 32 20 46 6F 75 | HTTP/1.1 302 Fou
0001: 0010: 6E 64 0D 0A 44 61 74 65 3A 20 46 72 69 2C 20 30 | nd..Date: Fri, 0
0001: 0020: 34 20 53 65 70 20 32 30 30 39 20 30 38 3A 35 33 | 4 Sep 2009 08:53
0001: 0030: 3A 30 33 20 47 4D 54 0D 0A 53 65 72 76 65 72 3A | :03 GMT..Server:
0001: 0040: 20 41 70 61 63 68 65 0D 0A 50 72 61 67 6D 61 3A | Apache..Pragma:
0001: 0050: 20 6E 6F 2D 63 61 63 68 65 0D 0A 45 78 70 69 72 | no-cache..Expir
0001: 0060: 65 73 3A 20 46 72 69 2C 20 30 31 20 4A 61 6E 20 | es: Fri, 01 Jan
0001: 0070: 31 39 39 39 20 30 30 3A 30 30 3A 30 30 20 47 4D | 1999 00:00:00 GM
0001: 0080: 54 0D 0A 43 61 63 68 65 2D 63 6F 6E 74 72 6F 6C | T..Cache-control
0001: 0090: 3A 20 6E 6F 2D 63 61 63 68 65 2C 20 6E 6F 2D 63 | : no-cache, no-c
0001: 00A0: 61 63 68 65 3D 22 53 65 74 2D 43 6F 6F 6B 69 65 | ache="Set-Cookie
0001: 00B0: 22 2C 20 70 72 69 76 61 74 65 0D 0A 4C 6F 63 61 | ", private..Loca
...
[обрезано]
...
0001: 0100: 76 3D 31 0D 0A 43 6F 6E 6E 65 63 74 69 6F 6E 3A | v=1..Connection:
0001: 0110: 20 63 6C 6F 73 65 0D 0A 43 6F 6E 74 65 6E 74 2D | close..Content-
0001: 0120: 54 79 70 65 3A 20 74 65 78 74 2F 68 74 6D 6C 0D | Type: text/html.
0001: 0130: 0A 0D 0A 52 65 64 69 72 65 63 74 20 70 61 67 65 | ...Redirect page
0001: 0140: 3C 62 72 3E 3C 62 72 3E 0A 54 68 65 72 65 20 69 | <br><br>.There i
0001: 0150: 73 20 6E 6F 74 68 69 6E 67 20 74 6F 20 73 65 65 | s nothing to see
0001: 0160: 20 68 65 72 65 2C 20 70 6C 65 61 73 65 20 6D 6F | here, please mo
0001: 0170: 76 65 20 61 6C 6F 6E 67 2E 2E 2E | ve along...
0001: Sent to ('127.0.0.1', 15223) (379)
0001: Connection reset by ('10.44.5.138', 5467)
0001: Connection closed
Теперь, собственно, исходник:
#!/usr/bin/python

import socket, string, threading, os, select, sys, time, getopt
from sys import argv

def usage():
name = os.path.basename(argv[0])
print "usage:", name, "-l listen_port -a host -p port [-L file] [-c] [-h?]"
print " -a host - address/host to connect"
print " -p port - remote port to connect"
print " -l listen_port - local port to listen"
print " -L file - log file"
print " -c - supress console output"
print " -h or -? - this help"
print " -v - version"
sys.exit(1)

PORT = False
REMOTE_HOST = REMOTE_PORT = False

CONSOLE = True
LOGFILE = False

try:
opts, args = getopt.getopt(argv[1:], "l:a:p:L:ch?v")

for opt in opts:
opt, val = opt
if opt == "-l":
PORT = int(val)
elif opt == "-a":
REMOTE_HOST = val
elif opt == "-p":
REMOTE_PORT = int(val)
elif opt == "-L":
LOGFILE = val
elif opt == "-c":
CONSOLE = False
elif opt == "-?" or opt == "-h":
usage()
elif opt == "-v":
print "Python TCP/IP Spy Version 1.01 Copyright (c) 2009 by Alexander Demin"
sys.exit(1)
else:
usage()

if not PORT:
raise StandardError, "listen port is not given"

if not REMOTE_HOST:
raise StandardError, "remote host is not given"

if not REMOTE_PORT:
raise StandardError, "remote port is not given"

except Exception, e:
print "error:", e, "\n"
usage()

# Remote host
REMOTE = (REMOTE_HOST, REMOTE_PORT)

# Create logging contitional variable
log_cond = threading.Condition()

queue = []

def logger():
global queue
while 1:
log_cond.acquire()

while len(queue) == 0:
log_cond.wait()

if LOGFILE:
try:
logfile = open(LOGFILE, "a+")
logfile.writelines(map(lambda x: x+"\n", queue))
logfile.close()
except: pass

if CONSOLE:
for line in queue:
print line

queue = []
log_cond.release()

# Thread safe logger
def log(thread, msg):
if CONSOLE or LOGFILE:
log_cond.acquire()
queue.append("%04d: %s" % (thread, msg))
log_cond.notify()
log_cond.release()

def printable(ch):
return (int(ch < 32) and '.') or (int(ch >= 32) and chr(ch))

# Pre-build a printable characters map
printable_map = [ printable(x) for x in range(256) ]

# Thread safe dumper
def log_dump(thread, msg):

if CONSOLE or LOGFILE:
log_cond.acquire()

width = 16

header = reduce(lambda x, y: x + ("%02X-" % y), range(width), "")[0:-1]
queue.append("%04d: ----: %s" % (thread, header))
queue.append("%04d: %s" % (thread, '-' * width * 3))

i = 0
while 1:
line = msg[i:i+width]
if len(line) == 0: break
dump = reduce(lambda x, y: x + ("%02X " % ord(y)), line, "")
char = reduce(lambda x, y: x + printable_map[ord(y)], line, "")
queue.append("%04X: %04X: %-*s| %-*s" % (thread, i, width*3, dump, width, char))
i = i + width

log_cond.notify()
log_cond.release()

# Spy thread
def spy_thread(local, addr, thread_id):
log(thread_id, "Thread started")

try:
log(thread_id, "Connecting to %s..." % str(REMOTE))
remote = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
remote.connect(REMOTE)
except Exception, e:
log(thread_id, "Unable connect to %s -> %s" % (REMOTE, e))
local.close()
return

LOCAL = str(addr)

log(thread_id, "Remote host: " + LOCAL)

try:
running = 1;
while running == 1:

rd, wr, er = select.select([local, remote], [], [local, remote], 3600)

for sock in er:
if sock == local:
log(thread_id, "Connection error from " + LOCAL)
running = 0
if sock == remote:
log(thread_id, "Connection error from " + REMOTE)
running = 0

for sock in rd:
if sock == local:
val = local.recv(1024)
if val:
log(thread_id, "Recevied from %s (%d)" % (LOCAL, len(val)))
log_dump(thread_id, val)
remote.send(val)
log(thread_id, "Sent to %s (%d)" % (REMOTE, len(val)))
else:
log(thread_id, "Connection reset by %s" % LOCAL)
running = 0;

if sock == remote:
val = remote.recv(1024)
if val:
log(thread_id, "Recevied from %s (%d)" % (REMOTE, len(val)))
log_dump(thread_id, val)
local.send(val)
log(thread_id, "Sent to %s (%d)" % (LOCAL, len(val)))
else:
log(thread_id, "Connection reset by %s" % str(REMOTE))
running = 0;

except Exception, e:
log(thread_id, ("Connection terminated: " + str(e)))

remote.close()
local.close()

log(thread_id, "Connection closed")

try:
# Server socket
srv = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
srv.bind(("", PORT))
except Exception, e:
print "error", e
sys.exit(1)

counter = 1

threading.Thread(target=logger, args=[]).start()

log(0, "Listen at port %d, remote host %s" % (PORT, REMOTE))

while 1:
srv.listen(1)
local, addr = srv.accept()
log(0, "Connection accepted from %s, thread %d launched" % (addr, counter))
threading.Thread(target=spy_thread, args=[local, addr, counter]).start()
counter = counter + 1
Лично я постоянно использую этот скрипт на Windows, Linux и Solaris.

Следующий шаг - это переписать все на чистом С в виде одного единственного файла, который можно было бы в течение минуты забросить на любой UNIX или Windows, скомпилить и получить готовую программу. Питон - это конечно здорово, но, например, для AIX или HP-UX Питон является небольшой загвоздкой, которую в пять секунд не решить.

А что стоит у вас на вооружении по этому вопросу?

четверг, 3 сентября 2009 г.

Google Code Jam Qualification Round 2009

Остается еще часов двенадцать до окончания квалификационного раунда Google Code Jam 2009.

Выполнив задачи A (Alien Language), B (Watersheds) и малую размерность задачи C (Welcome to Code Jam) я успешно сел в лужу на большой размерности задачи С. У меня там и не пахло отведенными 8 минутами на прогон данных. Сейчас ищу проблему, но поезд ушел -- на решение большой размерности дается только одна попытка.

Традиционный вывод: Good algorithms are better than supercomputers.

В итоге, пока я на почетном пенсионерском 1784-ом месте с 76-ю баллами (под именем begoon) из около 5700 всех участников.

Радует, что в топовой двадцатке три российских флага.

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

Забавно, через 3-4 часа после начала забега у них там что-то упало, и нельзя было скачать задания. Быстро все починили, но продлили время для участников на пару часов.

Кто-нибудь учавствует?

вторник, 4 августа 2009 г.

Хорошо ли использовать std::string?

Я регулярно имею споры с коллегами на тему стоит ли повсеместно использовать std::string, или таки надо реализовывать свой класс для строчек.

Один из вопросов - это вопрос качества самой реализации std::string. Забавно, что большинство людей, которых я просил набросать прототип класса для строчек, более менее эффективного с точки зрения работы с памятью, писали примерно следующее:
class String {
public:
explicit String(const std::string& value) {
init(value.c_str(), value.length());
}
String(const String& value) { init(value.data_, value.sz_); }
~String() { free(data_); }

String& operator=(const String& value) {
if (this != &value) {
if (value.sz_ > sz_) data_ = (char*)std::realloc(data_, value.sz_);
sz_ = value.sz_;
std::memcpy(data_, value.data_, sz_);
}
return *this;
}

private:
void init(const char* data, size_t sz) {
sz_ = sz;
data_ = (char*)malloc(sz_);
std::memcpy(data_, data, sz_);
}
char* data_;
size_t sz_;
};
Ясно, что при такой реализации оператора присваивания строка в плане занимаемой памяти будет только расти. Это сделано специально.

Практически никто сразу не думал о необходимости наличия операции перемещения, например swap. Почему-то наличие конструктора копирования и оператора присваивания считается достаточным.

Что ответить на этот вопрос раз и навсегда для себя самого, я написал тестовую программу. Это программа сортирует массив из длинных строк. Строки представлены четырьмя способами: объект std::string, указатель на std::string, объект самопального класса String (см. выше) и указатель на String.

По предварительным очевидным оценкам работа через указатель должна быть максимально эффективная, так как в данном случае при перемещении объектов физически std::sort() переставляет только указатели, а не сами объекты.

А вот при работе непосредственно с объектами будет интересно сравнить, насколько банальная реализации строки будет уступать std::string.

Итак, std_string.cpp:
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cassert>

#include "gtest/gtest.h"

static const int N = 100;

// Самопальный класс, реализующий хранение строки более менее
// эффективным образом с точки зрения копирования.
class String {
public:
// "explicit" запрещает неявное приведение аргумента, что мы
// могли точно знать, какие конструктор каких классов вызываются.
explicit String(const std::string& value) {
init(value.c_str(), value.length());
}
String(const String& value) { init(value.data_, value.sz_); }
~String() { free(data_); }

// Данный оператор - это, пожалуй, единственная попытка сделать
// работу с памятью эффективной.
String& operator=(const String& value) {
if (this != &value) {
// Память перераспределяется только если оригинал длинее текущей
// строки. Ясно, что при такой реализации строка может только
// расти в плане занимаемой памяти.
if (value.sz_ > sz_) data_ = (char*)std::realloc(data_, value.sz_);
sz_ = value.sz_;
std::memcpy(data_, value.data_, sz_);
}
return *this;
}

friend class StringCmp;
friend class StringPointerCmp;

private:
void init(const char* data, size_t sz) {
sz_ = sz;
data_ = (char*)malloc(sz_);
std::memcpy(data_, data, sz_);
}
char* data_;
size_t sz_;
};

std::vector<std::string> std_strings;
std::vector<std::string*> std_strings_p;
std::vector<String> strings;
std::vector<String*> strings_p;

// Объект для сравнения двух std::string.
class StlStringCmp {
public:
bool operator()(const std::string& a, const std::string& b) {
return a < b;
}
};

TEST(SortingStlString, StlString) {
std::sort(std_strings.begin(), std_strings.end(), StlStringCmp());
}

// Объект для сравнения двух std::string*.
class StlStringPointerCmp {
public:
bool operator()(const std::string* a, const std::string* b) {
return *a < *b;
}
};

TEST(SortingStlString, StlStringPointer) {
std::sort(std_strings_p.begin(), std_strings_p.end(), StlStringPointerCmp());
}

// Объект для сравнения двух String.
class StringCmp {
public:
bool operator()(const String& a, const String& b) {
assert(a.sz_ == b.sz_);
return std::memcmp(a.data_, b.data_, a.sz_);
}
};

TEST(SortingStlString, String) {
std::sort(strings.begin(), strings.end(), StringCmp());
}

// Объект для сравнения двух String*.
class StringPointerCmp {
public:
bool operator()(const String* a, const String* b) {
assert(a->sz_ == b->sz_);
return std::memcmp(a->data_, b->data_, a->sz_);
}
};

TEST(SortingStlString, StringPointer) {
std::sort(strings_p.begin(), strings_p.end(), StringPointerCmp());
}

int main(int argc, char* argv[]) {
// Это наполнитель, чтобы строки были длинные, и копирование было
// ощутимо дорого.
std::string big(1024 * 1024, '?');
for (int i = 0; i < N; ++i) {
// Все строки будут одинаковой длины. Функции сравнения рассчитывают
// на это.
std::stringstream fmt;
fmt << N * 2 - i << big;
// std::string строка-объект.
std_strings.push_back(fmt.str());
// std::string строка-указатель.
std_strings_p.push_back(new std::string(fmt.str()));
// Моя строка-объект.
strings.push_back(String(fmt.str()));
// Моя строка-указатель.
strings_p.push_back(new String(fmt.str()));
}

testing::InitGoogleTest(&argc, argv);
// Принудительно печатаем время работы тестов.
testing::GTEST_FLAG(print_time) = true;
return RUN_ALL_TESTS();
}
Компилируем:
cl /O2 /EHsc /I. std_string.cpp gtest-all.cc
Запускаем:
[==========] Running 4 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 4 tests from SortingStlString
[ RUN ] SortingStlString.StlString
[ OK ] SortingStlString.StlString (203 ms)
[ RUN ] SortingStlString.StlStringPointer
[ OK ] SortingStlString.StlStringPointer (0 ms)
[ RUN ] SortingStlString.String
[ OK ] SortingStlString.String (891 ms)
[ RUN ] SortingStlString.StringPointer
[ OK ] SortingStlString.StringPointer (0 ms)
[----------] 4 tests from SortingStlString (1125 ms total)

[----------] Global test environment tear-down
[==========] 4 tests from 1 test case ran. (1125 ms total)
[ PASSED ] 4 tests.
Видно, что версии с указателями отработали примерно одинаково быстро, а вот при работе с объектами std::string обогнал самопальную реализацию в 4 раза - 203 мс против 891 мс.

Несложно понять, почему это так. std::sort() для перестановки элементов использует шаблонную функцию std::swap(), которая для std::string реализована так, чтобы делать перестановку без физического копирования данных. А для String все происходит банально через конструктор копирования и оператор присваивания.

Вобщем, для себя я вынес, что не надо городить свой огород, так как в большинстве случаев std::string решает все проблемы. Но возникает вопрос - как добавлять в std::string свою функциональность? Например, поиск слов.
Проблема в том, что у std::string деструктор объявлен как невиртуальный (может это сделано по соображениям эффективности), а наследование от класса с невиртуальным деструктором в C++ является не самой правильной затеей.
Автор STL Александр Степанов в своем труде Notes for the Programming course at Adobe советует реализовать дополнительную функциональность для стандартных контейнеров STL через шаблонные алгоритмы. Плюсов тут много, например, реализовав какой-то разбор строки через итераторы в виде шаблонной функции-алгоритма, можно автоматически получить её же для все остальных контейнеров, у которых есть такие же итераторы.

Интересно, что пишет Степанов про свой взляд на то, как надо реализовывать функцию length() для контейнеров (в документе, ссылка на который дана выше, Степанов показывает шаг за шагом процесс создания эффективного контейнера):
While we could make a member function to return length, it is better to make it a global friend function. If we do that, we will be able eventually to define the same function to work on built-in arrays and achieve greater uniformity of design. I made size into a member function in STL in an attempt to please the standard committee. I knew that begin, end and size should be global functions but was not willing to risk another fight with the committee.
Он считает, что глобальная шаблонная функция length() - это правильнее, чем length() как член класса. Если б не комитет стандартизации - так оно и было бы в STL.

Итак, подытоживая сказанное, не стоит не доверять std::string. Для большинства задач этот класс решает все проблемы. Если надо добавить функциональность - это надо делать через реализацию шаблонного алгоритма.

Есть замечания или протесты? Прилагайте.

Посты по теме: