Selecting an element from a list

[Tinnin]

Hi all.
I'm working my way through "Accelerated C++" have a question regarding chapter 5.
The program calculates students final grades by taking a median of the homework grades.
I am trying to alter this program so that it uses list instead of vector.
The issue I'm having is with the median function. The function selected values from the middle of the vector but on changing it to list I am struggling to make it work.
How could I select the middle value of the list?

Many thanks.

// source file for median function

#include <algorithm>
#include <stdexcept>
#include <list>

using std::domain_error;    using std::sort;    using std::list;

double median(list<double> vec)
{
    typedef list<double>::size_type vec_sz;

    vec_sz size = vec.size();
    if(size==0) throw domain_error("median of an empty list");

    sort(vec.begin(),vec.end());

    vec_sz mid=size/2;

    for(list<double>::const_iterator it=vec.begin(); it!=vec.end(); ++it)   // Start of "list" median calculation
    {
        if(it == mid)
        {
            return size%2==0 ? (vec[*it]+vec[*it-1])/2 : vec[*it];
        }
    }                                                                       // End of "list" median calculation

    /*return size%2==0 ? (vec[mid]+vec[mid-1])/2 : vec[mid];*/              // Calculation when using "vector"
}

[np complete]

Have you tried it with if(it == mid + 1) or if(it == mid - 1) ?

[Tinnin]

Well, my main issue here seems to be that the comparison is between "it" of type const_iterator and "mid" of type size_type. As far as I can tell in my inexperience, this won't work. I left this in though just to show my train of thought.

[zvjezdan.veselinovic]

Couldn't you do it a different way? Like:

vector<float> grades;
float grade1, grade2, grade3; // and so on

then make a question and do

cin >> grade1;
grades.push_back(grade1);

and do that for all of your grades. Then just look in the middle spot

cout << "Median = " << grades.at(1) << endl;

for the median?

or if you needed to sort them you can do

sort(grades.begin(), grades.end());

[Tinnin]

The point of the exercise is to use list throughout rather than vector.

[zvjezdan.veselinovic]

Sorry, I am getting new glasses. I did not read the italics correctly. My bad.

[zvjezdan.veselinovic]

Is there any way you can call it individually like a vector? I am not that familiar with lists myself, hense the newbness. I am familiar with

cout << vector1.at(0) << endl; 

I think in line 18, couldn't you do

vec_sz mid = vect_sz.size()/2;

then just make an if statement and call out that specific location?

[zvjezdan.veselinovic]

I'm just trying out ideas.

[vijayan121]

The point of the exercise is to use list throughout rather than vector.

Yes; the point of the exercise is to understand the difference between using a sequence container like std::vector<> that provides random access to its values and one like std::list<> that does not.

double median( list<double> vec )
{
    typedef list<double>::size_type vec_sz ;
    vec_sz size = vec.size() ;
    if(size==0) throw domain_error("median of an empty list");

    // std::list<> does not provide random access to the values
    // std::list<>::iterator is not a random_access_iterator
    // we can't use std::sort() which requires random acccess iterators
    // http://en.cppreference.com/w/cpp/algorithm/sort
    // instead use the member function list<>::sort
    // http://en.cppreference.com/w/cpp/container/list/sort

    // sort(vec.begin(),vec.end());
    vec.sort() ;

    vec_sz mid=size/2;

    // std::list<> does not provide random access;
    // it does not have a subscript operator
    // we have to iterate linearly using its bidirectional iterator
    // keeping a count of the position and keeping track of the previous value

    /*
    for(list<double>::const_iterator it=vec.begin(); it!=vec.end(); ++it)   // Start of "list" median calculation
        {
            if(it == mid)
            {
                return size%2==0 ? (vec[*it]+vec[*it-1])/2 : vec[*it];
            }
        }
    */

    list<double>::size_type position = 0 ;
    double previous ;
    for( list<double>::iterator iter = vec.begin() ; iter != vec.end() ; ++iter )
    {
        if( position == mid ) return size%2==0 ? ( previous + *iter ) / 2 : *iter ;
        previous = *iter ;
        ++position ;
    }
}

If you have a current (C++11) compiler:

double median( list<double> seq )
{
    auto size = seq.size() ;
    if(size==0) throw domain_error("median of an empty list");

    seq.sort() ;

    auto mid = size / 2 ;

    list<double>::size_type position = 0 ;
    double previous ;
    for( double value : seq )
    {
        if( position == mid ) return size%2==0 ? ( previous + value ) / 2 : value ;
        previous = value ;
        ++position ;
    }
}

[Tinnin]

Great, that works. Thanks vijayan121.
And thank you zvjezdan.veselinovic. Any offer of help is much appreciated :)