Need help with std::map function

[vaderboi]

I am having a really hard time understanding how to use std::map. In my program below, I am placing elements from vector elementList that could quality to be the majority element in to the map, majorityElements. (The majority element is defined as appearing more than N(the size of the array)/ 2 times). After I place potential candidates in majorityElements, I want to iterate through it and check to see which key value returns the highest mapped value. To do this, I want my program to iterate through the majorityElements and every time it encounters a new highest mapped value it places value in the second map, greatestElement which should ever only have one value. Then after I have figured out the highest mapped value in greatestElement, I will determine if it is more than or equal to N / 2 and therefore if it is a majority element. If it isn't, that means the program has determined that there is no majority element.

I don't start getting compiler errors until the else-if condition within the
second for loop. My question is: how can I compare the current indexed mapped value in majorityElements to the single value in greatestElement to see which mapped value is greater? And if the program determines that the current indexed mapped value in majorityElements is greater than the single value in greatestElement, how do I swap them?

Here are the two errors the compiler threw:

On the else-if line: "error: no match for `operator>` (operand types are `std::map<int,int>::iterator {aka std::_Rb_tree_iterator<std::pair<const int, int> > }` and `std::map<const int, int>::iterator {aka std::_Rb_tree_iterator<std::pair<const int, int> > }`)"

on the function inside of the else-if condition: "error: `std::map<const int, int>::iterator {aka struct std::_Rb_tree_iterator<std::pair<const int, int> > }` has no member named swap."



exercise26.cpp

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


int main()
{

	std::vector<int> elementList;
	std::map<const int, int> majorityElements;
	std::map<const int, int> greatestElement;
	std::map<int, int>::iterator it; 

	elementList = {0, 9, 0, 0, 8, 5, 6};


	for( unsigned int i = 0; i < elementList.size(); i++ )
	{
		it = majorityElements.find(i);

		if( it != majorityElements.end() )
		{
			majorityElements[i]++;
		}
		else
		{
			majorityElements[i] = 1;
		}
	}

	for( std::map<int, int>::iterator secondIt = 
majorityElements.begin(); secondIt != majorityElements.end(); ++secondIt ) 
	{
		if( greatestElement.size() == 0 )
		{
			greatestElement.insert( greatestElement.begin(), majorityElements.begin() );
		}
		else if( secondIt > greatestElement.begin() )
		{
			greatestElement.begin().swap( secondIt );
		}
	}	

	return 0;	
}

[JLBorges]

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

int main()
{
    const std::vector<int> list { 67, 42, 67, 56, 67, 42, 67, 52, 67, 42, 67, 92, 67, 42, 67 } ;

    if( list.empty() ) return 0 ; // quit if list is empty

    // populate a frequency map
    std::map<int,std::size_t> frequency_map;

    // range based loop: http://www.stroustrup.com/C++11FAQ.html#for
    for( int v : list ) ++frequency_map[v] ;
    // note: if [] performs an insertion if the key v does not already exist.
    //       ie. if key does not exist, first insert key-value pair with frequency value == 0
    //                                  and then increment the frequency value to one
    //           if the key does already exist, increment its frequency value

    // determine the highest frequency and print frequencies
    // auto: http://www.stroustrup.com/C++11FAQ.html#auto
    auto highest_frequency_iter = frequency_map.begin() ; // iterator to the highest frequency item
    for( auto iter = frequency_map.begin() ; iter != frequency_map.end() ; ++iter )
    {
        // note: iter->first == const key, iter->second == mapped frequency value
        std::cout << "element: " << iter->first << "  frequency: " << iter->second << '\n' ;

        // update highest_frequency_iter if this iter points to an entry with a higher frequency value
        if( highest_frequency_iter->second < iter->second ) highest_frequency_iter = iter ;
    }

    if( highest_frequency_iter->second > list.size()/2 )
    {
        std::cout << "\nlist has " << list.size() << " values.\n"
                  << "majority element "  << highest_frequency_iter->first
                  << " occurs " << highest_frequency_iter->second << " times.\n" ;
    }
}

http://coliru.stacked-crooked.com/a/ec49209c63322ae9

[Duthomhas]

A “map” is a mapping, more commonly called an associative array in CS.

It is a (key → value) lookup table.

Given a key, you can access an associated value.

