qRegexReplace - аналог boost::regex_replace

[m_ax]

В последнее время на форуме частенько возникают темы, в которых поднимается проблема поиска и замены выражений в тексте. И, казалось бы, никаких вопросов  возникать не должно, ведь у нас есть замечательный find/replace прямо из коробки, но.. Но стоит задачу чуть усложнить, т.е. не просто тупо замена одного на другое, а скажем замена по определенному правилу... И вот тут возникают вопросы, плодятся темы [http://www.prog.org.ru/topic_30197_0.html, http://www.prog.org.ru/topic_30885_0.html] и рождаются велосипеды - хромые и одноразовые..  
Так вот, зачем изобретать велосипед, когда уже давно известен паттерн regex_replace с возможностью передачи в алгоритм своего, пользовательского форматера, который берёт на себя реализацию нетривиальных условий/правил при замене выражений?

Ну и запасясь пивом, семечками и водкой в этот субботний вечер, сел между делом и написал аналог regex_replace чисто на Qt. В качестве регулярки использовал класс QRegularExpression, как более последний.  

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

Код

C++ (Qt)
QString str = "http://server.com/$user/docs/$version";
 

 
где теги это $user и $version
Мы хотим заменить $user на terminator, а $version на T1000.

С алгоритмом qRegexReplace это делается элементарно:

Код

C++ (Qt)
#include <QCoreApplication>
#include <QDebug>
#include <QMap>
 
#include "qregexreplace.h"
 
class Substitute
{
public:
    Substitute()
    {
        m_map["$user"] = "terminator";
        m_map["$version"] = "T1000";
    }
 
    QString operator()(const QString & match) const
    {
        auto it = m_map.find(match);
        if (it != m_map.end())
            return it.value();
 
        return match;
    }
 
private:
    QMap<QString, QString> m_map;
};
 
 
int main()
{
    QString str = "http://server.com/$user/docs/$version";
 
    QRegularExpression rx("(\\$\\w+)");
 
    qDebug() << qRegexReplace(str, rx, Substitute());
 
    return 0;
}
 

Это, конечно, очень упрощённый вариант - он только для наглядности. Но, думаю, идея понятна)

Сама реализация алгоритма qRegexReplace

Код

C++ (Qt)
#ifndef QREGEXREPLACE_H
#define QREGEXREPLACE_H
 
#include <QRegularExpression>
#include <QStringList>
#include <QStringRef>
#include <QList>
#include <QPair>
 
 
template <class FormatFunction>
QString qRegexReplace(const QString & input, const QRegularExpression & regex, FormatFunction formatFunc)
{
    int pos = 0;
    QString out;
    auto regexIt = regex.globalMatch(input);
    while (regexIt.hasNext())
    {
          QRegularExpressionMatch match = regexIt.next();
          QPair<int, int> r = qMakePair(match.capturedStart(1), match.capturedEnd(1));
          out.append(QStringRef(&input, pos, r.first-pos));
          out.append(formatFunc(match.captured(1)));
          pos = r.second;
    }
 
    out.append(QStringRef(&input, pos, input.size()-pos));
 
    return out;
}
 
#endif // QREGEXREPLACE_H
 

Ну и приаттачиваю исходники с проектом.

[Racheengel]

Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.
А как у данного алгоритма с этим? Будет ли регэксп быстрее "заточенного" велика?

[m_ax]

Я так понимаю, если возникла цель "замены за 1 проход", то тут главный вопрос для юзера - это производительность либо расход памяти.

Здесь и то и другое будет во много раз лучше штатного find/replace. Это очевидно.
Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.

А как у данного алгоритма с этим? Будет ли регэксп быстрее "заточенного" велика?

Смотря какой регэксп и какой велик.. Вопрос в другом - всегда ли оправдано велосипедить ручной разбор, отлаживаться, делая различные проверки, тратя на это время, если такое решение абсолютно одноразово и не расширяемо? 
Лично для меня ответ очевиден (в подавляющем большинстве случаев)  

[Igors]

Один проход - это не единственный плюс данного решения. В первую очередь оно даёт гибкость разработчику.

Хмм.. ну а какую гибкость? Вариант типа "первое вхождение меняем на это, а второе - уже на то". Ну в принципе возможно, но редко

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

Смотря какой регэксп и какой велик.. Вопрос в другом - всегда ли оправдано велосипедить ручной разбор, отлаживаться, делая различные проверки, тратя на это время, если такое решение абсолютно одноразово и не расширяемо? 
Лично для меня ответ очевиден (в подавляющем большинстве случаев)  

