4

Как лучше всего разделить строку std::string на токены по заданным разделителям? Например для разделителей {" ", ",", ", "} и строки "один два,три, четыре" функция должна выдавать std::vector<std::string> вида {"один","два","три","четыре"}.

Обновление: мне казалось, что это видно из примера - разделитель может быть произвольной длины. То есть если разделитель ", ", то разделять надо именно им, а не отдельно "," и/или " ".

Обновление 2: благодаря комментарию AnT понял, что условие всё таки не до конца определено. Если в строке встречается несколько разделителей подряд, причём один из разделителей является подстрокой другого, то деление должно происходить по большему из разделителей. Например, "один, два"(два пробела) должно разделить на "один" и " два"(один пробел), а не на какую-либо другую пару.

11
  • @VTT разве std::strtok отличит ", " от ","?
    – brave
    23 дек 2018 в 17:48
  • @VTT то есть любой разделитель длины больше 1
    – brave
    23 дек 2018 в 17:48
  • ", " будет таким же разделителем как и " " или "," сами по себе. А если вам нужен токен-разделитель (т.е. когда " " или "," по отдельности не являются разделителями, а вместе являются) - то это другая история 23 дек 2018 в 17:51
  • @VTT обновил вопрос
    – brave
    23 дек 2018 в 17:58
  • Не то есть если у вас один разделитель является подстрокой другого, то надо стараться разделять по более длинному и только потом по более короткому. 23 дек 2018 в 18:14

3 ответа 3

5

Для нетривиального набора разделителей (взаимно включают друг друга) лучшим решением будет использование сторонней библиотеки (например, Boost.Tokenizer). Однако попробуем решить вашу задачу с использованием стандартной библиотеки.


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

Напишем функцию, которая будет выполнить разделение строки на токены с помощью передаваемого ей регулярного выражения:

#include <regex>   
#include <string>
#include <vector>

std::vector<std::string> regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}

Здесь -1 как раз и означает итерацию по non-matched фрагментам. То есть передаваемое регулярное выражение должно искать именно разделители, не затрагивая кириллический текст.

Для тестирования будем использовать следующий код:

#include <iostream>
#include <regex>
#include <string>
#include <vector>

std::vector<std::string> regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}

int main() {
    constexpr auto regex_str = R"()"; // сюда будем вставлять текст регулярного выражения
    const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,   девять"}; // строка для тестов

    const std::regex reg{regex_str};
    const auto tokens = regex_split(str, reg);
    
    for (auto&& token : tokens) {
        std::cout << token << '\n';
    }
}

В большинстве случаев будет достаточно следующего регулярного выражения (далее текст регулярного выражения нужно вставлять в R"()" без кавычек):

" *, *| +"

То есть запятая, окружённая произвольным количеством пробелов (0+), ИЛИ 1+ пробел без запятых.

На тестовом примере получим:

один
два
три
четыре
пять
шесть
семь

восемь
девять

Что в большинстве случаев и ожидается.

Если же мы считаем отсутствие строки неприемлемым (как между "семь" и "восемь"), то можно убрать "-1" и просто находить всё, что не является разделителем:

"[^, ]+"

Однако судя по комментариям и правкам к вопросу, вам нужно нечто более сложное. Попробуем для начала такое выражение (далее оставляем "-1"):

", | |,"

То есть запятая и пробел ИЛИ пробел ИЛИ запятая. Возможно, это именно то, что вам надо. Результаты для тестовой строки:

один
два
три
четыре

пять


шесть

семь

восемь


девять

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

Сделать это можно с помощью т.н. negative look-behind, проверив, что символ перед пробелом не является пробелом, при этом не захватывая этот символ. Если же символ всё же являлся пробелом (как между "четыре" и "пять" в тестовой строке) и захват не произошёл, то будет осуществлён greedy match, т.е. будет выбран разделитель ", ", что нам и нужно. Таким образом, регулярное выражение будет иметь вид:

", |(?! ) |,"

То есть запятая и пробел ИЛИ пробел, перед которым нет пробела ИЛИ запятая. Думаю, это именно то, что вам нужно (по крайней мере все условия соблюдаются). Однако есть небольшая проблема: look-behind не поддерживается стандартной грамматикой ECMAScript :). А, судя по этому ответу, остальные существующие в С++ грамматики также его не поддерживают. Но не беда, ведь look-ahead поддерживаются!

Нетрудно видеть, что если мы перевернём строку и в регулярном выражении заменим ", " на " ,", а также negative look-behind на negative look-ahead, то получим такое же поведение:

constexpr auto regex_str = R"( ,| (?! )|,)";
const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,   девять"};

const std::regex reg{regex_str};
const std::string reversed{str.crbegin(), str.crend()};
const auto reversed_tokens = regex_split(reversed, reg);

