Split string into same consecutive characters

Question

Description

• Splits a string into a vector of strings that has consecutive same characters
  • Examples in test cases below ("5500025" --> ["55", "000", "2", "5"])
• Only ASCII needs to be supported
• In case of style/formatting issues, I am using https://zed0.co.uk/clang-format-configurator/

Compile

• gcc -std=c++17 file.cpp
• I'm not committed to C++17 (using it for std::string_view), so if C++20 or some other version makes it significantly easier, I can switch to that

Test cases

• Provided in main()
  • "AAABBCDDDDAAEE5" --> ["AAA", "BB", "C", "DDDD", "AA", "EE", "5"]
  • "" --> []

Code

file.cpp (tio.run)

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

std::vector<std::string>
group_string_components(std::string_view input_string) {
  std::vector<std::string> grouping;

  if (input_string.length() == 0) {
    return grouping;
  }

  std::size_t pos = 0;
  while (pos != std::string::npos) {
    std::size_t next_pos =
        input_string.find_first_not_of(input_string[pos], pos + 1);

    std::size_t repeat = next_pos - pos;

    if (next_pos == std::string::npos) {
      repeat = input_string.length() - pos;
    }

    grouping.push_back(std::string(repeat, input_string[pos]));

    pos = next_pos;
  }

  return grouping;
}

void run_grouping_test(std::string_view test_case_name,
                       std::string_view input_string,
                       const std::vector<std::string> &expected_grouping) {
  std::vector<std::string> grouping = group_string_components(input_string);
  std::cout << test_case_name << " passed: " << std::boolalpha
            << (grouping == expected_grouping) << "\n";
}

int main() {
  run_grouping_test("General case", "AAABBCDDDDAAEE5",
                    {"AAA", "BB", "C", "DDDD", "AA", "EE", "5"});
  run_grouping_test("Empty case", "", {});

  return 0;
}

Answer 1

Avoid memory allocations, Part 1.

Your function takes a std::string_view in input, why does it return a std::string?

It would be better to return a std::string_view (referencing the input), and leave it up to the caller to turn it into a std::string if they so wish.

Use string_view functionality.

For consuming input, in a parsing, there are two great functions in std::string_view:

• substr, which allows creating a substring.
• remove_prefix, which allows popping the first N characters.

Rather than tracking the offset on your own, it simplifies the code quite a bit to use those two functions and "consume" your input as you go.

Putting it altogether.

A simple rewrite, with the above:

auto group_string_components(std::string_view input)
    -> std::vector<std::string_view>
{
    std::vector<std::string_view> grouping;

    if (input.empty()) {
        return grouping;
    }

    while (true) {
        std::size_t next = input.find_first_not_of(input[0], 1);

        grouping.push_back(input.substr(0, next));

        if (next == std::string_view::npos) {
            return grouping;
        }

        input.remove_prefix(next);
    }
}

Avoid memory allocations, Part 2.

There is, however, at least one remaining memory allocation: the vector. And actually, it's probably going to lead to several allocations, as the vector may internally need to reallocate a few times.

Do you actually need to materialize the collection? group_string_components certainly doesn't: it never looks back.

This suggests that instead of returning a vector, group_string_components should instead return either a pair of iterators, or, with C++20, ranges. Actually, C++23 should offer a ranges::chunk_by_view which would be ideal here... but in the mean time, it needs to be coded manually.

I'll show off the iterator case, there is a trick with the advance function (which has to be called in the constructor) that is good to remember:

class group_component_iterator {
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = std::string_view;
    using difference_type = std::ptrdiff_t;
    using pointer = value_type*;
    using reference = value_type&;

    group_component_iterator() noexcept = default;

    group_component_iterator(std::string_view v) noexcept : tail(v) {
         if (!this->tail.empty()) {
             this->advance();
         }
    }

    pointer operator->() { return &this->current; }

    reference operator*() { return this->current; }

    group_component_iterator& operator++() {
        this->advance();
        return *this;
    }

    group_component_iterator operator++(int) {
        auto tmp = *this;
        this->advance();
        return tmp;
    }

    bool operator==(group_component_iterator const& other) {
        //  Do not use `std::string_view` operator ==, as it compares the content
        //  which is potentially expensive.
        return (this->current.empty() && other.current.empty())
            || (this->current.data() == other.current.data()
                && this->current.size() == other.current.size()
                && this->tail.data() == other.tail.data()
                && this->tail.size() == other.tail.size());
    }

