Как написать explode() на c++?

Question

[Issue]

Я только начал писать на С++, решил начать с написания функции, но не понимаю, как то все очень криво, такое количество ошибок у меня небыло ни с одним языком. Помогите понять, что я тут не правильно делаю. Функция explode() на PHP режет строку по разделителю.

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

vector<string> explode(string separator, string input){
    string line;
    int count = 1;
    vector<string> output {};
    for (int i = 0; input[i] != '\0'; ++i) {
        if (input[i] == separator) {
            output.push_back(line);
            line = "";
            count++;
        } else {
            line += input[i];
        }
    }
    return output;
}

int main(){
    int count = 1;
    vector<string> msg = explode(".", "a.b.c.d");
    for (const string& word : msg){
        cout << count << " => " << word << endl;
        count++;
    }
    return 0;
}

Answer 1

[WAR_VIK]

Вот функция для разделителя с любым количеством символов:

std::vector<std::string> explode(std::string separator, std::string input) {
      std::vector<std::string> vec;
      for(int i{0}; i < input.length(); ++i) {
            int pos = input.find(separator, i);
            if(pos < 0) { vec.push_back(input.substr(i)); break; }
            int count = pos - i;
            vec.push_back(input.substr(i, count));
            i = pos + separator.length() - 1;
      }
return vec;
}

Comments

[Issue]

Благодарю! Не знал что есть такие методы. Я так понял - что vector и string - это классы со своими методами?

[WAR_VIK]

Issue, - Да Вы правильно поняли, это классы со своими методами

[RabraBabr]

Безотносительно качества кода. У меня вопрос по поводу вызова .length(); внутри цикла. Насколько это хорошая идея с точки зрения производительности?

[Евгений Шатунов]

RabraBabr,

У меня вопрос по поводу вызова .length(); внутри цикла.

O(1). Никаких проблем не вызывает.

[Евгений Шатунов]

Issue, рекомендую изучить этот ответ.
Если примешь во внимание все написанное там, тебе станет проще решать подобные заданному вопросы.

[RabraBabr]

Евгений Шатунов, То есть оно вызовется только один раз независимо от количества циклов?

for(int i{0}; i < input.length(); ++i)

сама input как я понимаю не меняется.

[Евгений Шатунов]

RabraBabr,

То есть оно вызовется только один раз независимо от количества циклов?

Ответ на этот вопрос лежит в области работы оптимизатора. Результат действительно может быть таким, что length будет вызван только один раз для неизменяемой строки.

Но код в ответе написан настолько нехорошо, что я могу говорить только о том, что вызывать length на каждой итерации - это не проблема для производительности. Метод просто возвращает значение поля длины строки. Никаких подсчетов фактической длины при этом не производится. Об этом и говорит сложность O(1) для этого метода.

[RabraBabr]

Метод просто возвращает значение поля длины строки

По значению? Каждый раз будет копирование?

[RabraBabr]

O'k возьмем код попроще

const Polygon operator+( const Polygon& lhs,const Polygon& rhs )
{
    Polygon ret = lhs;
    const int last = rhs.GetNumPoints();
    for( int i = 0; i < last; ++i ) // Конкатенация
    {
        ret.AddPoint( rhs.GetPoint(i) );
        
    }
    return ret;
}

Этот код попадет в библиотечный. Потом мы не знаем сколько миллионов раз он будет вызываться в клиентском коде (GetNumPoints(); можно пихнуть в цикл).

[Wataru]

Евгений Шатунов, RabraBabr,

У этого кода другая проблема с точки зрения производительности: input.find(separator, i); работает за квадрат в худшем случае. Если separator длинный, да еще там много частичных совпадений в input, то код будет тормозить.
Стандарт не накладывает никаких ограничений на временную сложность метода find и, насколько мне известно, все распространенные реализации стандартной библиотеки не используют каких-нибудь хитрых алгоритмов вроде Боера-Мура или Кнута-Морриса-Пратта.

[Евгений Шатунов]

Wataru, вопрос строки input.find(separator, i); я просто не стал обозначать. Как и вопрос чрезмерного выделения памяти. Я только ответил человеку относительно length внутри цикла.

[Евгений Шатунов]

RabraBabr,

По значению?

Да, по значению. А в чем сложность передать одно целочисленное значение в общем регистре ЦП?

Каждый раз будет копирование?

Копирование чего и куда?

O'k возьмем код попроще

Этот код при передаче в библиотеку будет выкинут и написан новый, уже без лишних выделений памяти и неподобающих инициализаций.

Answer 2

[galaxy]

Добавьте using namespace std; после заголовков (хотя, конечно, лучше явно писать std::vector, std:string).

Вот этого input[i] != '\0' делать не стоит, ибо, если не ошибаюсь, плюсы уже не гарантируют наличие терминатора в конце строки, и в любом случае это будет обращение за пределы длины строки, что есть Undefined behavior.

Ваш код последний кусок строки не добавляет в массив.
В PHP separator может состоять из нескольких символов, у вас - из одного. Тут нужно что-то типа string::find() использовать для поиска подстроки.

Answer 3

[Евгений Николаев]

По ссылке blog.ivru.net/?id=315 пример функции explodeItem которая в отличии от PHP функции explode возвращает не массив полученный при разбиении строки по сепаратору а только один элемент по его порядковому номеру после разбиения, с учётом того что первый элемент имеет номер - 0.

Возможно не то что Вам требуется, при этом некоторые моменты написания требуемой функции понять можно.