Цели: закрепление навыков работы с std::vector и std::string.
Критерии полноты
Данная работа основана на работе 7, но на новой “технологической базе”: вместо “обычного” массива указателей на си-строки следует использовать вектор строк из Стандартной библиотеки C++, т.е. vector<string>. Первые шесть заданий предполагают поэлементную обработку текста (без изменения количества или порядка строк). Следующие пять — удаление строк, отвечающих заданному критерию. Последние три задания имеют более “синкретический” характер.
Рекомендуется внимательно прочитать примеры употребления функций-членов класса string. Можно использовать функцию find для поиска подстроки, функцию replace — для замены, включая удаление (заменить найденную подстроку на пустую строку).
Ввод-вывод векторов строк реализовать довольно легко.
/// Для сокращения записи введём синоним типа "массив строк" -- "строки"
using Line = string;
using Lines = vector<Line>;
/// Вывести в стандартный поток вывода массив строк.
void putlines(const Lines &lines)
{
for (auto &line: lines)
cout << line << '\n';
}
// gets не нужна (есть стандартная функция getline).
/// Читаем построчно, пока возможно, и складываем в vector.
Lines getlines()
{
Lines lines;
for (Line line; getline(cin, line); )
lines.push_back(line);
return lines;
}Сравните это с кодом для массивов си-строк из задачи 7.
Аналог первого задания в задаче 7 на основе vector<string> также легко реализовать: string поддерживает операцию конкатенации (операции + и +=) непосредственно и управляет памятью самостоятельно.
// delim = {} означает, что по умолчанию delim -- пустая строка
// (если проигнорировать некоторые нюансы, то можно было бы написать delim = "").
Line join(const Lines &lines, const Line &delim = {})
{
Line result;
if (!lines.empty())
{
result = lines.front();
for (size_t i = 1, sz = lines.size(); i < sz; ++i)
(result += delim) += lines[i];
}
return result;
}Оптимизация: заранее зарезервировать нужную память, чтобы избежать лишних перераспределений памяти в процессе “наращивания” строки. Для этого требуется вычислить общее количество символов результирующей строки. Оно равно сумме длин строк текста плюс (количество строк текста – 1) * длина строки-разделителя. См. также пример split/join.
/// Количество символов в тексте.
size_t text_size(const Lines &lines)
{
size_t s = 0;
for (auto &line: lines)
s += line.size();
return s;
}
Line join(const Lines &lines, const Line &delim = {})
{
Line result;
if (!lines.empty())
{
result.reserve(text_size(lines) + (lines.size() - 1) * delim.size());
result += lines.front();
for (size_t i = 1, sz = lines.size(); i < sz; ++i)
(result += delim) += lines[i];
}
return result;
}
Данный пример является аналогом одноимённого примера из задачи 7. Строки здесь не удаляются, удаляются лишь комментарии в конце каждой строки. Если вся строка занята комментарием, то в результате она остаётся в виде пустой строки.
/// Удалить закомментированный "хвост" строки.
void remove_comment(Line &line, char ch)
{
const auto pos = line.find(ch);
// Функция поиска возвращает позицию знака или
// особое значение npos, если знак не найден.
if (pos != Line::npos)
line.resize(pos);
}
/// Удалить комментарии из текста.
void remove_comments(Lines &text, char comment_mark)
{
for (auto &line: text)
remove_comment(line, comment_mark);
}Теперь можно написать тест. Никаких вспомогательных определений уже не требуется: всё, что нужно есть в Стандартной библиотеке C++.
/// Тест функции remove_comments.
bool test_remove_comments()
{
// Исходный текст.
Lines input =
{
"",
"# comment",
"something; # comment",
"'hello, world!'",
"'# not a comment but it's OK to cut here too'... # a real comment"
};
// Текст результата, который должен получиться.
const Lines reference =
{
"",
"",
"something; ",
"'hello, world!'",
"'"
};
remove_comments(input, '#');
return input == reference;
}
Предположим, задано ограничение на длину строк, и мы хотим удалить из массива все строки, превышающие это ограничение. Использование функции вектора erase для каждой обнаруженной строки имеет два недостатка: 1) квадратичное время по числу строк в худшем случае (весь остаток массива каждый раз сдвигается на одну позицию); 2) высокая вероятность допустить ошибку при переборе строк с одновременным удалением.
Итак, вариант 1 — создать новый массив из неудалённых строк и заменить старый на новый.
void remove_too_long_lines(Lines &lines, size_t max_len)
{
Lines short_lines;
for (auto &line: lines)
if (line.size() <= max_len)
short_lines.push_back(line);
lines.swap(short_lines); // заменить старый на новый
}Данный вариант довольно прост, работает за линейное по числу строк время, но технически несовершенен: требуется дополнительная память и время на копирование строк и создание нового массива.
Можно ли как-то улучшить ситуацию?
Попробуем немного поработать над вариантом 1. Будем работать в явных индексах и заменим вставку в конец присваиванием.
void remove_too_long_lines(Lines &lines, size_t max_len)
{
Lines short_lines;
// Вычислим реальный размер short_lines.
size_t slsz = 0;
for (auto &line: lines)
slsz += line.size() <= max_len;
short_lines.resize(slsz);
// Запишем нужные строки в short_lines.
for (size_t i = 0, j = 0, lsz = lines.size(); i < lsz; ++i)
if (lines[i].size() <= max_len)
short_lines[j++] = lines[i];
lines.swap(short_lines); // заменить старый на новый
}Теперь достаточно понять, что во втором цикле j никогда не бывает больше i. А значит, вместо вспомогательного массива short_lines можно изменять сам массив lines на месте.
void remove_too_long_lines(Lines &lines, size_t max_len)
{
size_t j = 0; // После цикла -- новый размер lines.
for (size_t i = 0, lsz = lines.size(); i < lsz; ++i)
if (lines[i].size() <= max_len)
lines[j++] = lines[i];
lines.resize(j);
}От копирования строк можно избавиться с помощью функции swap, которая обменивает содержимое строк за постоянное время (обменивает внутренние указатели на динамические массивы вместо того, чтобы обменивать содержимое массивов).
Итак, вариант 2:
void remove_too_long_lines(Lines &lines, size_t max_len)
{
size_t j = 0; // После цикла -- новый размер lines.
for (size_t i = 0, lsz = lines.size(); i < lsz; ++i)
if (lines[i].size() <= max_len)
lines[j++].swap(lines[i]);
lines.resize(j);
}Впрочем, данную задачу в C++ следует решать с привлечением стандартных функций из Стандартной библиотеки алгоритмов (часть STL, заголовочный файл <algorithm>), а именно remove_if. По сути, это тот же алгоритм, что и в варианте 2, который благодаря механизму шаблонов может принимать произвольный предикат-критерий удаления (в виде функционального объекта = “функтора”). Пока данные примеры приводятся без разъяснений.
Вариант 3 для C++98:
#include <algorithm>
// ...
/// Функтор, который будет проверять строки.
class Is_string_too_long
{
size_t max_len;
public:
Is_string_too_long(size_t max_len)
: max_len(max_len) {}
bool operator()(const Line &line) const
{
return line.size() > max_len;
}
};
void remove_too_long_lines(Lines &lines, size_t max_len)
{
lines.erase(
remove_if(lines.begin(), lines.end(),
Is_string_too_long(max_len)),
lines.end());
}Вариант 3 для C++11 (написание особого класса Is_string_too_long здесь уже не требуется):
#include <algorithm>
// ...
void remove_too_long_lines(Lines &lines, size_t max_len)
{
lines.erase(
remove_if(lines.begin(), lines.end(),
[=](const Line &line) { return line.size() > max_len; }),
lines.end());
}
С помощью Стандартной библиотеки алгоритмов, например, задача 9 из работы 7: удаление подряд идущих дубликатов строк, решается “в одну инструкцию”:
void remove_duplicates(Lines &lines)
{
lines.erase(
unique(lines.begin(), lines.end()),
lines.end());
}
Заменить последовательности символов TAB ('\t') в начале каждой строки (каждого элемента vector<string>) на пробелы. Количество пробелов, соответствующих одному TAB, должно быть параметром функции.
Заменить последовательности пробелов в начале каждой строки (каждого элемента vector<string>) на последовательности символов TAB ('\t'). Количество пробелов, соответствующих одному TAB (ширину TAB), должно быть параметром функции.
Если последовательность пробелов в начале строки содержит число пробелов, не делящееся нацело на заданную ширину TAB, то оставлять после TAB’ов “лишние” пробелы (в количестве, равном остатку от деления).
“Раскомментировать” строки. Комментарий начинается с заданной подстроки и продолжается до конца строки. Удалить такую подстроку, если она стоит в начале строки (возможно, после последовательности пробельных символов).
Пример
Пусть дана строка, открывающая комментарий "//", и входной массив вида:
{
" //using std::begin;",
" //using std::end; // comment",
"//using std::true_type;",
"using std::false_type; // comment"
};Результирующий массив должен быть следующим:
{
" using std::begin;",
" using std::end; // comment",
"using std::true_type;",
"using std::false_type; // comment"
};“Закомментировать” строки, не являющиеся комментарием. Задана строка rem, открывающая комментарий. Для каждой строки в исходном массиве проверяем, начинается ли она строкой rem (возможно, после последовательности пробельных символов), и если нет, то добавляем rem в начало строки.
Пример
Пусть дана строка, открывающая комментарий rem = "//", и входной массив вида:
{
" //using std::begin;",
"//using std::end; // comment",
"using std::true_type;",
"using std::false_type; // comment"
};Результирующий массив должен быть следующим:
{
" //using std::begin;",
"//using std::end; // comment",
"//using std::true_type;",
"//using std::false_type; // comment"
};“Цензуирование”. Пусть дан “текст” (вектор строк) и набор “запрещённых слов” (тоже вектор строк). Заменить каждое вхождение подстроки из текста, совпадающей с любым из “запрещённых слов”, на строку "***".
Подобный способ использовался в реальных программах, но, конечно, он слишком примитивен и приводит к нелепым ошибкам из-за случайных совпадений частей вполне литературных слов с ругательствами.
Пример
Пусть дана текст:
{
"I begin my work with the time when Servius Galba was consul for the second time with Titus Vinius for his colleague.",
"Of the former period, the 820 years dating from the founding of the city, many authors have treated;",
"and while they had to record the transactions of the Roman people, they wrote with equal eloquence and freedom.",
"After the conflict at Actium, and when it became essential to peace, that all power should be centered in one man, these great intellects passed away."
};Пусть дан набор “запрещённых слов”:
{
"beg",
"aut",
"record",
"zor"
};Результирующий массив тогда должен быть следующим:
{
"I ***in my work with the time when Servius Galba was consul for the second time with Titus Vinius for his colleague.",
"Of the former period, the 820 years dating from the founding of the city, many ***hors have treated;",
"and while they had to *** the transactions of the Roman people, they wrote with equal eloquence and freedom.",
"After the conflict at Actium, and when it became essential to peace, that all power should be centered in one man, these great intellects passed away."
};Если префикс строки в исходном массиве совпадает с одной из строк в другом массиве, то удалить этот префикс.
Пример
Пусть дан массив:
{
"glCreateShader",
"glShaderSource",
"glCompileShader",
"glCreateProgram",
"malloc",
"free",
"GL_TRUE",
"GL_FALSE"
};И дан набор префиксов:
{
"axp",
"gl",
"GL_"
};Результирующий массив должен быть следующим:
{
"CreateShader",
"ShaderSource",
"CompileShader",
"CreateProgram",
"malloc",
"free",
"TRUE",
"FALSE"
};Пусть исходный набор строк можно условно представить в виде следующих друг за другом блоков (A и X — некоторые последовательности строк):
A
X
Aт.е. блок A повторяется в конце набора. При этом A — максимальный по размеру такой блок.
Требуется удалить финальный блок A. Результирующий набор строк должен иметь вид:
A
XПримечание. В данном задании предполагается реализация квадратичного алгоритма, находящего блок A, после чего для удаления финальной копии блока A достаточно воспользоваться функцией-членом вектора resize.
Если строка в исходном массиве имеет префикс, совпадающий с любой из строк из заданного набора префиксов, то удалить эту строку из массива.
Пример
Пусть дан массив:
{
"glCreateShader",
"glShaderSource",
"glCompileShader",
"glCreateProgram",
"malloc",
"free",
"GL_TRUE",
"GL_FALSE"
};И дан набор префиксов:
{
"axp",
"gl",
"GL_"
};Результирующий массив должен быть следующим:
{
"malloc",
"free"
};Если строка в исходном массиве имеет суффикс, совпадающий с любой из строк из заданного набора суффиксов, то удалить эту строку из массива.
Пример
Пусть дан массив:
{
"makeup",
"the fire of truth",
"nature",
"get out",
"failure",
"stand up"
};И дан набор суффиксов:
{
"up",
"ure"
};Результирующий массив должен быть следующим:
{
"the fire of truth",
"get out"
};Удалить из массива строки, содержащие в качестве подстроки хотя бы одну из строк из заданного набора (другой массив строк).
Пример
Пусть дан массив:
{
"like anyone else",
"both of you",
"and he too has got those two",
"look through the window"
"it had a greater illusion of realism than theatre"
};И дан набор строк:
{
"one",
"two",
"three"
};Результирующий массив должен быть следующим:
{
"both of you",
"look through the window"
"it had a greater illusion of realism than theatre"
};Удалить из массива строки, являющиеся повторением заданной строки.
Пусть дана строка “re” и массив:
{
"re",
"rere",
"rerere",
"abc",
"lax",
"relax",
"rerelax",
"rere"
};Результирующий массив должен быть следующим:
{
"abc",
"lax",
"relax",
"rerelax"
};Пусть дано число W. Для каждой строки длиннее W, содержащей по крайней мере два слова, выполнить перенос слов на следующую строку, чтобы “вписать” текст в ширину W. Последнее слово (первое по счёту слева направо) не переносится. Пробелы, отделяющие перенесённое слово, уничтожаются.
Пусть дано значение W = 50 и текст
{
" Преимуществами способа 2 являются: удобство кодирования и в среднем большее быстродействие",
"операций, выполняемых над массивом целиком, а также минимизация операций выделения и",
"освобождения памяти, минимизация затрат памяти (нет вспомогательного массива)."
};Результирующий массив должен быть следующим:
{
" Преимуществами способа 2 являются: удобство",
"кодирования и в среднем большее быстродействие",
"операций, выполняемых над массивом целиком, а",
"также минимизация операций выделения и",
"освобождения памяти, минимизация затрат памяти",
"(нет вспомогательного массива)."
};Выравнивание текста по ширине. Пусть задано число W. Привести все строки текста, которые короче W и содержат, по крайней мере два слова, к ширине W путём равномерного “наращивания” пробелов между словами.
Пусть дано значение W = 50 и текст
{
" Преимуществами способа 2 являются: удобство",
"кодирования и в среднем большее быстродействие",
"операций, выполняемых над массивом целиком, а",
"также минимизация операций выделения и",
"освобождения памяти, минимизация затрат памяти",
"(нет вспомогательного массива)."
};Результирующий массив должен быть следующим:
{
" Преимуществами способа 2 являются: удобство",
"кодирования и в среднем большее быстродействие",
"операций, выполняемых над массивом целиком, а",
"также минимизация операций выделения и",
"освобождения памяти, минимизация затрат памяти",
"(нет вспомогательного массива)."
};Найти первое вхождение заданного слова в тексте, представленном вектором строк, при условии, что слово может быть разбито переносом (знаком -, завершающим строку) в любой позиции (остаток переносится на следующую строку). Вхождение определяется как пара чисел: индекс строки в векторе и индекс первого символа слова в строке.
Кувшинов Д.Р. © 2016