How to get the first n elements of a std::map

Question

Since there is no .resize() member function in C++ std::map I was wondering, how one can get a std::map with at most n elements.

The obvious solution is to create a loop from 0 to n and use the nth iterator as the first parameter for std::erase().

I was wondering if there is any solution that does not need the loop (at least not in my user code) and is more "the STL way to go".

Alex

Hmm.. I'd say using an iterator loop is the STL way to go, isn't it? – Haroun

There is no std::erase. Use std::map<Key,Val,Pred,Alloc>::erase() – Prearrange

Answer 1

You can use std::advance( iter, numberofsteps ) for that.

Irmine

Answer 2

Universal solution for almost any container, such as std::list, std::map, boost::multi_index. You must check the size of your map only.

template<class It>
It myadvance(It it, size_t n) {
   std::advance(it, n);
   return it;
}

template<class Cont>
void resize_container(Cont & cont, size_t n) {
    cont.erase(myadvance(cont.begin(), std::min(n, cont.size())), 
                 cont.end());
}

Prearrange

it's void std::advance(), so this did not compile. – Alex

+1, but if you were tidying this up for release you'd have to make up your mind what concept resize_container operates on. The function and template parameter names suggests any container. The function parameter name suggests any map. As written I think it will in fact work on any Sequence or Associative Container, which unfortunately means its domain is a polyphyletic group in the C++ taxonomy. – Edelstein

Does that sound pretentious, at all? ;-) I just mean that "Erasable" or whatever isn't a natural part of the way C++ containers are classified, because Sequence and Associative Container each have their own almost but not quite compatible erase functions. – Edelstein

Answer 3

The correct way for this is to use std::advance. But here is a funny (slow) way allowing to 'use resize on map'. More generally, this kind of trick can be used for other things working on vector but not on map.

map<K,V> m; //your map
vector< pair<K,V> > v(m.begin(), m.end());
v.resize(n);
m = map<K,V>(v.begin(),v.end());

Aftonag

Answer 4

Just use this simple code

    int cnt = n;
    for(auto it = mp.cbegin(); it != mp.cend(); ++it)
    {
        if(cnt == 0) {
            return;
        }
        cout << it->first << "" << it->second << endl;
        cnt--;
    }

Adler

Answer 5

Why would you want to resize a map?

The elements in a map aren't stored in any order - the first 'n' doesn't really mean anything

edit:
Interestingly std::map does have an order, not sure how useful this concept is.
Are the entries in the same sort order as the keys?
What does that mean? If you have Names keyed by SSN does that mean the names are stored in SSN numeric order?

Lotz

Aren't the elements ordered by key? – Coconut

Not in the way you think, the elements are in some order in memory. There is a hash algorithm that converts the key into an index. But the elements for key1 and key2 aren't necessarily next to each other. – Lotz

@mgb No, that would be a hash table. An std::map is a binary search tree (usually a red-black tree to be specific). The elements in an std::map are therefore stored in a way that makes iterating in order easy and fast. – Wolford

I was thinking the same as Andreas Brinck. I did store some results in a map and wanted to get out the n elements, that fit best. That's why I'd throw away the rest. (So in fact, I would not resize, i would shrink the map.) But if I get you right, I'll get a my n results, but they are not guaranteed to be the n with the smallest key value? – Alex

@Adhemar: My post came too late. Thank you for clarifying that. – Alex

What I mean is that if you have an iterator it and then do: jt = it; ++jt; isn't it->first guaranteed to be less than jt->first? – Coconut

It is probably implemented as a red-black tree but it doesn't have to be - as long as the same key maps onto the same value I can implement it however I want. All the standard requires is that it is stable and iterable. – Lotz

std::map, unlike java map, is always sorted so "the first n" has semantic meaning: it means they are before everything else in the map. The fact that the implementation is a RB tree is irrelevant, they are still ordered. – Madly

Answer 6

A std::map is not a list. There are no "first n" elements.

BTW: Iterators become invalid if the container is changed.

If you really need a smaller map you could iterate though it and add all elements up to the n-th into a new map.

Underbrush

Well, the elements are sorted by their key aren't they? – Obie

@Nailer: Nice, I didn't know that. This link confirms: cplusplus.com/reference/stl/map – Charismatic

Yes, they are. But a map is "most likely implemented as a (balanced) tree of nodes" (quote "The C++ programming language", Bjarne Stroustrup), not a list. So mymap[n] doesn't make any sense. – Underbrush

According to sgi's documentation, std::map's iterators don't become invalid after the container is changed: "Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. " -- sgi.com/tech/stl/Map.html – Magbie

the iterator invalidation (or not) is irrelevant here. We will use map.erase(iterator1, iterator2), any 'iterator invalidation' problem would make this function impossible to use, and we assume that STL functions are not impossible to use ;-) – Aftonag

There are "first n" elements, it just does not mean the same thing as with a list: it means everything after them is "greater" as determined by the Strict Weak Ordering defined when creating the map (default std::less<Key>) – Madly

I am aware of that. But the OP wants a map "with at most n elements". Chopping of all elements larger than n is not like unlinking a list or shortening an array. Since std::map is organized like a tree, chopping is probably rather expensive... – Underbrush