STL style function to find the middle of an STL container

Question

I am new to C ++ and kindly ask for help to solve the problem.

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

Here is my function, I am trying to use the iterator concept

template <class It, class T> It middle(It first, It last) { while(first!=last){ ++first; --last; } return first; } 

here is my main one, trying to call middle for an ints vector (I skipped include)

 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> > >&)' 

Can someone give me some advice on how to fix it? Thanks for any help in advanced snacks.

Answer 1

What about:

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

If you have C ++ 11, std::next allows you to do the same thing on one line instead of two.

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

Answer 2

If this is an exercise, it may be easier to implement something in terms of std::next . Ignoring the special case of containers with an even number of elements, you can 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 to deduce the second parameter from function arguments. Since the parameter is still not needed, you can simply delete 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 have to work with ranges of iterators. Here's a solution that does an effective thing for random access iterators, but also works for advanced 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()); } 

Answer 4

There are several types of iterators in STL, random access vector functions, which means you can get an iterator in the middle element

 auto middle = v.begin() + v.size()/2; 

Answer 5

Here is another way:

Assuming that first and last are iterators in the begin() and end() container, then:

 Iterator middle = first; std::advance( middle, std::distance( first, last ) / 2 );