4
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ Is it a bound task that you need to return a 'std::vector<std::string>'? \$\endgroup\$
    – Surt
    Sep 25, 2022 at 20:53

3 Answers 3

4
\$\begingroup\$

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.
\$\endgroup\$
9
  • \$\begingroup\$ Looks like we had a lot of the same observations, including remove_prefix() and group_by_view(). \$\endgroup\$ Sep 19, 2022 at 10:50
  • 1
    \$\begingroup\$ @TobySpeight: Indeed; your answer wasn't there when I started on mine, otherwise I wouldn't have bothered. Your use of sink iterator as an argument leads to much simpler code, too. \$\endgroup\$ Sep 19, 2022 at 11:59
  • 1
    \$\begingroup\$ I saw yours appear when I was halfway through writing mine, but decided not to read it until I finished. I like your idea of demonstration of a custom iterator; it's more complex, but quite educational. \$\endgroup\$ Sep 19, 2022 at 12:45
  • \$\begingroup\$ I had hoped to be able to use the output iterator to assign to both string-views and string objects, but failed because conversion from string-view to string is (rightly) explicit. \$\endgroup\$ Sep 19, 2022 at 13:08
  • 1
    \$\begingroup\$ @FromTheStackAndBack: adding to Matthieu's explanation, when you get to C++20, you'll find that the concept of an iterator pair (more accurately, an iterator and a sentinel) is the founding principle of the Ranges library. It will definitely be useful to you if you're already thinking in those terms. \$\endgroup\$ Sep 20, 2022 at 7:58
4
\$\begingroup\$

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.

\$\endgroup\$
0
3
\$\begingroup\$

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));
\$\endgroup\$
1
  • 1
    \$\begingroup\$ emplace_back is a thing! empty isn't only more idiomatic, it better expresses intent and can be more efficient for some other containers. \$\endgroup\$ Sep 19, 2022 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.