Самый эффективный способ избежать XML/HTML в С++-строке?
Я не могу поверить, что этот вопрос не задавался раньше. У меня есть строка, которая должна быть вставлена в файл HTML, но может содержать специальные символы HTML. Я хочу заменить их соответствующим представлением HTML.
Код ниже работает, но довольно подробный и уродливый. Производительность не имеет решающего значения для моего приложения, но я думаю, что здесь есть проблемы с масштабируемостью. Как я могу улучшить это? Я предполагаю, что это работа для алгоритмов STL или некоторая эзотерическая функция Boost, но приведенный ниже код - лучшее, что я могу придумать сам.
void escape(std::string *data)
{
std::string::size_type pos = 0;
for (;;)
{
pos = data->find_first_of("\"&<>", pos);
if (pos == std::string::npos) break;
std::string replacement;
switch ((*data)[pos])
{
case '\"': replacement = """; break;
case '&': replacement = "&"; break;
case '<': replacement = "<"; break;
case '>': replacement = ">"; break;
default: ;
}
data->replace(pos, 1, replacement);
pos += replacement.size();
};
}
Ответы
Ответ 1
Вместо того, чтобы просто заменять исходную строку, вы можете выполнять копирование с заменой "на лету", которая позволяет избежать перемещения символов в строке. Это будет иметь намного лучшую сложность и поведение кэша, поэтому я ожидаю огромного улучшения. Или вы можете использовать boost:: spirit:: xml encode или http://code.google.com/p/pugixml/.
void encode(std::string& data) {
std::string buffer;
buffer.reserve(data.size());
for(size_t pos = 0; pos != data.size(); ++pos) {
switch(data[pos]) {
case '&': buffer.append("&"); break;
case '\"': buffer.append("""); break;
case '\'': buffer.append("'"); break;
case '<': buffer.append("<"); break;
case '>': buffer.append(">"); break;
default: buffer.append(&data[pos], 1); break;
}
}
data.swap(buffer);
}
EDIT: Небольшое улучшение может быть достигнуто с помощью эвристики для определения размера буфера. Замените строку buffer.reserve на data.size()*1.1 (10%) или что-то подобное в зависимости от того, сколько ожидается замена.
Ответ 2
void escape(std::string *data)
{
using boost::algorithm::replace_all;
replace_all(*data, "&", "&");
replace_all(*data, "\"", """);
replace_all(*data, "\'", "'");
replace_all(*data, "<", "<");
replace_all(*data, ">", ">");
}
Может ли выиграть приз за наименьшее количество слов?
Ответ 3
Я бы честно пошел с более общей версией, используя итераторы, чтобы вы могли "потопить" кодировку. Рассмотрим следующую реализацию:
#include <algorithm>
namespace xml {
// Helper for null-terminated ASCII strings (no end of string iterator).
template<typename InIter, typename OutIter>
OutIter copy_asciiz ( InIter begin, OutIter out )
{
while ( *begin != '\0' ) {
*out++ = *begin++;
}
return (out);
}
// XML escaping in it general form. Note that 'out' is expected
// to an "infinite" sequence.
template<typename InIter, typename OutIter>
OutIter escape ( InIter begin, InIter end, OutIter out )
{
static const char bad[] = "&<>";
static const char* rep[] = {"&", "<", ">"};
static const std::size_t n = sizeof(bad)/sizeof(bad[0]);
for ( ; (begin != end); ++begin )
{
// Find which replacement to use.
const std::size_t i =
std::distance(bad, std::find(bad, bad+n, *begin));
// No need for escaping.
if ( i == n ) {
*out++ = *begin;
}
// Escape the character.
else {
out = copy_asciiz(rep[i], out);
}
}
return (out);
}
}
Затем вы можете упростить средний случай, используя несколько перегрузок:
#include <iterator>
#include <string>
namespace xml {
// Get escaped version of "content".
std::string escape ( const std::string& content )
{
std::string result;
result.reserve(content.size());
escape(content.begin(), content.end(), std::back_inserter(result));
return (result);
}
// Escape data on the fly, using "constant" memory.
void escape ( std::istream& in, std::ostream& out )
{
escape(std::istreambuf_iterator<char>(in),
std::istreambuf_iterator<char>(),
std::ostreambuf_iterator<char>(out));
}
}
Наконец, проверьте всю партию:
#include <iostream>
int main ( int, char ** )
{
std::cout << xml::escape("<foo>bar & qux</foo>") << std::endl;
}
Ответ 4
Вот простая ~ 30-строчная программа C, которая делает трюк довольно неплохо. Здесь я предполагаю, что temp_str будет выделять достаточную память, чтобы иметь дополнительные экранированные символы.
void toExpatEscape(char *temp_str)
{
const char cEscapeChars[6]={'&','\'','\"','>','<','\0'};
const char * const pEscapedSeqTable[] =
{
"&",
"'",
""",
">",
"<",
};
unsigned int i, j, k, nRef = 0, nEscapeCharsLen = strlen(cEscapeChars), str_len = strlen(temp_str);
int nShifts = 0;
for (i=0; i<str_len; i++)
{
for(nRef=0; nRef<nEscapeCharsLen; nRef++)
{
if(temp_str[i] == cEscapeChars[nRef])
{
if((nShifts = strlen(pEscapedSeqTable[nRef]) - 1) > 0)
{
memmove(temp_str+i+nShifts, temp_str+i, str_len-i+nShifts);
for(j=i,k=0; j<=i+nShifts,k<=nShifts; j++,k++)
temp_str[j] = pEscapedSeqTable[nRef][k];
str_len += nShifts;
}
}
}
}
temp_str[str_len] = '\0';
}
Ответ 5
Мои тесты показали, что этот ответ дал наилучшую производительность из предложенных (не удивительно, что он имеет наибольшую ставку).
Я реализовал такой же алгоритм для своего проекта (я действительно хочу иметь хорошую производительность и использование памяти) - мои тесты показали, что моя реализация имеет скорость ~ 2.6-3.25. Также мне не нравится предыдущий наилучший предложенный алгоритм bcs из-за плохого использования памяти - у вас будет дополнительное использование памяти, например, при применении множителя 1,1 эвристики, как когда .append() приведет к изменению размера.
Итак, оставьте мой код здесь - может быть, кто-нибудь найдет его полезным.
HtmlPreprocess.h:
#ifndef _HTML_PREPROCESS_H_
#define _HTML_PREPROCESS_H_
#include <string>
class HtmlPreprocess
{
public:
HtmlPreprocess();
~HtmlPreprocess();
static void htmlspecialchars(
const std::string & in,
std::string & out
);
};
#endif // _HTML_PREPROCESS_H_
HtmlPreprocess.cpp:
#include "HtmlPreprocess.h"
HtmlPreprocess::HtmlPreprocess()
{
}
HtmlPreprocess::~HtmlPreprocess()
{
}
const unsigned char map_char_to_final_size[] =
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 6, 1, 1, 1, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 4, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
const unsigned char map_char_to_index[] =
{
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 2, 0xFF, 0xFF, 0xFF, 0, 1, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 4, 0xFF, 3, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
};
void HtmlPreprocess::htmlspecialchars(
const std::string & in,
std::string & out
)
{
const char * lp_in_stored = &in[0];
size_t in_size = in.size();
const char * lp_in = lp_in_stored;
size_t final_size = 0;
for (size_t i = 0; i < in_size; i++)
final_size += map_char_to_final_size[*lp_in++];
out.resize(final_size);
lp_in = lp_in_stored;
char * lp_out = &out[0];
for (size_t i = 0; i < in_size; i++)
{
char current_char = *lp_in++;
unsigned char next_action = map_char_to_index[current_char];
switch (next_action){
case 0:
*lp_out++ = '&';
*lp_out++ = 'a';
*lp_out++ = 'm';
*lp_out++ = 'p';
*lp_out++ = ';';
break;
case 1:
*lp_out++ = '&';
*lp_out++ = 'a';
*lp_out++ = 'p';
*lp_out++ = 'o';
*lp_out++ = 's';
*lp_out++ = ';';
break;
case 2:
*lp_out++ = '&';
*lp_out++ = 'q';
*lp_out++ = 'u';
*lp_out++ = 'o';
*lp_out++ = 't';
*lp_out++ = ';';
break;
case 3:
*lp_out++ = '&';
*lp_out++ = 'g';
*lp_out++ = 't';
*lp_out++ = ';';
break;
case 4:
*lp_out++ = '&';
*lp_out++ = 'l';
*lp_out++ = 't';
*lp_out++ = ';';
break;
default:
*lp_out++ = current_char;
}
}
}
Ответ 6
Если вы собираетесь обрабатывать скорость, то мне кажется, что лучше всего будет иметь вторую строку, которую вы создаете по ходу, копируя из первой строки во вторую строку, а затем добавляя html escape-последовательности как вы их встретите. Поскольку я предполагаю, что метод replace сначала включает перемещение памяти, а затем копию в замещенную позицию, для больших строк это будет очень медленным. Если у вас есть вторая строка для построения с использованием .append(), это позволит избежать перемещения памяти.
Насколько это было "чистотой" кода, я думаю, что так же красиво, как вы собираетесь. Вы можете создать массив символов и их замен, а затем выполнить поиск в массиве, но это, вероятно, будет медленнее и не намного чище.
Ответ 7
Вы можете использовать boost::property_tree::xml_parser::encode_char_entities, если вы не хотите писать его самостоятельно.
Для справки, здесь код в boost 1.64.0:
`` `
template<class Str>
Str encode_char_entities(const Str &s)
{
// Don't do anything for empty strings.
if(s.empty()) return s;
typedef typename Str::value_type Ch;
Str r;
// To properly round-trip spaces and not uglify the XML beyond
// recognition, we have to encode them IF the text contains only spaces.
Str sp(1, Ch(' '));
if(s.find_first_not_of(sp) == Str::npos) {
// The first will suffice.
r = detail::widen<Str>(" ");
r += Str(s.size() - 1, Ch(' '));
} else {
typename Str::const_iterator end = s.end();
for (typename Str::const_iterator it = s.begin(); it != end; ++it)
{
switch (*it)
{
case Ch('<'): r += detail::widen<Str>("<"); break;
case Ch('>'): r += detail::widen<Str>(">"); break;
case Ch('&'): r += detail::widen<Str>("&"); break;
case Ch('"'): r += detail::widen<Str>("""); break;
case Ch('\''): r += detail::widen<Str>("'"); break;
default: r += *it; break;
}
}
}
return r;
}
`` `
Ответ 8
Я профилировал 3 решения с Visual Studio 2017. Входные данные составляли 10 000 000 строк размером 5-20 с вероятностью 9,4%, чтобы избежать char.
- Решение от Джованни Фуншала
- Решение HostageBrain
- Решение - мое.
Результат:
- требуется 1.675 секунд
- требуется 0,769 секунд.
- требуется 0.368 секунд
В моем решении окончательный размер предварительно вычисляется и копия строковых данных выполняется только тогда, когда это необходимо. Поэтому распределения памяти кучи должны быть минимальными.
const unsigned char calcFinalSize[] =
{
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 6, 1, 1, 1, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 4, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
};
void escapeXml(std::string & in)
{
const char* dataIn = in.data();
size_t sizeIn = in.size();
const char* dataInCurrent = dataIn;
const char* dataInEnd = dataIn + sizeIn;
size_t outSize = 0;
while (dataInCurrent < dataInEnd)
{
outSize += calcFinalSize[static_cast<uint8_t>(*dataInCurrent)];
dataInCurrent++;
}
if (outSize == sizeIn)
{
return;
}
std::string out;
out.resize(outSize);
dataInCurrent = dataIn;
char* dataOut = &out[0];
while (dataInCurrent < dataInEnd)
{
switch (*dataInCurrent) {
case '&':
memcpy(dataOut, "&", sizeof("&") - 1);
dataOut += sizeof("&") - 1;
break;
case '\'':
memcpy(dataOut, "'", sizeof("'") - 1);
dataOut += sizeof("'") - 1;
break;
case '\"':
memcpy(dataOut, ""e;", sizeof(""e;") - 1);
dataOut += sizeof(""e;") - 1;
break;
case '>':
memcpy(dataOut, ">", sizeof(">") - 1);
dataOut += sizeof(">") - 1;
break;
case '<':
memcpy(dataOut, "<", sizeof("<") - 1);
dataOut += sizeof("<") - 1;
break;
default:
*dataOut++ = *dataInCurrent;
}
dataInCurrent++;
}
in.swap(out);
}
Ответ 9
Или с помощью только stl:
std::string& rep(std::string &s, std::string from, std::string to)
{
int pos = -1;
while ( (pos = s.find(from, pos+1) ) != string::npos)
s.erase(pos, from.length()).insert(pos, to);
return s;
}
Использование:
rep(s, "&", """);
rep(s, "\"", """);
или
rep(s, "HTML","xxxx");