for (auto it = reversed_tokens.crbegin(); it != reversed_tokens.crend(); ++it) {
    auto&& reversed_token = *it;
    std::cout << std::string{reversed_token.crbegin(), reversed_token.crend()} << '\n';
}

Результаты для тестовой строки:

один
два
три
четыре
 пять
 
шесть

семь

восемь
  девять

Теперь перед "пять" появился пробел, между " пять" и "шесть" один пробел вместо двух. Аналогичная "склейка" и для "девять".

Окончательный код:

#include <iostream>
#include <regex>
#include <string>
#include <vector>

std::vector<std::string> regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}

int main() {
    constexpr auto regex_str = R"( ,| (?! )|,)";
    const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,   девять"};

    const std::regex reg{regex_str};
    const std::string reversed{str.crbegin(), str.crend()};
    const auto reversed_tokens = regex_split(reversed, reg);

    for (auto it = reversed_tokens.crbegin(); it != reversed_tokens.crend(); ++it) {
        auto&& reversed_token = *it;
        std::cout << std::string{reversed_token.crbegin(), reversed_token.crend()} << '\n';
    }
}
4

Для решения такой задачи пригодился бы алгоритм одновременного поиска нескольких подстрок в строке, вроде алгоритма Ахо-Корасик.

Если же решать подручными средствами "на коленке", то можно предложить такой вариант. Пусть у нас есть N разделителей

  1. Отсортировать массив разделителей по убыванию длины
  2. Начиная с текущей позиции C в строке (изначально C = 0), выполнить поиск первой подстроки для каждого разделителя и сформировать массив размера найденных позиций (массив размера N)
  3. Среди N полученных позиций найти минимальную позицию M. Если разделителей с такой позицией несколько, то берем самый первый (т.е. самый длинный, согласно упорядочению с шага 1).
  4. Подстрока от С до M уходит на выход
  5. Перемещаем текущую позицию C в позицию M плюс длина использованного разделителя
  6. Обновляем содержимое массива, полученного на шаге 2: те позиции, которые оказались меньше C обновляем путем поиска соответствующей подстроки с позиции C
  7. Переходим на шаг 3

Например

#include <iostream>
#include <string>
#include <string_view>
#include <vector>
#include <algorithm>

std::vector<std::string_view> split(const std::string_view &str, 
                                    std::vector<std::string> delimiters)
{
  std::vector<std::string_view> result;    

  std::sort(delimiters.begin(), delimiters.end(), 
    [](const std::string &lhs, const std::string &rhs) 
      { return lhs.length() > rhs.length(); });

  std::vector<std::string::size_type> nexts(delimiters.size());
  for (unsigned i = 0; i < delimiters.size(); ++i)
    nexts[i] = str.find(delimiters[i]);

  std::string::size_type current = 0;

  do
  {
    auto it_next = std::min_element(nexts.begin(), nexts.end());
    if (*it_next == std::string::npos)
      break;

    if (current < *it_next)
      result.emplace_back(&str[current], *it_next - current);

    current = *it_next + delimiters[it_next - nexts.begin()].length(); 

    for (unsigned i = 0; i < delimiters.size(); ++i)
      if (nexts[i] < current)
        nexts[i] = str.find(delimiters[i], current);

  } while (true);

  if (current < str.length())
    result.emplace_back(&str[current], str.length() - current);

  return result;
}

int main()
{
    auto r = split("abc..def, ghij ief.dkj ,ddd.", { ",", ", ", ".", ".." });
    for (auto &s : r)
      std::cout << "'" << s << "'" << std::endl; 
}

Эта реализация пропускает пустые строки, если разделители идут подряд.

0
std::string s, delim(" ,-");
std::vector<std::string> vs;
while (getline(std::cin, s))
    vs.emplace_back(s.substr(0, s.find_first_of(delim)));

После обновления вопроса: Я напишу на простом примере, а вы по этой логике работайте над любой строкой с любым разделителем:

std::string s("one,-         two"), del(",-");
std::vector<std::string> vs;
int k = del.size(),
        pos = s.find(del); // находим позицию разделителья
vs.emplace_back(s.substr(0, pos));  // строка от начала до разделителья
vs.emplace_back(s.substr(pos + k)); // строка от конца разделителья
6
  • 1
    Так ", " не будет разделять. Я сделал дополнительно пояснение в вопросе
    – brave
    23 дек 2018 в 18:00
  • Это то же самое, что говорить: так не будет заполняться вектор... А вы попробуйте хотябы. 23 дек 2018 в 18:16
  • Что попробовать?
    – brave
    23 дек 2018 в 18:21
  • Вы хотите чтобы разделитель была строкаб а не символ? 23 дек 2018 в 18:27
  • Один разделитель - строка, т.е. может быть более 1 символа. Но всего разделителей может быть много. Т.е. разделители = вектор строк или множество строк или т.п.
    – brave
    23 дек 2018 в 18:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.