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;
}
}
CodePudding user response:
Iterate through it backwards, and remove an element if its previous element is <= it.
CodePudding user response:
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;
}
}
CodePudding user response:
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
.
CodePudding user response:
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).
CodePudding user response:
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.