Давно завидовал #истам и их String...
... а тут меня еще и на раздумья о диапозонах потянуло.
Какая операция над C-строками одновременно частая и O(N) дорогая?
Вычисление длины строки. Особенно некрасиво получается если вы хотите перебрать строку с конца - приходится сначало до этого конца O(N) ехать.
И давно витала идея "а почему бы не хранить длину строки в специальной переменной". Действительно, почему бы и нет? Строки, обычно, занимают заметно больше 4-х байтового int, зато выростет производительность и по функции не надо будет таскать временную переменную с длиной строки.
Был и недостаток: принцип инкаспуляции не позволяет нам "выдавать" во вне класса хранилище строки. Вроде бы ничего страшного - можно наплодить друзей и методов.
Еще один недостаток: мы ограничиваем размер строки. Правда, ограничиваем где-то числом в 4Гб, что имеет смысл лишь на 64-битных системах. А на них и
Тем более, что позже придумали итераторы. А также в STL вошли алгоритмы.
И обнаружились два недостатка:
1. В алгоритмах диапозон указывается двумя итераторами на начало и конец, но проверка корректности, то есть принадлежности итераторов одному контейнеру и правильной последовательности, не производится.
Кроме того, такая передача неудобна с точки зрения наглядности кода:
Запись
copy(it1, it2, it3);
код не украшает.
2. В реализации алгоритмов почти повсеместно используется идиома просмотра последовательности
for(iterator = begin; iterator != end; ++iterator) (кстати, если вычислять end() как begin + length и не поставить const получиться небольшое падение в скорости)
Такая запись удобна и с точки зрения производительности: операция итерации заменяется на разыменование. Но тут совсем не используется длина! Зачем же мы ее хранили.
Самое смешное, что длина нужна чтобы
1. организовать цикл с итерацией
2. получить доступ с конца строки
3. Определить размер буфера.
И только для 3-го пункта нужна именно длина. Для первых двух лучше подойдет указатель на конец буфера.
Итак, вместо указателя на начало сопряженного с длиной, мы храним два указателя - на начало и конец.
А поддиапозон, можно получить просто поставив указатели на родительский диапозон. Только для этого требуется константность хранилищ объектов. Проще говоря, семантика copy on write, либо неизменность контейнеров.
В .NET используется именно второй вариант. Кроме того, из-за отсутсвия проблем с управлением памятью неизменяемые строки почти автоматически становытся безопасны для передачи между потоками. А класс StringBuilder, служащий для изготовления новых строк, в спецификации нагло объявляется себя небезопасным с точки зрения потоков.
Тут у меня все не получается подойти к логическому концу, кроме того, время прижимает. Потому просто дам ссылки на свой код где сделанны #-подобные строки (это не рабочий прототип, просто мазки, вопросами правильного размещения счетчика ссылок я не задавался):
http://www.everfall.com/paste/id.php?4euuxsz84lsi
http://www.everfall.com/paste/id.php?5d42z63wnzdu
http://www.everfall.com/paste/id.php?t9562ixjkdmm
Какая операция над C-строками одновременно частая и O(N) дорогая?
Вычисление длины строки. Особенно некрасиво получается если вы хотите перебрать строку с конца - приходится сначало до этого конца O(N) ехать.
И давно витала идея "а почему бы не хранить длину строки в специальной переменной". Действительно, почему бы и нет? Строки, обычно, занимают заметно больше 4-х байтового int, зато выростет производительность и по функции не надо будет таскать временную переменную с длиной строки.
Был и недостаток: принцип инкаспуляции не позволяет нам "выдавать" во вне класса хранилище строки. Вроде бы ничего страшного - можно наплодить друзей и методов.
Еще один недостаток: мы ограничиваем размер строки. Правда, ограничиваем где-то числом в 4Гб, что имеет смысл лишь на 64-битных системах. А на них и
Тем более, что позже придумали итераторы. А также в STL вошли алгоритмы.
И обнаружились два недостатка:
1. В алгоритмах диапозон указывается двумя итераторами на начало и конец, но проверка корректности, то есть принадлежности итераторов одному контейнеру и правильной последовательности, не производится.
Кроме того, такая передача неудобна с точки зрения наглядности кода:
Запись
copy(it1, it2, it3);
код не украшает.
2. В реализации алгоритмов почти повсеместно используется идиома просмотра последовательности
for(iterator = begin; iterator != end; ++iterator) (кстати, если вычислять end() как begin + length и не поставить const получиться небольшое падение в скорости)
Такая запись удобна и с точки зрения производительности: операция итерации заменяется на разыменование. Но тут совсем не используется длина! Зачем же мы ее хранили.
Самое смешное, что длина нужна чтобы
1. организовать цикл с итерацией
2. получить доступ с конца строки
3. Определить размер буфера.
И только для 3-го пункта нужна именно длина. Для первых двух лучше подойдет указатель на конец буфера.
Итак, вместо указателя на начало сопряженного с длиной, мы храним два указателя - на начало и конец.
А поддиапозон, можно получить просто поставив указатели на родительский диапозон. Только для этого требуется константность хранилищ объектов. Проще говоря, семантика copy on write, либо неизменность контейнеров.
В .NET используется именно второй вариант. Кроме того, из-за отсутсвия проблем с управлением памятью неизменяемые строки почти автоматически становытся безопасны для передачи между потоками. А класс StringBuilder, служащий для изготовления новых строк, в спецификации нагло объявляется себя небезопасным с точки зрения потоков.
Тут у меня все не получается подойти к логическому концу, кроме того, время прижимает. Потому просто дам ссылки на свой код где сделанны #-подобные строки (это не рабочий прототип, просто мазки, вопросами правильного размещения счетчика ссылок я не задавался):
http://www.everfall.com/paste/id.php?4euuxsz84lsi
http://www.everfall.com/paste/id.php?5d42z63wnzdu
http://www.everfall.com/paste/id.php?t9562ixjkdmm