STL style function to find the middle of an STL container

Question

I ' m a newcomer in C++ and I kindly request for help to resolve an issue.

I'm writing a simple STL style function , that should return the middle element of sequence (vector, list etc)

Here is my function, I try to use the concept of iterator

template <class It, class T> It  middle(It first, It last) 
{

    while(first!=last){
        ++first;
        --last;
    }
    return first;
}

here is my main, trying to call middle for a vector of ints (I've omitted includes)

int main() {
    vector<int>vi;
    int x;
    cout<<"Enter vector elemets...";
    while (cin>>x)
    vi.push_back(x);
    cout<<endl;
    cin.clear();
    cout<<"the vector is:"<<endl;
    for(int i=0;i<vi.size();++i)
    cout<<vi[i]<<" ";
    cout<<endl;
    vector<int>::iterator first=vi.begin();
    vector<int>::iterator last=vi.end();
    vector<int>::iterator ii=middle(first,last);
    cout<<"The middle element of the vector is: "<<*ii<<endl;
}

When compiling with g++ I get the following error:

myex21-7.cpp:79: error: no matching function for call to ‘middle(__gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >&, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > >&)’

Could somebody give me some tips to resolve it? Thanks for any help in advanced snek

Answer 1

How about:

auto middle = container.begin();
std::advance(middle, container.size()/2);

If you have C++11 available, std::next lets you do the same in one line instead of two.

Also note that in the case of a container that supports random access iterators (e.g., std::vectoror std::deque) this will be relatively efficient (constant complexity instead of linear complexity).

Answer 2

Unless this is an exercise, it might be simpler to implement something in terms of std::next. Ignoring for now the special case of containers with an even number of elements, you could use something like this:

std::vector<SomeType> v = ....;
auto mid = std::next(v.begin(), v.size()/2);

As for the problem with your code, your middle function template has two parameters:

template <class It, class T> It  middle(It first, It last) { .... }

But there is no way for the second parameter to be deduced from the function arguments. Since the parameter is not needed anyway, you can simply remove it:

template <class It> It  middle(It first, It last) { .... } 

Answer 3

The other answers here are interesting, but they require access to the container itself. To be truly STL style, you should work with iterator ranges. Here's a solution that does the efficient thing for random access iterators, but also works for forward iterators

// http://ideone.com/1MqtuG

#include <iterator>

template <typename ForwardIt>
ForwardIt DoMidpoint(ForwardIt first, ForwardIt last, std::forward_iterator_tag)
{
    ForwardIt result = first;

    // Try to increment the range by 2
    bool sawOne = false;
    // EDIT: Note improvements to this loop in the comments

    while(first != last)
    {
        ++first;
        if (sawOne)
        {
            // If that succeeded, increment the result by 1
            ++result;
            sawOne = false;
        }
        else
        {
            sawOne = true;
        }
    }

    return result;
}

template <typename RandomAccessIt>
RandomAccessIt DoMidpoint(RandomAccessIt first, RandomAccessIt last, std::random_access_iterator_tag)
{
    return first + (last - first)/2;
}

template <typename ForwardIt>
ForwardIt midpoint(ForwardIt first, ForwardIt last)
{
    return DoMidpoint(first, last, typename std::iterator_traits<ForwardIt>::iterator_category());
}