Написать функцию, которая вычисляет длину самого длинного строго возрастающего подотрезка

Question

Есть некоторая последовательность s1,s2...sn, подотрезком которой называется непрерывная подпоследовательность вида si,s(i+1)...s(j-1), i <= j. Необходимо написать функцию, которая принимает последовательность, хранящуюся в std::list, по двум итераторам, и вычисляет для неё длину самого длинного строго возрастающего подотрезка. Копировать элементы запрещено, тип элементов в list неизвестен. Данная реализация не проходит тест при длине list = 2

template<class It>
size_t max_increasing_len(It p, It q)
{
    size_t size = 0;
    int index = 0;

    if (p == q) return 0;
    else if (p == --q) return 1;
    else ++q;

    for (; p != q;)
    {
        if (*p < *++p)
        {
            index++;
        }
        else if (index > size)
        {
            size = ++index;
            index = 0;
        }
        else
        {
            index = 0;
        }
    }

    return index > size ? index : size;
}

Answer 1

if (*p < *++p) - неопределённое поведение. Если в выражении используется результат ++p, запрещено там же использовать значение p.

Это по стандарту. А на деле компилятор может преобразовать ваш код в следующее:

++p;
if (*p < *p)

А потом сообразить что в условии тождественная ложь и выбросить условный оператор из кода программы вообще.

Вы думаете я шучу? Нет, порядок вычисления аргументов оператора < не определяется стандартом.

Order of evaluation:

Order of evaluation of any part of any expression, including order of evaluation of function arguments is unspecified (with some exceptions listed below). The compiler can evaluate operands and other subexpressions in any order, and may choose another order when the same expression is evaluated again.

There is no concept of left-to-right or right-to-left evaluation in C++. This is not to be confused with left-to-right and right-to-left associativity of operators: the expression a() + b() + c() is parsed as (a() + b()) + c() due to left-to-right associativity of operator+, but c() may be evaluated first, last, or between a() or b() at run time...

В вашем случае компилятор может скомпилировать код к, примеру, двумя способами:

auto a = *p;
auto b = *++p;
if (a < b)      // тут всё работает как ожидается

auto b = *++p;
auto a = *p;
if (a < b)      // тут ничего не работает

Пока вы учитесь, избегайте инкрементов в составе выражений. ++p; - можно, *++p или что-то сложнее - нельзя.

Answer 2

`

template<class It>
size_t max_increasing_len(It p, It q){
    int cnt = 0, max = 0;
    for(It iter = p, temp; iter != q; ++iter) {
        if (cnt != 0 && *(--(temp = iter)) < *iter) {
            ++cnt;
        } else {
            max = cnt > max ? cnt : max;
            cnt = 1;
        }
    }
    return max = cnt > max ? cnt : max

`

БЛОГ НА HUSL

Написать функцию, которая вычисляет длину самого длинного строго возрастающего подотрезка

Ответы (2 шт):