Delete all elements from list whose sum with preceding element equals target value

Question

Let me start off by saying that the question specifically implies using std::list<int> and not anything else AND you are allowed to iterate over the list only once. Taking this into account, we assume the target sum value to be 10.

The task is:

You are given a list of integers (std::list<'int'>). Iterating over the list only once, delete all elements that give a sum of 10 with the preceding element.

I was wondering how I can make my code more efficient and clear, because my application was rejected immediately.

#include <list>
#include <iostream>
#include <conio.h>

bool target_sum(const int i, const int j)
{
    return (i+j) == 10;
}

void print(const std::list<int> &nmbrs)
{
    for (const int p : nmbrs)
        std::cout << p << " ";
    std::cout << std::endl;
}    


int main()
{
    // initialises a list that holds the numbers
    std::list<int> nmbrs = {5, 5, 3, 7, 7, 7, 3, 3, 1, 2, 3, 7, 4, 6};

if (nmbrs.size() > 1)                     //if there are at least 2 numbers
{
    std::list<int>::iterator i = nmbrs.begin();
    while (i != std::prev(nmbrs.end()))   //we compare number *i to the following number *(i+1),
    {                                     //while incrementing the iterator at the same time
        if (target_sum(*i, *(i++)))
        {
            i = nmbrs.erase(i);
            i--;                          //move back in case the numbers repeat
        }

        //print(nmbrs);
    }
} else 
{
    //print(nmbrs);
}

print(nmbrs);

_getch();

return 0;
}

Answer 1

Breaking down the requirements:

You are given a list of integers (std::list<'int'>).

The algorithm is required to at least work with std::list<int>, so we cannot rely on random-access/contiguity.

Iterating over the list only once,

Requires a single-pass algorithm. Single pass algorithms have special rules associated with them, like only accessing the current element once and only moving forward. Your implementation exhibits multi-pass behavior.

std::prev(nmbrs.end())
--i;

delete all elements that give a sum of 10 with the preceding element.

Applying this to a single pass approach, you will need to store the preceding element in a temporary.

---

A source file should be self-sufficient in providing the definition of every symbol used. Some implementations may include the library for you (<list> including <iterator>, but that behavior is neither standard nor portable. std::prev requires <iterator>.

---

bool target_sum(const int i, const int j)
{
    return (i+j) == 10;
}

Don't use magic numbers. The target sum for this test is 10, but will it always be 10?

---

void print(const std::list<int> &nmbrs)
{
    for (const int p : nmbrs)
        std::cout << p << " ";
    std::cout << std::endl;
}    

Every line that gets printed prints an extra delimiter at the end of the list. An extra whitespace character might not do anything, but it certainly isn't intended. Strive for correctness in your programs.

Avoid std::endl. Directly state your intent in code and be aware of what std::endl does. The following two statements are equivalent (ignoring localization).

std::cout << std::endl;
std::cout << '\n' << std::flush;

Again, be explicit with your intent.

std::cout << std::endl;           // Flush intended?
std::cout << '\n';                // Definitely don't flush.
std::cout << '\n' << std::flush;  // Definitely flush.

---

// initialises a list that holds the numbers
std::list<int> nmbrs = {5, 5, 3, 7, 7, 7, 3, 3, 1, 2, 3, 7, 4, 6};

if (nmbrs.size() > 1)                     //if there are at least 2 numbers

Don't say in comments what can be or is already stated in code.

Vowels do not cost $500. Having a smaller variable name because your abbreviation strips vowels or truncates the end doesn't translate to better code or performance. Abbreviations negatively impacts readability and maintainability, which are two very important aspects in programming.

---

Factor out common code into functions. Functions promote reuse and limits the scope for errors (making testing easier).

---

std::list<int>::iterator i = nmbrs.begin();

Use auto to avoid repetition of type names.

---

target_sum(*i, *(i++))

C++ has special rules regarding evaluation order. In this case, the , of the argument list is not a sequence point because the argument list itself is not an expression. Since the arguments are indeterminately sequenced, modifying the variable and trying to access the variable is undefined behavior.

---

// print(nmbrs);

Remove dead code rather than commenting.

---

_getch();

You don't need _getch(); or conio.h. If you need to pause on input, the standard library already provides such a facility (std::cin.get()).

Instead of cluttering your program with unnecessary debugging support code, learn about your terminal emulator and how to use it correctly. Some IDE's provide an option to keep the window open after running. Other IDE's offer a full fledged debugging system (MSVC) where you can use breakpoints to externally "pause" the program.

Answer 2

My personal preference would be to implement the removal algorithm in a style that's at least reasonably close to that used by the algorithms in the standard library. For example, we could have something like this:

template <class T, class F>
void erase_if2(T &in, F f) {
    assert(in.size() >= 2);

    auto prev = in.front();

    for (auto pos = std::next(in.begin()); pos != in.end(); ) {
        auto p = pos++;
        auto temp = prev;

        if (f(temp, *p))
            in.erase(p);
        else
            prev = *p;
    }
}

This would be invoked something like:

std::list<int> numbers = { 5, 5, 3, 7, 7, 7, 3, 3, 1, 2, 3, 7, 4, 6 };
auto cond = [](int a, int b) { return a + b == 10; };

erase_if2(numbers, cond);

Due to the requirements (e.g., apparently required to modify in place) this doesn't follow the standard conventions exactly (e.g., you have to pass the container, not just iterators).

Despite that, we've fulfilled most of the general intent of the standard algorithms. For example, the algorithm can be applied to a variety of containers, not just list, and policy is separated from mechanism. That is, deciding what to erase is independent from the code that does the erasing.

This is still at least a truly single-pass algorithm; that is, each element of the list is visited only once, rather than back-tracking to the previous number under some circumstances.

You could, of course, make this somewhat more generic still. For example, it currently allows/uses exactly two items to determine whether an element should be extracted or not. If we wanted to, we could rewrite it to maintain an arbitrary number of recent elements instead. There are times that could be useful, but it's irrelevant to the current situations, so I've ignored the possibility for now.

Answer 3

I am afraid the reason was not lack of clarity, let alone inefficiency. The code has a number of problems.

• Undefined behaviour in target_sum(*i, *(i++)).

• Missing #include <iterator>, required for std::prev.

• Using non-standard conio.h.

• Implementing the algorithm inside main.

Answer 4

The core logic you have for removing elements from the list is:

std::list<int>::iterator i = nmbrs.begin();
while (i != std::prev(nmbrs.end()))
{
   if (target_sum(*i, *(i++)))
   {
      i = nmbrs.erase(i);
      i--;
   }
}

That code is not correct since target_sum(*i, *(i++)) has undefined behavior. I suggest changing that block of code to:

std::list<int>::iterator i = nmbrs.begin();
int prev = *i;
for ( ++i; i != nmbrs.end(); )
{
   int cur = *i;
   if ( target_sum(prev, cur) )
   {
      i = nmbrs.erase(i);
   }
   else
   {
      ++i;
   }
   prev = cur;
}