How can I traverse/iterate an STL map?
Solution 1
Yes, you can traverse a Standard Library map
. This is the basic method used to traverse a map
, and serves as guidance to traverse any Standard Library collection:
C++03/C++11:
#include <cstdlib>
#include <map>
#include <string>
using namespace std;
int main()
{
typedef map<int,string> MyMap;
MyMap my_map;
// ... magic
for( MyMap::const_iterator it = my_map.begin(); it != my_map.end(); ++it )
{
int key = it->first;
string value = it->second;
}
}
If you need to modify the elements:
- Use
iterator
rather thanconst_iterator
. -
Instead of copying the values out of the iterator, get a reference and modify the values through that.
for( MyMap::iterator it = my_map.begin(); it != my_map.end(); ++it ) { int key = it->first; string& value = it->second; if( value == "foo" ) value = "bar"; }
This is how you typically traverse Standard Library containers by hand. The big difference is that for a map
the type of *it
is a pair
rather than the element itself
C++11
If you have the benefit of a C++11 compiler (for example, latest GCC with --std=c++11
or MSVC), then you have other options as well.
First you can make use of the auto
keyword to get rid of all that nasty verbosity:
#include <cstdlib>
#include <map>
#include <string>
using namespace std;
int main()
{
map<int,string> my_map;
// ... magic
for( auto it = my_map.begin(); it != my_map.end(); ++it )
{
int key = it->first;
string& value = it->second;
}
}
Second, you can also employ lambdas. In conjunction with decltype
, this might result in cleaner code (though with tradeoffs):
#include <cstdlib>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
map<int,string> my_map;
// ... magic
for_each(my_map.begin(), my_map.end(), [](decltype(*my_map.begin()) val)
{
string& value = val.second;
int key = val.first;
});
}
C++11 also instroduces the concept of a range-bases for
loop, which you may recognize as similar to other languages. However, some compilers do not fully support this yet -- notably, MSVC.
#include <cstdlib>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
map<int,string> my_map;
// ... magic
for(auto val : my_map )
{
string& value = val.second;
int key = val.first;
}
}
Solution 2
As with any STL container, the begin()
and end()
methods return iterators that you can use to iterate over the map. Dereferencing a map iterator yields a std::pair<const Key, Value>
.
Solution 3
C++17
Since C++17 you can use range-based for loops together with structured bindings for iterating over a map. The resulting code, e.g. for printing all elements of a map, is short and well readable:
std::map<int, std::string> m{ {3, "a"}, {5, "b"}, {9, "c"} };
for (const auto &[k, v] : m)
std::cout << "m[" << k << "] = " << v << std::endl;
Output:
m[3] = a
m[5] = b
m[9] = c
Solution 4
You can traverse STL map in the same way as any other STL container: using iterators, e.g.
for (std::map<key, value>::const_iterator
i = myMap.begin(), end = myMap.end(); i != end; ++i)
{
// *i is a key-value pair
}
Solution 5
Using for
with auto
for C++11 and above usage
map<int,int> map_variable; //you can use any data type for keys, as well as value
for(auto &x:map_variable)
{
cout<<x.first ;// gives the key
cout<<x.second; //gives the value
}
The newer format of for
using auto
was introduced in C++11
To give it functionality like some higher level languages like python
Where there was already an implementation of such type of iteration
P.S. : map variable keeps values sorted, so when iterating you will get keys in sorted order
Related videos on Youtube
Comments
-
atoMerz about 4 years
I want to traverse an STL map. I don't want to use its key. I don't care about the ordering, I just look for a way to access all elements it contains. How can I do this?
-
Nim over 13 yearsrefer to: cplusplus.com/reference/stl/map/begin
-
-
ROAR over 13 yearsIn the latest version of C++ standard you can replace the lengthy iterator decelerations with the auto keyword.
-
Matthieu M. over 13 yearsI do wonder: in generally, does a compiler automatically lifts the
myMap.end()
outside of the loop ? Lifting invariants is a common optimization but I do wonder if it gets detected, I suppose it could with the implementation being inlined, but I don't know. Thoughts ? -
fredoverflow over 13 years@RA: Or even better, a range based for loop. g++ 4.6.0 already supports this.
-
Steve Jessop over 13 years@RA: strictly speaking, in the latest proposal for the next version of the C++ standard, you can do that thing you said.
-
Steve Jessop over 13 years@Matthieu: main thought is that
myMap.end()
is almost certainly a trivial operation. Barely worth lifting, especially considering that iterating a map isn't a very cache-friendly operation. -
Steve Jessop over 13 years@Matthieu: after some header-diving: in the GNU implementation, an iterator holds a pointer to a node, and the "end node" of a map is embedded in the object. So I think that assuming several layers of calls can be inlined, constructing and returning an end iterator is basically a pointer copy, and if you're lucky
i != myMap.end()
could just be a compare of the address stored ini
, withmyMap+offset
. I haven't disassembled any code to check, though. -
Steve Jessop over 13 years@John: I think you can use
auto & val
in your range-based for statement. We'll reach a proper type-inferred language some day... -
John Dibling over 13 years@Steve: Edited. I'll verify once i get G++ installed. Until then I'm trusting you!
-
Steve Jessop over 13 years@John: I'm pretty sure just by looking at the definition of range-based for loop that
auto
is OK. My doubt aboutauto &
is thatauto
does a somewhat fiddly thing equivalent to template argument deduction, so I may have missed something. I don't have a good enough compiler to test either. -
Martin York over 13 yearsYou keep copying the value out of the iterator. You should use a references as this then allows manipulation of the data within the map.
string& value = val.second;
I think any (average) user manipulating the value would expect the internal representation of the map to change. -
EddieV223 over 11 yearsThis is wrong, not all STL container iterators yield std::pair. There is no need for a pair in vector or list for example.
-
fredoverflow over 11 years@EddieV223 fair enough, I clarified my answer.
-
thecoshman over 11 yearsAs this is now a c++-faq answer, perhaps it can be cleaned up so that it is neater.