    bool operator!=(group_component_iterator const& other) {
        return !(*this == other);
    }

private:
    void advance() {
        assert(!tail.empty());

        auto next = tail.find_first_not_of(tail[0], 1);
        current = tail.substr(0, next);

        tail.remove_prefix(std::min(next, tail.size()));
    }

    std::string_view current;
    std::string_view tail;
};

The core of the logic has moved into the iterator, so the function is now simple:

auto group_string_components(std::string_view input)
    -> std::pair<group_component_iterator, group_component_iterator>
{
    return std::make_pair(group_component_iterator(input), group_component_iterator());
}

Note: untested code.

There are two advantages to using an iterator/range approach:

• Laziness:
  • If the caller only cares about the first 5 groups, then the others are never used.
  • If the caller only uses 1 group at a time, then the others are not materialized simultaneously, which saves on memory.
• No allocations.

Answer 2

Nice tidy code, and you've provided a test - that's good. You didn't mention warning options when compiling; I used g++-12 -std=c++17 -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion -Weffc++ -Wuseless-cast and it was clean.

Interface

Taking input as a std::string_view is perfect - no need to copy any character data. However, we forgot to include the <string_view> header (<string> isn't sufficient if we want portable code). We might want to generalise it to accept any character type, using template std::basic_string_view<CharT>.

Consider returning a collection of views, and leave it to the caller to decide whether to construct string objects from these.

The return type of the function might be a constraint in some use cases - not everyone wants a std::vector, and it might be hard for the allocator to find sufficient contiguous storage when the result is large. We could provide a version that accepts an output iterator - users could then use a std::back_insert_iterator into any kind of collection, or even a std::ostream_iterator for full streaming without using any storage.

Implementation

We're using the wrong npos constant - we should be using std::string_view::npos.

We don't actually need the pos index, if instead we shorten the view by advancing its start point, so that we're always looking at the beginning of the string (note, this is cheap with a view, but very costly with a string object). We can use the remove_prefix() member function:

while (!input_string.empty()) {
    auto count = input_string.find_first_not_of(input_string.front());
    if (count == input_string.npos) {
        count = input_string.size();
    }

    grouping.emplace_back(input_string.substr(0, count));
    input_string.remove_prefix(count);
}

This has the additional advantage that we don't need a separate path to handle empty input - that naturally happens with this loop.

As user Deduplicator observed, because the npos value is very large, we can use std::min() to restrict it to the string's size:

while (!input_string.empty()) {
    auto count = std::min(input_string.size(),
                          input_string.find_first_not_of(input_string.front()));
    *iter++ = input_string.substr(0, count);
    input_string.remove_prefix(count);
}

---

Modified code

#include <algorithm>
#include <iterator>
#include <string_view>
#include <vector>

template<typename CharT,
         typename Traits = std::char_traits<CharT>,
         typename Iter>
auto
group_string_components(std::basic_string_view<CharT, Traits> input,
                        Iter iter)
{
    while (!input.empty()) {
        auto count = std::min(input.size(),
                              input.find_first_not_of(input.front()));
        *iter++ = input.substr(0, count);
        input.remove_prefix(count);
  }

  return iter;
}

template<typename CharT,
         typename Traits = std::char_traits<CharT>>
auto
group_string_components(std::basic_string_view<CharT, Traits> input)
{
    std::vector<std::basic_string_view<CharT, Traits>> grouping;
    group_string_components(input, std::back_inserter(grouping));
    return grouping;
}

If we had C++20, we could use constraints to restrict the Iter type, and with C++23, we might use std::ranges::chunk_by_view to split in this way.

Answer 3

You could convert the while loop to a for loop:

for (std::size_t pos = 0, next_pos; pos != std::string::npos; pos = next_pos) {

The main reason to do that is to limit the pos variable to the loop body, it's not used outside.

---

I think input_string.empty() is more idiomatic than input_string.length() == 0.

---

For each grouping, the loop body checks if the end of the string was reached or not. You could avoid the extra conditional by counting the repeats yourself, instead of using find_first_not_of, at the expense of duplicating a grouping.push_back(...).

std::size_t repeat = 0;
char prev = input_string[0];

for (auto c : input_string) {
  if (c == prev) {
    repeat++;
  } else {
    grouping.push_back(std::string(repeat, prev));
    prev = c;
    repeat = 1;
  }
}

grouping.push_back(std::string(repeat, prev));