Can I access the elements in a c++ std::map by an integer index?

Question

I have a map of elements that I would like to iterate through. Of course, the standard way to do that would be using a for loop with

for (map<string, int> iterator it = myMap.begin(); it != myMap.end(); ++it) {
    string thisKey = it->first;
    int thisValue = it->second;
}

but if I try and make this loop run parallel using OpenMP's parallel for construct, it doesn't work, and this is (apparently) a known issue, as it doesn't recognize this sort of loop construct.

So, my backup plan was to use an integer index iterator, and access the list of keys and values by index, as I would do in C# like so:

for (int i = 0; i < myMap.Count; ++i) {
    string thisKey = myMap.Keys[i];
    string thisValue = myMap.Values[i];
}

... yet I can't seem to find an equivalent method in C++. Is there a way to do this in C++ that I'm unaware of?

Solution 1

I don't know anything about OpenMP, so I don't know if it will optimize the following or not. But you could use std::advance, like so:

#include <map>
#include <string>
#include <iterator>
#include <iostream>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  for(int i = 0; i < m.size(); ++i) {
    Map::iterator it = m.begin();
    std::advance(it, i);
    std::string thiskey = it->first;
    int thisValue = it->second;
    std::cout << thiskey << "\n";
  }
}

But do be aware that std::advance is O(n), so your (single-threaded) complexity is O(n^2).

---

EDIT

std::vector<Map::value_type> v(m.begin(), m.end());

thus:

#include <map>
#include <string>
#include <iterator>
#include <iostream>
#include <vector>

typedef std::map<std::string, int> Map;

int main() {
  Map m;
  m["one"] = 1;
  m["two"] = 2;
  int i = 0;
  for( std::vector<Map::value_type> v(m.begin(), m.end());
    i < v.size(); ++i) {
    std::string thiskey = v[i].first;
    int thisValue = v[i].second;
    std::cout << thiskey << "\n";
  }
}

Solution 2

Here are a few options that are relatively painless.

1. Keep a std::vector or std::deque for array access, and a separate map of values. The leg work of ensuring that they are consistent is your problem.

2. Use boost::multi_index to ensure consistency between the two index structures. As a word of warning, compile times are pretty long with this option. Consider using the pimpl idiom if you go this route.

I have no experience with OpenMP, so I cannot speculate if either of these options would be worthwhile in practice.

Comments

[Charles]

I actually tried that.. it is horribly slow. I lose almost all the time I gain by running it multi-threaded, and I have 24 threads going. My present solution right now is to declare a vector<string> and a vector<int>, resize them, and dump the data into the vectors, then access them that way.. it adds very little overhead but it seems like such a kluge.

[matth]

It might be better to keep a single vector of map::value_type. See my edit. (Hmmm, but that won't reserve enough initial memory.)