Будет ли разрешена такая оптимизация при реализации std::string ?

StackOverflow https://stackoverflow.com/questions/4682603

Вопрос

Я просто думал о реализации 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 при необходимости, будет ли соответствовать стандарту для автора библиотеки изменять прототип элемента на возвращаемый тип?Или, в более общем плане, есть ли у авторов библиотек возможность возвращать "прокси-объекты" вместо обычных объектов в таких случаях в качестве оптимизации?

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

Это было полезно?

Решение

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

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

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

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

Другие советы

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

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

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

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 методы, потому что компилятор больше не в состоянии помочь программисту с корректностью const.

Редактировать: На самом деле, чтобы приспособить c_str() const и data() const, вы могли бы использовать одно изменяемое поле типа const charT*.Изначально установлено значение NULL, это может быть отдельный экземпляр, инициализированный указателем на новый charT массив всякий раз, когда c_str() const или data() const вызываются и удаляются в basic_string деструктор, если нет-NULL.

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top