#include <iostream>
#include <functional>
#include <list>
#include <iterator>


int reduce (std::list<int> l,std::function<int(int a,int b)> f,int start){
int sum=start;
 for(auto i1=l.begin();i1!=l.end();  i1){
   auto i2=  i1;
     sum =f((*i1),(*i2));
       i2;
 }

return sum;

}


int main(){

  std::list<int> list{11,4,5,12,6,8,9};

  auto a=[](int a,int b){return a b 1;};

  int start=-12;

  int o=reduce(list,a,start);

  std::cout<<"Output: "<< o<<std::endl;

}

I have to write a reduce function that takes a list of integers as the first argument, second argument is a function that will reduce the elements of the container to one element and the third is initial value of the given accumulation (-12 in this example). It should reduce the elements of the passed container to 1 element using the function passed as an argument. The output should be 50.

When I write cout in for loop in order to see the output, iterators are returning elements which they should but why am I getting an inifite loop, is it because i2 line will come out of the container? What is the better way to write this code? How can I solve this problem so that second iterator doesn't reach outside of the container.What is your advice when it comes to iterating through list container? Thanks a lot

CodePudding user response：

I think you are misunderstanding the task you have been asked to perform. This is my take

int reduce(std::list<int> l, std::function<int(int a,int b)> f, int start) {
    for (auto it = l.begin(); it != l.end();   it) {
        start = f(*it, start);
    }
    return start;
}

That's the normal mathematical definition of reduce

CodePudding user response：

The problem is that you increase i1 twice in the loop, which for a list of uneven number of elements will skip over the end iterator. So your loop goes beyond the end and into undefined behavior.

You need to fetch one element at a time, but do it twice. And if one of them is the end iterator you need to stop.

For example:

auto i1 = begin(l);
while (true)
{
    if (i1 == end(l))
    {
        // The end of an even-numbered list
        break;
    }
    auto value1 = *i1  ;

    if (i1 == end(l))
    {
        // The end of an odd-numbered list
        // Here we skip the last element, which is value1
        break;
    }
    auto value2 = *i1  ;

    sum  = f(value1, value2);
}

I also recommend you think about how the standard library handles generic containers, and accept an iterator pair instead. Then you can use any type of container.

CodePudding user response：

Theres too much in your code. You do not need any. Also you need to decide what to do with a list with odd number of elements as in your case. Incrementing begin in steps of two will never make the iterator equal end when number of elements is odd. In the below code I decided to not call the function and return when the next iterator is the end.

I suppose your adding elements is just a simplified example, because for that sum it doesnt matter in which order the elements are added nor is adding them in pairs necessary.

#include <iostream>
#include <functional>
#include <list>
#include <iterator>

int reduce(std::list<int> l,std::function<int(int a,int b)> f,int start){
    int sum=start;
    for(auto it=l.begin(); it!=l.end(); std::advance(it,2)) {
        if (std::next(it) == l.end()) return sum;
        sum  = f((*it),(*(std::next(it,1))));     
    }
    return sum;
}

int main(){
  std::list<int> list{11,4,5,12,6,8,9};
  auto a = [](int a,int b){
      std::cout << a << " " << b << "\n"; // some poor-mans-debugging
      return a b 1;
  };
  int start = -12;
  int o = reduce(list,a,start);
  std::cout << "Output: "<< o << std::endl;    
}

Live Demo

std::list iterators are not random access, hence it =2 wont work. The equvalent to = is std::advance. It advances the iterator. std::next does not modify the iterator, but only returns the next iterator.

The code could be made a tiny bit more performant, because currently it increments the same iterator twice. Though this would be at the cost of readability and maybe the compiler will already optimize this. When in doubt profile and study the assembly, but for now I wouldnt worry about it too much.