Будет ли разрешена эта оптимизация в реализации std::string?
Я просто думал о реализации std::string::substr, Возвращает новый std::string объект, который мне кажется немного расточительным. Почему бы не вернуть объект, который ссылается на содержимое исходной строки и может быть неявно присвоен std::string? Этакая ленивая оценка фактического копирования. Такой класс может выглядеть примерно так:
template <class Ch, class Tr, class A>
class string_ref {
public:
// not important yet, but *looks* like basic_string's for the most part
private:
const basic_string<Ch, Tr, A> &s_;
const size_type pos_;
const size_type len_;
};
Открытый интерфейс этого класса будет имитировать все операции только для чтения реального std::string, поэтому использование будет беспроблемным. std::string может иметь новый конструктор, который принимает string_ref так что пользователь никогда не станет мудрее. В тот момент, когда вы пытаетесь "сохранить" результат, вы в конечном итоге создаете копию, поэтому никаких реальных проблем со ссылкой на данные и последующим изменением их за спиной не возникает.
Идея в том, что этот код выглядит так:
std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
std::cout << "match!" << std::endl;
}
будет иметь не более 2 std::string объекты построены в общей сложности. Это кажется полезной оптимизацией для кода, который выполняет много строковых манипуляций. Конечно, это относится не только к std::string, но для любого типа, который может вернуть подмножество его содержимого.
Насколько я знаю, никакие реализации не делают этого.
Я полагаю, суть вопроса заключается в следующем:
Учитывая класс, который может быть неявно преобразован в std::string при необходимости, будет ли соответствовать стандарту для автора библиотеки изменение прототипа члена для возвращаемого типа? Или, в более общем смысле, имеют ли разработчики библиотеки возможность вернуть "прокси-объекты" вместо обычных объектов в таких случаях в качестве оптимизации?
Я хочу сказать, что это недопустимо и что прототипы должны точно соответствовать. Учитывая, что вы не можете перегружать только возвращаемый тип, это не оставит возможность авторам библиотек воспользоваться этими типами ситуаций. Как я уже сказал, я думаю, что ответ - нет, но я решил спросить:-).
6 ответов
Эта идея является копированием при записи, но вместо того, чтобы COW'измещал весь буфер, вы отслеживаете, какое подмножество буфера является "реальной" строкой. (COW в его обычной форме (использовался?) Использовался в некоторых реализациях библиотеки.)
Таким образом, вам вообще не нужен прокси-объект или изменение интерфейса, потому что эти детали могут быть полностью внутренними. Концептуально вам необходимо отслеживать четыре вещи: исходный буфер, счетчик ссылок для буфера, а также начало и конец строки в этом буфере.
Каждый раз, когда операция вообще изменяет буфер, она создает свою собственную копию (из начального и конечного разделителей), уменьшает счетчик ссылок старого буфера на единицу и устанавливает счетчик ссылок нового буфера на единицу. Остальные правила подсчета ссылок одинаковы: копировать и увеличивать счетчик на единицу, уничтожать строку и уменьшать счетчик на единицу, достигать нуля и удалять и т. Д.
substr просто создает новый экземпляр строки, за исключением явно заданных начального и конечного разделителей.
Это довольно известная оптимизация, которая широко используется и называется копирование при записи или COW. Основное дело даже не в подстроках, а в простом
s1 = s2;
Теперь проблема этой оптимизации заключается в том, что для библиотек C++, которые должны использоваться на целях, поддерживающих несколько потоков, счетчик ссылок для строки должен быть доступен с помощью атомарных операций (или, что еще хуже, защищен мьютексом в случае целевой платформы). не поставляет атомарные операции). Это достаточно дорого, так что в большинстве случаев реализация простых строк, не относящихся к COW, происходит быстрее.
Смотри GOTW # 43-45:
http://www.gotw.ca/gotw/043.htm
http://www.gotw.ca/gotw/044.htm
http://www.gotw.ca/gotw/045.htm
Что еще хуже, библиотеки, которые использовали COW, такие как библиотека GNU C++, не могут просто вернуться к простой реализации, поскольку это нарушит ABI. (Хотя, C++0x на помощь, так как это все равно потребует удара ABI!:))
Поскольку substr возвращается std::stringнет способа вернуть прокси-объект, и они не могут просто изменить тип возвращаемого значения или перегрузить его (по причинам, которые вы упомянули).
Они могли бы сделать это, сделав string сам по себе может быть подставкой другой строки. Это будет означать штраф памяти для всех использований (для хранения дополнительной строки и двух size_types). Кроме того, каждая операция должна проверять наличие символов или прокси. Возможно, это можно сделать с помощью указателя реализации - проблема в том, что теперь мы делаем класс общего назначения медленнее для возможного граничного случая.
Если вам это нужно, лучший способ создать другой класс, substring, который конструирует из строки, pos и длины, и покрывает строку. Вы не можете использовать его как s1.substr(6), но вы можете сделать
substring sub(s1, 6);
Вам также необходимо создать общие операции, которые принимают подстроку и строку, чтобы избежать преобразования (поскольку в этом весь смысл).
Если и только если вам действительно нужно больше производительности, чем обеспечивает std::string, тогда напишите что-нибудь, что работает так, как вам нужно. Я работал с вариантами строк раньше.
Мое собственное предпочтение состоит в том, чтобы использовать неизменяемые строки, а не копировать при записи, и использовать boost::shared_ptr или эквивалентный, но только в том случае, если длина строки на самом деле превышает 16, поэтому для строкового класса также имеется закрытый буфер для краткости. строки.
Это означает, что строковый класс может иметь небольшой вес.
В моем списке коллекций также есть класс "слайс", который может смотреть на "подмножество" класса, который живет в другом месте, пока целое время жизни исходного объекта не повреждено. Так что в вашем случае я мог бы нарезать строку, чтобы увидеть подстроку. Конечно, он не будет завершен нулем, и нет способа сделать его таковым, не копируя его. И это не строковый класс.
Что касается вашего конкретного примера, это сработало для меня:
if (&s1[6] == s2) {
std::cout << "match!" << std::endl;
}
Это может не ответить на ваш вопрос для решения общего назначения. Для этого вам понадобится подстрока CoW, как предлагает @GMan.
То, о чем вы говорите, является (или было) одной из основных функций Java java.lang.String класс ( http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/). Во многих отношениях конструкции Java String класс и C++ basic_string шаблон похожи, так что я хотел бы представить, что написание реализации basic_string шаблон, использующий эту "оптимизацию подстроки", возможен.
Одна вещь, которую вам нужно будет рассмотреть, это как написать реализацию c_str() const член. В зависимости от расположения строки в качестве подстроки другой, может потребоваться создать новую копию. Определенно придется создать новую копию внутреннего массива, если строка, для которой был запрошен c_str, не является конечной подстрокой. Я думаю, что это требует использования mutable ключевое слово в большинстве, если не во всех, членах данных basic_string реализация, значительно усложняя реализацию других const методы, потому что компилятор больше не может помочь программисту с правильной константой.
РЕДАКТИРОВАТЬ: На самом деле, для размещения c_str() const а также data() const, вы можете использовать одно изменяемое поле типа const charT*, Первоначально установлено значение NULL, это может быть для каждого экземпляра, инициализировано указателем на новый charT массив всякий раз c_str() const или же data() const вызываются и удаляются в basic_string деструктор, если неNULL,