Шаблон vector
Вектор в библиотеке STL — это удобный массив (вернее, структура, аналогичная массиву), размер которого может изменяться динамически. Вектор целых чисел A задается таким образом:
vector A;
Аналогично можно задавать векторы любого другого типа.
Вектор поддерживает операцию обращения по индексу A[i] , как и обычный массив, но в отличии от обычного массива размер вектора может меняться. У вектора есть метод size , возвращающий количество элементов в векторе в настоящий момент.
Есть несколько способов создать вектор (конструкторы вектора):
vector(B) , где B — вектор такого же типа. Создает копию вектора B
vector(n) , где n — целое число. Создает вектор из n элементов.
vector(n, val) — создает вектор из n элементов, заполненных значением val .
vector A(10, 179); vector B(A);
создаст вектор A из 10 элементов равных 179, а затем вектор B , являющийся копией вектора A .
Конструкторы можно вызывать явно для создания объектов, например, vector(10, 179) создаст объект типа vector и вызовет для вновь создаваемого объекта конструктор.
Для изменения размера вектора можно использовать метод resize . Первый его параметр — новый размер вектора, второй параметр (необязательный, имеет смысл только при увеличении размера вектора) — значение, которым заполняются вновь созданные элементы.
Для добавления нового элемента в конец вектора можно использовать метод push_back(val) . Для удаления последнего элемента из вектора можно использовать метод pop_back() .
Из вектора A можно удалить элемент с индексом i при помощи A.erase(A.begin() + i) . Для удаления элементов с i -го (включая) до j -го (не включая) можно использовать A.erase(A.begin() + i, A.begin() + j) . Также можно использовать итератор end() , возвращающий элемент на конец вектора (фиктивный элемент, следующий за последним). Например, удалить элементы с i -го до конца можно при помощи A.erase(A.begin() + i, A.end()) , а удалить k последних элемента вектора можно при помощи A.erase(A.end() — k, A.end()) . Удаление требует сдвига элементов, поэтому выполняется за линейное время.
Вставить значения в вектор можно при помощи метода insert . Например, вставить элемент val перед i -м элементов вектора A можно при помощи A.insert(A.begin() + i, val) . Если же передать в качестве указателя два итератора, то можно вставить весь фрагмент между итераторами. Например, A.insert(A.begin(), B.begin(), B.end()) вставляет в начало вектора A все содержимое вектора B .
Более подробно обо всех методах работы с векторами можно прочесть на cppreference.com.
Операции со строками в STL
В этом листке мы снова будем работать со строками, активно используя стандартную библиотеку языка C++ STL (Standard template library).
Считывание строк
Напомним, что строки можно считывать двумя способами: до пробельного символа (пробела, конца строки, символа табуляции) при помощи конструкции cin >> S , и до конца строки при помощи функции getline(cin, S) .
Арифметические операторы
Со строками можно выполнять следующие арифметические операции:
= — присваивание значения.
+= — добавление в конец строки другой строки или символа.
+ — конкатенация двух строк, конкатенация строки и символа.
== , != — посимвольное сравнение.
< , >, = — лексикографическое сравнение.
Подробней об операторах для строк читайте здесь.
Конструкторы
Строки можно создавать с использованием следующих конструкторов:
string() — конструктор по умолчанию (без параметров) создает пустую строку.
string(string & S) — копия строки S
string(int n, char c) — повторение символа c заданное число n раз.
string(char c) — строка из одного символа c .
string(string & S, int start, int len) — строка, содержащая не более, чем len символов данной строки S , начиная с символа номер start .
Конструкторы можно вызывать явно, например, так:
S += string(10, 'z');
В этом примере явно вызывается конструктор string для создания строки, состоящей из 10 символов ‘z’ .
Неявно конструктор вызывается при объявлении строки с указанием дополнительных параметров. Например, так:
string S(10, 'z');
Подробней о конструкторах для строк читайте здесь.
Методы для строк
Методом называется функция, которая применяется к объекту, например, строке. При вызове метода его имя пишется после идентификатора объекта через точку, например, у объекта типа string есть метод size , возвращающий длину строки. Если S — это строка, то метод вызывается так: S.size() . Другой пример: метод substr возвращает подстроку заданной строки:
string S = "Hello, world!"; coutВ данном случае будет выведен текст world .
Вот список полезных методов, применяемых к строкам:
Векторы в C++ — урок 12
Вектор в C++ — это замена стандартному динамическому массиву, память для которого выделяется вручную, с помощью оператора new .
Разработчики языка рекомендуют в использовать именно vector вместо ручного выделения памяти для массива. Это позволяет избежать утечек памяти и облегчает работу программисту.
- Пример создания вектора
- Управление элементами вектора
- Методы класса vector
Пример создания вектора
#include int main() < // Вектор из 10 элементов типа int std::vectorv1(10); // Вектор из элементов типа float // С неопределенным размером std::vector v2; // Вектор, состоящий из 10 элементов типа int // По умолчанию все элементы заполняются нулями std::vector v3(10, 0); return 0; >
Управление элементами вектора
Создадим вектор, в котором будет содержаться произвольное количество фамилий студентов.
#include #include int main() < // Поддержка кириллицы в консоли Windows setlocale(LC_ALL, ""); // Создание вектора из строк std::vectorstudents; // Буфер для ввода фамилии студента std::string buffer = ""; std::cout 0) < // Добавление элемента в конец вектора students.push_back(buffer); >> while (buffer != ""); // Сохраняем количество элементов вектора unsigned int vector_size = students.size(); // Вывод заполненного вектора на экран std::cout return 0; >
Результат работы программы:
Методы класса vector
Для добавления нового элемента в конец вектора используется метод push_back() . Количество элементов определяется методом size() . Для доступа к элементам вектора можно использовать квадратные скобки [] , также, как и для обычных массивов.
- pop_back() — удалить последний элемент
- clear() — удалить все элементы вектора
- empty() — проверить вектор на пустоту
Подробное описание всех методов std::vector (на английском) есть на C++ Reference.
Цели и критерии
Цели: закрепление навыков работы с std::vector и std::string.
Критерии полноты
- Используя vector, реализовать отдельную функцию, решающую поставленную задачу.
- Реализовать автоматическое тестирование функции из п.1 с помощью, по крайней мере, двух не слишком простых тестов. Разместить тесты в отдельной функции (не в main).
Введение
Данная работа основана на работе 7, но на новой “технологической базе”: вместо “обычного” массива указателей на си-строки следует использовать вектор строк из Стандартной библиотеки C++, т.е. vector. Первые шесть заданий предполагают поэлементную обработку текста (без изменения количества или порядка строк). Следующие пять — удаление строк, отвечающих заданному критерию. Последние три задания имеют более “синкретический” характер.
Рекомендуется внимательно прочитать примеры употребления функций-членов класса string. Можно использовать функцию find для поиска подстроки, функцию replace — для замены, включая удаление (заменить найденную подстроку на пустую строку).
Примеры
Ввод-вывод
Ввод-вывод векторов строк реализовать довольно легко.
/// Для сокращения записи введём синоним типа "массив строк" -- "строки" using Line = string; using Lines = vector; /// Вывести в стандартный поток вывода массив строк. void putlines(const Lines &lines) < for (auto &line: lines) cout '\n'; > // gets не нужна (есть стандартная функция getline). /// Читаем построчно, пока возможно, и складываем в vector. Lines getlines() < Lines lines; for (Line line; getline(cin, line); ) lines.push_back(line); return lines; >Конкатенация массива строк в одну строку
Аналог первого задания в задаче 7 на основе vector также легко реализовать: 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() // заменить старый на новый >Данный вариант довольно прост, работает за линейное по числу строк время, но технически несовершенен: требуется дополнительная память и время на копирование строк и создание нового массива.
Можно ли как-то улучшить ситуацию?
Попробуем немного поработать над вариантом 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() // Запишем нужные строки в short_lines. for (size_t i = 0, j = 0, lsz = lines.size(); i < lsz; ++i) if (lines[i].size() // заменить старый на новый >Теперь достаточно понять, что во втором цикле 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()
От копирования строк можно избавиться с помощью функции 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()
Впрочем, данную задачу в C++ следует решать с привлечением стандартных функций из Стандартной библиотеки алгоритмов (часть STL, заголовочный файл ), а именно remove_if . По сути, это тот же алгоритм, что и в варианте 2, который благодаря механизму шаблонов может принимать произвольный предикат-критерий удаления (в виде функционального объекта = “функтора”). Пока данные примеры приводятся без разъяснений.
Вариант 3 для C++98:
#include // . /// Функтор, который будет проверять строки. 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)
Вариант 3 для C++11 (написание особого класса Is_string_too_long здесь уже не требуется):
#include // . 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)
Варианты
1
Заменить последовательности символов TAB ( '\t' ) в начале каждой строки (каждого элемента vector) на пробелы. Количество пробелов, соответствующих одному TAB, должно быть параметром функции.
2
Заменить последовательности пробелов в начале каждой строки (каждого элемента vector) на последовательности символов TAB ( '\t' ). Количество пробелов, соответствующих одному TAB (ширину TAB), должно быть параметром функции.
Если последовательность пробелов в начале строки содержит число пробелов, не делящееся нацело на заданную ширину TAB, то оставлять после TAB’ов “лишние” пробелы (в количестве, равном остатку от деления).
3
“Раскомментировать” строки. Комментарий начинается с заданной подстроки и продолжается до конца строки. Удалить такую подстроку, если она стоит в начале строки (возможно, после последовательности пробельных символов).
Пример
Пусть дана строка, открывающая комментарий "//" , и входной массив вида:
< " //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" >;4
“Закомментировать” строки, не являющиеся комментарием. Задана строка 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" >;5
“Цензуирование”. Пусть дан “текст” (вектор строк) и набор “запрещённых слов” (тоже вектор строк). Заменить каждое вхождение подстроки из текста, совпадающей с любым из “запрещённых слов”, на строку "***" .
Подобный способ использовался в реальных программах, но, конечно, он слишком примитивен и приводит к нелепым ошибкам из-за случайных совпадений частей вполне литературных слов с ругательствами.
Пример
Пусть дана текст:
< "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." >;6
Если префикс строки в исходном массиве совпадает с одной из строк в другом массиве, то удалить этот префикс.
Пример
Пусть дан массив:
< "glCreateShader", "glShaderSource", "glCompileShader", "glCreateProgram", "malloc", "free", "GL_TRUE", "GL_FALSE" >;И дан набор префиксов:
< "axp", "gl", "GL_" >;Результирующий массив должен быть следующим:
< "CreateShader", "ShaderSource", "CompileShader", "CreateProgram", "malloc", "free", "TRUE", "FALSE" >;7
Пусть исходный набор строк можно условно представить в виде следующих друг за другом блоков ( A и X — некоторые последовательности строк):
A X Aт.е. блок A повторяется в конце набора. При этом A — максимальный по размеру такой блок.
Требуется удалить финальный блок A . Результирующий набор строк должен иметь вид:
Примечание. В данном задании предполагается реализация квадратичного алгоритма, находящего блок A , после чего для удаления финальной копии блока A достаточно воспользоваться функцией-членом вектора resize.
8
Если строка в исходном массиве имеет префикс, совпадающий с любой из строк из заданного набора префиксов, то удалить эту строку из массива.
Пример
Пусть дан массив:
< "glCreateShader", "glShaderSource", "glCompileShader", "glCreateProgram", "malloc", "free", "GL_TRUE", "GL_FALSE" >;И дан набор префиксов:
< "axp", "gl", "GL_" >;Результирующий массив должен быть следующим:
< "malloc", "free" >;9
Если строка в исходном массиве имеет суффикс, совпадающий с любой из строк из заданного набора суффиксов, то удалить эту строку из массива.
Пример
Пусть дан массив:
< "makeup", "the fire of truth", "nature", "get out", "failure", "stand up" >;И дан набор суффиксов:
< "up", "ure" >;Результирующий массив должен быть следующим:
< "the fire of truth", "get out" >;10
Удалить из массива строки, содержащие в качестве подстроки хотя бы одну из строк из заданного набора (другой массив строк).
Пример
Пусть дан массив:
< "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" >;11
Удалить из массива строки, являющиеся повторением заданной строки.
Пусть дана строка “re” и массив:
< "re", "rere", "rerere", "abc", "lax", "relax", "rerelax", "rere" >;Результирующий массив должен быть следующим:
< "abc", "lax", "relax", "rerelax" >;12
Пусть дано число W. Для каждой строки длиннее W, содержащей по крайней мере два слова, выполнить перенос слов на следующую строку, чтобы “вписать” текст в ширину W. Последнее слово (первое по счёту слева направо) не переносится. Пробелы, отделяющие перенесённое слово, уничтожаются.
Пусть дано значение W = 50 и текст
< " Преимуществами способа 2 являются: удобство кодирования и в среднем большее быстродействие", "операций, выполняемых над массивом целиком, а также минимизация операций выделения и", "освобождения памяти, минимизация затрат памяти (нет вспомогательного массива)." >;Результирующий массив должен быть следующим:
< " Преимуществами способа 2 являются: удобство", "кодирования и в среднем большее быстродействие", "операций, выполняемых над массивом целиком, а", "также минимизация операций выделения и", "освобождения памяти, минимизация затрат памяти", "(нет вспомогательного массива)." >;13
Выравнивание текста по ширине. Пусть задано число W. Привести все строки текста, которые короче W и содержат, по крайней мере два слова, к ширине W путём равномерного “наращивания” пробелов между словами.
Пусть дано значение W = 50 и текст
< " Преимуществами способа 2 являются: удобство", "кодирования и в среднем большее быстродействие", "операций, выполняемых над массивом целиком, а", "также минимизация операций выделения и", "освобождения памяти, минимизация затрат памяти", "(нет вспомогательного массива)." >;Результирующий массив должен быть следующим:
< " Преимуществами способа 2 являются: удобство", "кодирования и в среднем большее быстродействие", "операций, выполняемых над массивом целиком, а", "также минимизация операций выделения и", "освобождения памяти, минимизация затрат памяти", "(нет вспомогательного массива)." >;14
Найти первое вхождение заданного слова в тексте, представленном вектором строк, при условии, что слово может быть разбито переносом (знаком - , завершающим строку) в любой позиции (остаток переносится на следующую строку). Вхождение определяется как пара чисел: индекс строки в векторе и индекс первого символа слова в строке.
Поиск подстроки в std::vector
Подскажите как решить следующую задачу оптимальным путем: есть std::vector stringVector, содержащий 3 элемента. Есть задача: Найти, содержит ли i-ый элемент stringVector подстроку(std::string). Пример: Допустим, stringVector состоит из: stringVector[0] = "Сегодня хороший день."; stringVector[1] = "Завтра будет день апокалипсиса."; stringVector[2] = "Привет, Андрей."; string searchString = "день"; То, что я написал(но не работает):
for (size_t i = 0; i < tokens.size(); i++) < // Не работает: ошибка бинарный оператор == не найден и т.д. auto result = find(tokens[i].begin(), tokens[i].end(), searchString); if (result != tokens[i].end()) < // Какое-то действие >>
P.s. я бы мог сделать перегрузку оператора == в глобальной области(или достаточно в области видимости класса?) для моего случая и объявить его дружественным классу, но не понимаю какие аргументы он должен принимать.
Отслеживать
задан 12 дек 2019 в 16:07
399 3 3 серебряных знака 15 15 бронзовых знаков
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Вы хотите что-то такое?
vector tokens; string sub; . for(const auto& s: tokens) if (s.find(sub)!=s.npos) < // Найдена подстрока >Отслеживать
ответ дан 12 дек 2019 в 16:21
219k 15 15 золотых знаков 119 119 серебряных знаков 230 230 бронзовых знаков
почти так. Но можно ли как-то сделать, что поиск осуществлялся по конкретному tokens[i]? То есть когда итерируется цикл for, поиск должен происходить не во всех tokens, как у Вас в примере, а только в tokens[i]?