Будет ли разрешена эта оптимизация в реализации std :: string? - PullRequest
7 голосов
/ 13 января 2011

Я просто думал о реализации 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 ]

6 голосов
/ 13 января 2011

Это идея copy-on-write , но вместо того, чтобы COW'ing весь буфер, вы отслеживаете, какое подмножество буфера является "реальной" строкой. (COW в его обычной форме был (есть?) Использован в некоторых реализациях библиотеки.)

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

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

substr просто создает новый экземпляр строки, за исключением явно заданных начального и конечного разделителей.

3 голосов
/ 13 января 2011

Это довольно известная оптимизация, которая относительно широко используется, называется копирование при записи или 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! :))

1 голос
/ 13 января 2011

Поскольку substr возвращает std::string, невозможно вернуть прокси-объект, и они не могут просто изменить тип возвращаемого значения или перегрузить его (по причинам, которые вы упомянули).

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

Если вам это нужно, лучший способ - создать еще один класс, substring, который состоит из строки, позиции и длины, а также из кавычек в строку. Вы не можете использовать его как s1.substr(6), но вы можете сделать

 substring sub(s1, 6);

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

0 голосов
/ 13 января 2011

Если и только если вам действительно нужно больше производительности, чем обеспечивает std :: string, тогда напишите что-нибудь, что работает так, как вам нужно. Я работал с вариантами строк раньше.

Я предпочитаю использовать не изменяемые строки, а не копировать при записи, и использовать boost :: shared_ptr или эквивалентный, но только когда длина строки на самом деле больше 16, поэтому класс строки также имеет закрытый буфер для коротких строк.

Это означает, что класс строки может иметь небольшой вес.

У меня также есть в моем списке коллекций класс «слайс», который может смотреть на «подмножество» класса, который живет в другом месте, пока целое время жизни исходного объекта не повреждено. Так что в вашем случае я мог бы нарезать строку, чтобы увидеть подстроку. Конечно, он не будет нулевым, и нет способа сделать его таковым, не копируя его. И это не строковый класс.

0 голосов
/ 13 января 2011

То, о чем вы говорите, является (или было) одной из основных функций класса java.lang.String в Java (http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/).). Во многих отношениях конструкции класса String в Java и шаблона basic_string в C ++аналогично, поэтому я думаю, что написание реализации шаблона basic_string с использованием этой «оптимизации подстрок» ​​возможно.

Одна вещь, которую вам нужно будет рассмотреть, - это как написать реализацию c_str() constчлен. В зависимости от расположения строки в качестве подстроки другой, может потребоваться создать новую копию. Определенно потребуется создать новую копию внутреннего массива, если строка, для которой был запрошен c_str, не является завершающейподстрока. Я думаю, что для этого необходимо использовать ключевое слово mutable в большинстве, если не во всех, элементах данных реализации basic_string, что значительно усложняет реализацию других методов const, поскольку компилятор больше не может помочьпрограммист с правильной константой.

РЕДАКТИРОВАТЬ: На самом деле, в соответствииommodate c_str() const и data() const, вы можете использовать одно изменяемое поле типа const charT*.Первоначально установленный на NULL, он может быть для каждого экземпляра инициализирован указателем на новый массив charT всякий раз, когда вызывается c_str() const или data() const, и удаляться в деструкторе basic_string, если не NULL.

0 голосов
/ 13 января 2011

Что касается вашего конкретного примера, это сработало для меня:

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

Это может не ответить на ваш вопрос для решения общего назначения.Для этого вам понадобится подстрока CoW, как предлагает @GMan.

...