For example, the following array is a mapping of number value to name:

const char* number_to_name[] =
{
  "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten"
};

I can get a number’s name by looking it up by the number’s value:

  std::cout << "A newborn is " << number_to_name[ 0 ] << " years old.\n";

The problem with a simple C-style array is that it can only use consecutive integer values as keys. Sometimes you need something a little more sophisticated.

For example, suppose I want to keep the age of people by name:

    "Sandy" → 19
    "Jacob" → 18
    "Katie" → 20

There is no simple way to do this. Fortunately, the Standard Library helps, by providing several associative array types. The oldest is the std::map.

  std::map <std::string, unsigned> person_to_age
  {
    { "Sandy", 19 },
    { "Jacob", 18 },
    { "Katie", 20 }
  };

Now I can look things up with the same ease:

  std::cout << "Sandy is " << person_to_age[ "Sandy" ] << " years old.\n";

Now, for your problem. You seem to be doing it the hard way. You are dancing around the idea of a histogram.

A histogram is a mapping of (value → number of times value appears). Since you are looking for the element with the maximum unique number of appearances, I recommend using a std::multimap, so that you can reverse the mapping (since the number of times a value appears might not be unique).

See https://stackoverflow.com/a/5056797/2706707 for the essentials (and from where I got the following functions).

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

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
    return std::pair<B,A>(p.second, p.first);
}

template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}

int main()
{
  std::vector<int> elementList;
  ...

  // First, we histogram the elementList
  std::map<int,int> histogram;
  for (int elt : elementList)
    histogram[elt]++;

  // Now we want the histogram sorted by the frequency that elements appear
  auto frequencyList = flip_map( histogram );

  // The very last element (being the largest key in the default ordering) will be 
  // the "majority element" IFF:
  //   • the key (frequency) is greater than the (size of the elementList) div 2, and
  //   • the key appears exactly once
  if (frequencyList.size())
  {
    int frequency, element;
    std::tie( frequency, element ) = *frequencyList.rbegin();
    if ( (frequency > elementList.size() / 2) and (frequencyList.count( frequency ) == 1) )
    {
      std::cout << "The majority element is " << element << ".\n";
    }
    else
    {
      std::cout << "There is no majority element.\n";
    }
  }
  else
  {
    std::cout << "There were no elements...\n";
  }
}

Disclaimer: I have not compiled and executed this, so typos may have occurred.

Hope this helps.

[vaderboi]

Thank you both! Both of your code blocks have been very helpful!

[JLBorges]

Now, have a look at this short and sweet version:

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

int main()
{
    const std::vector<int> list { 67, 42, 67, 56, 67, 42, 67, 52, 67, 42, 67, 92, 67, 42, 67 } ;

    if( list.empty() ) return 0 ; // quit if list is empty

    std::map<int,std::size_t> frequency_map;
    for( int v : list ) ++frequency_map[v] ;

    // https://en.cppreference.com/w/cpp/algorithm/max_element
    auto iter = std::max_element( frequency_map.begin(), frequency_map.end(),
                                  []( const auto& a, const auto& b ) { return a.second < b.second ; } ) ;

    if( iter->second > list.size()/2 )
    {
        std::cout << "the list has " << list.size() << " values. majority element "
                  << iter->first << " occurs " << iter->second << " times.\n" ;
    }
}

http://coliru.stacked-crooked.com/a/7e00eab20b323e54

[vaderboi]

Nice! The shorter the better. I used portions of your code, @JLBorges and it compiles and does exactly what I need it to.

[Duthomhas]

Dang, that was dumb of me not to remember I could do what JLBorges did. Nice!

The only thing JLBorges left out was to check that the majority element was unique.

As it stands, you’ll have to make a second pass through the elements to find any majority frequency duplicates:

  auto n = std::count_if( frequency_map.begin(), frequency_map.end(),
             [iter]( const auto& x ) { return x.second == *iter ; } ) ;

  if ((n == 1) and (iter->second > list.size()/2))
  {
    ...

This is still O(2n), so, very good complexity.

[JLBorges]

By definition, the majority element, if it exists, would be unique.
(In s sequence of size n, there can't be more than one element with frequency greater than n/2).

[Duthomhas]

Dang, I need to sleep more. My brain is going stupid.