7

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".

dandan78
  • 13,328
  • 13
  • 64
  • 78
Norbert
  • 73
  • 1
  • 3

6 Answers6

14

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

xtofl
  • 40,723
  • 12
  • 105
  • 192
3

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());
}
Alexey Malistov
  • 26,407
  • 13
  • 68
  • 88
  • it's void std::advance(), so this did not compile. – Norbert Nov 27 '09 at 15:24
  • +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. – Steve Jessop Nov 27 '09 at 15:53
  • 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. – Steve Jessop Nov 27 '09 at 16:02
1

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());
Alink
  • 394
  • 2
  • 4
0

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--;
    }
KaranKulshrestha
  • 176
  • 1
  • 4
-1

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?

Martin Beckett
  • 94,801
  • 28
  • 188
  • 263
  • Aren't the elements ordered by key? – Andreas Brinck Nov 27 '09 at 15:07
  • 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. – Martin Beckett Nov 27 '09 at 15:13
  • 3
    @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. – Tim Nov 27 '09 at 15:17
  • 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? – Norbert Nov 27 '09 at 15:19
  • @Adhemar: My post came too late. Thank you for clarifying that. – Norbert Nov 27 '09 at 15:20
  • 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? – Andreas Brinck Nov 27 '09 at 15:20
  • 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. – Martin Beckett Nov 27 '09 at 15:39
  • 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. – laura Nov 27 '09 at 16:31
-2

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.

EricSchaefer
  • 25,272
  • 21
  • 67
  • 103
  • 3
    Well, the elements are sorted by their key aren't they? – Nailer Nov 27 '09 at 15:06
  • @Nailer: Nice, I didn't know that. This link confirms: http://www.cplusplus.com/reference/stl/map/ – ya23 Nov 27 '09 at 15:29
  • 1
    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. – EricSchaefer Nov 27 '09 at 15:32
  • 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. " -- http://www.sgi.com/tech/stl/Map.html – Eld Nov 27 '09 at 16:10
  • 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 ;-) – Alink Nov 27 '09 at 16:27
  • 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`) – laura Nov 27 '09 at 16:37
  • 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... – EricSchaefer Nov 27 '09 at 18:53