Split text with array of delimiters

Question

I want a function that split text by array of delimiters. I have a demo that works perfectly, but it is really really slow. Here is a example of parameters.

text:

"pop-pap-bab bob"

vector of delimiters:

"-"," "

the result:

"pop", "-", "pap", "-", "bab", "bob"

So the function loops throw the string and tries to find delimeters and if it finds one it pushes the text and the delimiter that was found to the result array, if the text only contains spaces or if it is empty then don't push the text.

std::string replace(std::string str,std::string old,std::string new_str){
    size_t pos = 0;
    while ((pos = str.find(old)) != std::string::npos) {
        str.replace(pos, old.length(), new_str);
    }
    return str;
}


std::vector<std::string> split_with_delimeter(std::string str,std::vector<std::string> delimeters){
    std::vector<std::string> result;
    std::string token;
    int flag = 0;
    for(int i=0;i<(int)str.size();i++){
        for(int j=0;j<(int)delimeters.size();j++){
            if(str.substr(i,delimeters.at(j).size()) == delimeters.at(j)){
                if(token != ""){
                    result.push_back(token);
                    token = "";
                }
                if(replace(delimeters.at(j)," ","") != ""){
                    result.push_back(delimeters.at(j));
                }
                i += delimeters.at(j).size()-1;
                flag = 1;
                break;
            }
        }
        if(flag == 0){token += str.at(i);}
        flag = 0;
    }
    if(token != ""){
        result.push_back(token);
    }
    return result;
}

My issue is that, the functions is really slow since it has 3 loops. I am wondering if anyone knows how to make the function faster. I am sorry, if I wasn't clear enough my english isn't the best.

Answer 1

Maybe, as an alternative, you could use a regex? But maybe also too slow for you . . .

With a regex life would be very simple.

Please see the following example:

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

const std::regex re(R"((\w+|[\- ]))");

int main() {
    
    std::string s{"pop-pap-bab bob"};
    
    std::vector<std::string> part{std::sregex_token_iterator(s.begin(),s.end(),re),{}};
    
    for (const std::string& p : part)   std::cout << p << '\n';
}

We use the std::sregex_token_iterator in combination with the std::vectors range constructor, to extract everything specified in the regex and then put all those stuff into the std::vector

The regex itself is also simple. It specifies words or delimiters.

Maybe its worth a try . . .

Answer 2

NOTE: You've complained that your code is slow, but it's important to understand that most of the answers will have options to potentially speed up the program. And even if the author of the option measured the acceleration of the program, the option may be slower on your machine, so do not forget to measure the execution speed yourself.

If I were you, I would create a separate function that receives an array of strings and outputs an array of delimited strings. The problem with this approach may be that if the delimiter includes another delimiter, the result may not be what you expect, but it will be easier to iterate through different options for string splitting, finding the best. And my solution would looks like this(though, it requires c++20)

#include <iomanip>
#include <iostream>
#include <ranges>
#include <string_view>
#include <vector>

std::vector<std::string> split_elems_of_array(const std::vector<std::string>& array, const std::string& delim)
{
    std::vector<std::string> result;
    for(const auto str: array)
    {
        for (const auto word : std::views::split(str, delim))
        {
            std::string chunk(word.begin(), word.end());
            if(!chunk.empty() && chunk != " ")
                result.push_back(chunk + delim);
        }
    }

    return result;
}

std::vector<std::string> split_string(std::string str, std::vector<std::string> delims)
{
    std::vector<std::string> result = {std::string(str)};
    for(const auto&delim: delims)
        result = split_elems_of_array(result, delim);
    return {result.begin(), result.end()};
}

For my machine, my approach is 56 times faster: 67 ms versus 5112 ms. Length of string is 1000000, there are 100 delims with length 100

Answer 3

Here is the algorithm of standard splitting. if you split pop-pap-bab bob by {'-' , ' '} it gives you ["pop", "pap", "bab", "bob"] it's not storing delimiters and doesn't check for empty text. You can change it to do those things too.

• Define a vector of strings named result.
• Define a string variable named buffer.
• Loop over your string, if current character is not a delimiter append it to buffer.
• if current character is a delimiter, append buffer to result.
• Return result at the end.

std::vector<std::string> split(std::string str, std::vector<char> delimiters)
  {
    std::vector<std::string> result;
    std::string buffer;

    for (const auto ch : str)
    {
      if (std::find(delimiters.begin(), delimiters.end(), ch) == delimiters.end())
        buffer += ch;

      else
      {
        result.insert(result.end(), buffer);
        buffer.clear();
      }
    }

    if (buffer.length())
      result.insert(result.end(), buffer);

    return result;
  }

It's time complexity is O(n.m). n is the length of string and m is the length of delimiters.

Answer 4

It might be a good idea to use boost expressive. It is a powerful tool for various string operations more than struggling with string::find_xx and self for-loop or regex.

Concise explanation: +as_xpr(" ") is repeated match more than 1 like regex and then prefix "-" means shortest match. If you define regex parser as sregex rex = "(" >> (+_w | +"_") >> ":" >> +_d >> ")", it would match (port_num:8080). In this case, ">>" means the concat of parsers and (+_w | +"_") means that it matches character or "_" repeatedly.

#include <vector>
#include <string>
#include <iostream>
#include <boost/xpressive/xpressive.hpp>
using namespace std;
using namespace boost::xpressive;

int main() {
    string          source = "Nigeria is a multi&&national state in--habited by more than 2;;50 ethnic groups speak###ing 500 distinct languages";
    vector<string>  delimiters{ " ", "  ", "&&", "-", ";;", "###"};

    vector<sregex>  pss{ -+as_xpr(delimiters.front()) };
    for (const auto& d : delimiters) pss.push_back(pss.back() | -+as_xpr(d));

    vector<string>  ret;
    size_t          pos = 0;
    auto push       = [&](auto s, auto e) { ret.push_back(source.substr(s, e)); };
    for_each(sregex_iterator(source.begin(), source.end(), pss.back()), {}, [&](smatch const& m) {
            if (m.position() - pos) push(pos, m.position() - pos);
            pos = m.position() + m.str().size();
        }
    );
    push(pos, source.size() - pos);
    for (auto& s : ret) printf("%s\n", s.c_str());
}

Output is splitted by multiple string delimiers.

Nigeria
is
a
multi
national
state
in
habited
by
more
than
2
50
ethnic
groups
speak
ing
500
distinct
languages