Hello.
I have a map
map<int, vector<int> >
and I want to find which one of the vectors has the most elements.
Is there a built in function that does that or do I have to write my
one code.
That depends... (BTW thanks for the interesting exorcise.)
'max_element' will return the first iterator that satisfies the binary
predicate, so:
----------------------------------------------------------------------
typedef map< int, vector<int> > IntMap;
bool comp_sizes( const IntMap::value_type& lhs,
const IntMap::value_type& rhs ) {
return lhs.second.size() < rhs.second.size();
}
void foo( const IntMap& m ) {
IntMap::const_iterator it = max_element( m.begin(), m.end(),
&comp_sizes );
// 'it' points to the one you want, or m.end() if m was empty.
}
----------------------------------------------------------------------
If you want the last key, then use rbegin() and rend().
If however you want all of the keys with the biggest vectors, then:
----------------------------------------------------------------------
template < typename OutIt >
void copy_keys_with_biggest_vectors( IntMap::const_iterator begin,
IntMap::const_iterator end, OutIt result ) {
if ( begin != end ) {
begin = max_element( begin, end, comp_sizes );
vector< int >::size_type target = begin->second.size();
while ( begin != end ) {
if ( begin->second.size() == target )
*result++ = begin->first;
++begin;
}
}
}
----------------------------------------------------------------------
If you find that you are collecting keys based on some predicate in
several places in your code then you might want to consider a more
generic algorithm:
----------------------------------------------------------------------
template < typename FwIt, typename OutIt, typename Pred >
void copy_keys_if( FwIt begin, FwIt end, OutIt result, Pred pred ) {
while ( begin != end ) {
if ( pred( *begin ) )
*result++ = begin->first;
++begin;
}
}
----------------------------------------------------------------------
Then you can collect all the keys of vectors that have a particular size
by:
----------------------------------------------------------------------
struct has_size {
size_t target;
has_size( size_t target_ ) : target( target_ ) { }
bool operator()( const IntMap::value_type& elem ) const {
return elem.second.size() == target;
}
};
vector< int > keys;
copy_keys_if( intMap.begin(), intMap.end(), back_inserter( keys ),
has_size( target ) );
----------------------------------------------------------------------
