A simple C++ template data structure for range segmentation

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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