finding the mode in a vector

[kohlh]

I am working on a basic problem with vectors. How to find the mode. I have searched the internet and this forum and have not found a good answer, usually too confusing. I do not have any code written (for finding the mode) becuase I do not know where to start. I am doing this for homework and this is for extra points for creativity (I already made the mean, median and range). I have seen solutions that involve maps which seem to be designed for this task but could not understand the implementation given in that post specifically how to create the map and than assign the vector to the map. also I have thought the problem through and come to the idea that I could loop through the vector and check each element for equality to all other elements but this is sloppy and a work around. Here is the code so far for the rest of the program so that the answer given can be centered on the same style of implementation used.

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int main ()
{
	vector <double> HW3;    //declares a vector to store our data
	double num;             //declares a double to read data into vector
	double sum=0;   //declares a double to add the values of the vector elements

	cout<<"Enter in whole or decimal numbers, positive or negative."<<endl
		<<"When you are done entering data enter any letter to finish."<<endl;
	while(cin>>num)         
	{                         //allows user input of data, pushes that data 
		HW3.push_back(num);    //into the end of the vector untill cin fails
	}
	sort(HW3.begin(),HW3.end());//sorts vector elements into ascending order
	cout<<endl;
	for(double i=0;i<HW3.size();++i)
	{
		cout<<HW3[i]<<" ";           //displays sorted vector
	}
	cout<<endl<<"Total indices "<<HW3.size()<<endl;
	cout<<"The smallest value is "<<HW3.front()<<"."<<endl
	    <<"The largest value is "<<HW3.back()<<"."<<endl;  //displays the first and the last index in the vector                                                   

	for(int i=0;i<HW3.size();++i) //loops throught the vector
	{                                
		sum+=HW3[i];     //adds all the values of the elements in the vector and assignes it to sum
	}
	cout<<"The sum of all the values is "<<sum<<"."<<endl;         //displays the sum of the element values in the vector
	cout<<"The mean of all the values is "<<sum/HW3.size()<<"."<<endl;//displays the average of the element values
	if(HW3.size()%2==1)
	{
		int i=(HW3.size())/2;
		cout<<"The median is "<<HW3[i]<<endl;
	}
	else
	{
		double x=(HW3.size()/2.0);
		double y=((HW3.size()-1)/2.0);
		cout<<"The median is "<<((HW3[x]+HW3[y])/2.0)<<endl;
	}

	cout<<"The range is "<<abs(HW3.front()-HW3.back())<<endl;

	system("pause");
	return 0;
}

[cire]

You've sorted your vector, so it's fairly straightforward. Iterate through it while counting runs of the same value. The largest such run(s) will be your mode(s.)

[kohlh]

Please elaborate maybe with an example and what about multiple runs IE two modes

[cire]

#include <iostream>
#include <vector>

double values[] = 
{
    1.0, 1.0,
    2.0, 2.0,
    3.0, 3.0, 3.0,
    4.0, 4.0, 4.0, 4.0, 4.0,
    5.0, 5.0, 5.0, 5.0, 5.0,
    6.0, 6.0, 6.0, 6.0,
};

typedef std::vector<double> vec_type ;

vec_type getMode( const vec_type& v ) ;
void print( const char* msg, const vec_type& v ) ;

int main()
{
    vec_type v(values, values+sizeof(values)/sizeof(values[0])) ;
    print("Modes", getMode(v)) ;
}

// PRE: v.empty() != true; v is sorted.
// POST: a non-empty vector of distinct modal values is returned.
vec_type getMode( const vec_type& v )
{
    vec_type modes ;
    vec_type::const_iterator it = v.begin() ;

    double runValue = *it++ ;
    unsigned runCount = 1 ;
    unsigned highestRunCount = runCount ;
    modes.push_back(runValue) ;

    while ( it != v.end() )
    {
        if ( runValue == *it )                      // run continuing.
        {
            if ( ++runCount > highestRunCount )     // current run is new high?
            {
                highestRunCount = runCount ;

                if ( modes.front() != runValue )    // then there should only be one mode
                {
                    modes.clear() ;
                    modes.push_back(runValue) ;
                }
            }
            else if ( runCount == highestRunCount ) // more than one mode, currently
                modes.push_back(runValue) ;
        }
        else                                        // new run beginning
            runValue = *it, runCount = 0 ;

        ++it ;
    }

    return modes ;
}

void print( const char* msg, const vec_type& v)
{
    std::cout << msg << '\n' ;

    for ( vec_type::const_iterator it = v.begin(); it != v.end(); ++it )
        std::cout << *it << '\t' ;
    std::cout << '\n' ;
}

[Stewbond]

Here's one:

#include <iterator>
#include <vector>
#include <algorithm>

// Returns the first mode of all elements in the range [first, last)
// If no mode is found, 0 is returned.
template <class Iter>
typename std::iterator_traits<Iter>::value_type
	Mode(Iter first, Iter last)
{
	typedef typename std::iterator_traits<Iter>::value_type type_t;

	std::vector<type_t> arr (first, last);

	std::sort(arr.begin(), arr.end() );

	type_t output = type_t();
	int final_frequency = 0;
	int local_frequency = 0;

	for (typename std::vector<type_t>::iterator it = arr.begin(); it != arr.end()-1; ++it)
	{
		if (*it == *(it+1)) local_frequency++;
		else                local_frequency = 0;

		if (local_frequency > final_frequency)
		{
			final_frequency = local_frequency;
			output = *it;
		}
	}

	return output;
}

Usage:

std::vector<int> SomeVect;
// ... Populate SomeVect ...
int myMode = Mode( SomeVect.begin(), SomeVect.end() );

or

int SomeArr[10];
// ... Populate SomeArr ...
int myMode = Mode(SomeArr, SomeArr+10);

Edit: Adding cire's multi-mode support while keeping the same parameter list:

#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>

template <class Iter>
std::vector<typename std::iterator_traits<Iter>::value_type>
    Modes(Iter first, Iter last)
{
    typedef std::vector<typename std::iterator_traits<Iter>::value_type> vect_t;

    vect_t arr (first, last);
    vect_t modes;

    std::sort(arr.begin(), arr.end() );

    typename vect_t::const_iterator it = arr.begin() ;

    double runValue = *it++ ;
    unsigned runCount = 1 ;
    unsigned highestRunCount = runCount ;
    modes.push_back(runValue) ;

    while ( it != arr.end() )
    {
        if ( runValue == *it )                      // run continuing.
        {
            if ( ++runCount > highestRunCount )     // current run is new high?
            {
                highestRunCount = runCount ;

                if ( modes.front() != runValue )    // then there should only be one mode
                {
                    modes.clear() ;
                    modes.push_back(runValue) ;
                }
            }
            else if ( runCount == highestRunCount ) // more than one mode, currently
                modes.push_back(runValue) ;
        }
        else                                        // new run beginning
            runValue = *it, runCount = 0 ;

        ++it ;
    }

    return modes ;
}

int main()
{
    double values[] =
    {
        1.0, 1.0,
        2.0, 2.0,
        3.0, 3.0, 3.0,
        4.0, 4.0, 4.0, 4.0, 4.0,
        5.0, 5.0, 5.0, 5.0, 5.0,
        6.0, 6.0, 6.0, 6.0,
    };

    auto mod = Modes(values, values+21);

    for (auto i : mod)
        std::cout << i << ' ';
}