А что Вы написали как не велик? (вполне в моем стиле ) И чем оно хуже отой дустовщины? Менее лаконично и меньше возможностей? Может быть, но это с лихвой компенсируется легкостью использования. Ах да, это же "только QString" - где же общность? Ничего, переживем

[m_ax]

Решил тут сравнить по производительности две реализации qRegexReplace:
В первой реализации перед записью результирующей строки (QString out) высчитал её точный размер (каков будет её размер после замены текста) и после этого вызываю reserve:

Код

C++ (Qt)
QString out;
    out.reserve(input.size() - replacedTextLength + replacementTextLength);
 

для того, что бы избежать частых переаллокаций при вызове append вот здесь:

Код

C++ (Qt)
        out.append(QStringRef(&input, pos, r.first-pos));
        out.append(*it++);
 

И второй вариант - в лоб

Код

C++ (Qt)
template <class FormatFunction>
QString qRegexReplace(const QString & input, const QRegularExpression & regex, FormatFunction formatFunc)
{
    int pos = 0;
    QString out;
    auto regexIt = regex.globalMatch(input);
    while (regexIt.hasNext())
    {
          QRegularExpressionMatch match = regexIt.next();
          QPair<int, int> r = qMakePair(match.capturedStart(1), match.capturedEnd(1));
          out.append(QStringRef(&input, pos, r.first-pos));
          out.append(formatFunc(match.captured(1)));
          pos = r.second;
    }
 
    out.append(QStringRef(&input, pos, input.size()-pos));
 
    return out;
}
 

Наивно полагал, что последний вариант будет заметно медленнее, однако тесты показали что по времени оба варианта дают по порядку одинаковые результаты.  Размер файла для теста составлял примерно 123 Мб.  У QString какая то хитрая стратегия аллокации памяти под капотом?  

[Racheengel]

Ну я так понимаю, регэксп надо тут только для того, чтобы начальные индексы слов найти.
Но, честно говоря, тяжело такое будет использовать.
Я бы API примерно так видел:

QString qRegexReplace(const QString& text, const QMap<QString,QString>& replaceMap) const

и пользователь больше не имеет понятия ни о каком регэксп - оно меняет ключи на значения, а как - вопрос имплементации.

[m_ax]

По поводу реализации: может не стоит формировать "список замен", а действовать "в лоб" в одном цикле замены.

Вот мне сейчас это тоже интересно.. Списки были нужны, чтоб знать точный размер итоговой строки, чтоб можно было вначале один раз отхватить кусок.

Ах да, это же "только QString" - где же общность? Ничего, переживем

С QString сделал специально, специально только Qt онли) Специально для Qt пользователей)  

А что Вы написали как не велик? (вполне в моем стиле  )

Нет, я просто перенёс идею, реализованную в boostе в Qt мир) Потому что в Qt из коробки такого решения нет, а тема, по видимому, актуальна для новичков) Вот и всё..

[m_ax]

Я бы API примерно так видел:

QString qRegexReplace(const QString& text, const QMap<QString,QString>& replaceMap) const

Окей, как Вы тогда решите такую проблему: http://www.prog.org.ru/topic_30197_0.html
Ммм? 

[Old]

У QString какая то хитрая стратегия аллокации памяти под капотом?  

Код

C++ (Qt)
int qAllocMore(int alloc, int extra) Q_DECL_NOTHROW
{
    Q_ASSERT(alloc >= 0 && extra >= 0);
    Q_ASSERT_X(alloc <= MaxAllocSize - extra, "qAllocMore", "Requested size is too large!");
 
    unsigned nalloc = qNextPowerOfTwo(alloc + extra);
 
    Q_ASSERT(nalloc > unsigned(alloc + extra));
 
    return nalloc - extra;
}
 

[m_ax]

Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..) 

[Old]

Да, я понимаю, что она не на каждый чих будет выделять новый блок, но всё же..
Сейчас попробую построить для наглядности график как ведёт себя capacity.. Моментик..)  

Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....

Т.е. для вашего объема было выполнено 28 переаллокаций.

[m_ax]

Блоки растут по степеням двойки:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, ....

Да, действительно) Достаточно агрессивная стратегия)

[__Heaven__]

Ещё бы spirit под Qt онли

[__Heaven__]

Вектора примерно также растут (QVector, std::vector под gcc и clang)

[Old]

Вектора примерно также растут (QVector, std::vector под gcc и clang)

Не примерно, а ровно точно так (QVector, QByteArray, QList).