A simple C++ template data structure for range segmentation

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	165
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Hello Codeforces,

It is sometimes required in competitive programming problems to segment a range defined as [first, last) of indices in a given data container, where first refers to the first element to inspect and last refers to the element past the last element to inspect, into a number of intervals such that all the consecutive elements in any interval have the same value of a particular segmentation function $$$f(x)$$$ whose value depends on the present element $$$x$$$ only, and this value is different from the function value in the intervals before and after such interval if any of them exists.

This blog presents a simple C++ template data structure for such purpose.

The following is the declaration and implementation of the data structure.

struct seg

template<class ForwardIt, class UnaryFunction>
struct seg: vector<size_t> {
    inline seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) {
        if (first != last) {
            size_t width = 1; 
            for (auto present_value = fun(*first++); first != last; ++width) {
                const auto next_value = fun(*first++);
                if (next_value != present_value)
                    push_back(width), present_value = next_value, width = 0; }
            push_back(width); } } };

The seg data structure inherits vector<size_t> as a base class to store the range-segmentation results. The data-structure constructor seg(ForwardIt first, ForwardIt last, const UnaryFunction& fun) has three parameters: first and last specify the range [first, last), and fun specifies the segmentation function.

The time-complexity of constructing an object/instance of this data structure should be $$$O((S+T+U).N)$$$, where $$$S$$$, $$$T$$$ and $$$U$$$ are the execution times required to complete the segmentation function call fun(*first), to append an element to the vector using a vector<size_t>::push_back(width) member function call, to increment the iterator first, respectively, and $$$N = last-first$$$ is the range size.

The following are sample applications of this data structure.

CodingKnight's blog