function- delete element which is bigger then prevoius

Question

how can I change the code that after erasing first number, next iterator doesn't skip that number and compares it with the next one?

    //previous number
    auto i = aa.begin();
    //next number
    auto j = ++aa.begin();
    while (j != aa.end()) {
        if (*i < *j) {
            //if next number is bigger - it gets erased
            j = aa.erase(j);
            continue;
        }
        i = j;
        ++j;
    }
}

Warning: `auto j = ++aa.begin();` is fatal if the container is empty. Make sure removing `j` can't invalidate `i`. — user4581301, May 30 '22 at 17:26
Isn't that code already doing exactly that? Or do you mean that `{3, 4, 4}` should result in `{3, 4}` because the second 4 isn't larger than the first 4? Give an example of input with expected and actual output. — Goswin von Brederlow, May 30 '22 at 17:54
I mean do you know how to implement this solution using stl linked list? — Veronika Novikova, May 31 '22 at 10:26

score 1 · Answer 1 · answered May 30 '22 at 17:27

std::vector::erase returns an iterator to the first element after the removed elements. Hence you only need to increment the iterator when nothing has been erased:

    if (*std::next(j) < *j) {
        j = aa.erase(j);
    } else {
        ++j;
    }

Instead of keeping track of i manually you can use std::next to get the next iterator. In that case you need to stop the loop when std::next(j) == end.

score 0 · Answer 2 · answered May 30 '22 at 17:23

0

Iterate through it backwards, and remove an element if its previous element is <= it.

answered May 30 '22 at 17:23

Xinurval

44
3

score 0 · Answer 3 · answered May 30 '22 at 17:26

0

You can store the value of the previous number in a variable.

    //previous number
    auto i = aa.begin();
    //next number
    auto previousValue = *i
    auto j = ++aa.begin();
    while (j != aa.end()) {
        if (previousValue < *j) {
            //if next number is bigger - it gets erased
            previousValue = *j;
            j = aa.erase(j);
            continue;
        }
        i = j;
        previousValue = *j;
        ++j;
    }
}

answered May 30 '22 at 17:26

Deepak Patankar

3,076
3
16
35

Thanks a lot! Maybe you can help also with linked list? ``` void deleteelem(Element* list){ //function to delete elements Element* x, * next; x = list; next = list->next; while (next != NULL){ if (x->nr < next->nr) { //comparing prevoius number with next next = next->next; delete x->next; x->next = next; continue; } x = next; next = x->next; }; ``` – Veronika Novikova May 30 '22 at 17:51
Oh great, that's also a nice solution!! – Deepak Patankar May 31 '22 at 05:17

Marek R · Answer 4 · 2022-05-30T17:52:28.990

It is best to use standard library for this kind of operations. Smaller chance to make mistake. Also designing functions API keeping common standard from STL library is a good practice too:

template <typename It>
auto remove_smaller_then_prev(It b, It e)
{
    if (b == e)
        return e;
    auto prev = *b++;
    return std::remove_if(b, e, [&prev](const auto& x) { return x < std::exchange(prev, x); });
}

template <typename V>
void erase_smaller_then_prev(V& v)
{
    auto newEnd = remove_smaller_then_prev(std::begin(v), std::end(v));
    v.erase(newEnd, std::end(v));
}

https://godbolt.org/z/s96xW4qf9

Extra question: how about testcase: 5, 3, 4 what should be the result, I assumed: 5, 4.

Side note: please remember that code exists in some context, so it is a good practice to show problematic code inside a complete function which provides such context (like in my answer).

bitmask · Answer 5 · 2022-05-30T18:22:06.737

Do not keep erasing from the vector. Instead, use the read-write-pointer pattern. It performs much better and is easier to reason about.

template <typename T>
void removeUnsorted(std::vector<T>& vec) {
  if (vec.empty()) return;
  auto last = begin(vec);
  auto write = begin(vec);
  for (auto read = begin(vec); read != end(vec); ++read) {
    if (!(*last < *read)) {
      *write++ = *read;
    } 
    last = read; // !
  }   
  vec.resize(distance(begin(vec),write));
}

Basically this tracks all value you want to keep between begin(vec) and write. The read iterator goes over every value once and copies it to *write if and only if you decide to keep it.

You can decide with which value to compare, the last one read or the last one written. The code as it stands now compares against the last one read, such that this:

{7,6,9,4,3,8,5,2}

gets transformed to this:

{7,6,4,3,5,2}
         ^----- note the 5

If you do not want this, but want to always have a descending value, move the line with a // ! comment inside the if condition, thereby only updating the "compare-to" value when it was kept, not when it was encountered.

In the very last line, you truncate the vector, dropping every value that was not kept. Note that this is done in constant time for integers.

function- delete element which is bigger then prevoius

5 Answers5