Question

I have python code that contains the following code.

d = {}

d[(0,0)] = 0
d[(1,2)] = 1
d[(2,1)] = 2
d[(2,3)] = 3
d[(3,2)] = 4

for (i,j) in d:
    print d[(i,j)], d[(j,i)]

Unfortunately looping over all the keys in python isn t really fast enough for my purpose, and I would like to translate this code to C++. What is the best C++ data structure to use for a python dictionary that has tuples as its keys? What would be the C++ equivalent of the above code?

I looked at sparse matrices in the boost library, but couldn t find an easy way to loop only over the non-zero elements.

Answer 1

A dictionary would be a std::map in c++, and a tuple with two elements would be a std::pair.

The python code provided would translate to:

#include <iostream>
#include <map>

typedef std::map<std::pair<int, int>, int> Dict;
typedef Dict::const_iterator It;

int main()
{
   Dict d;

   d[std::make_pair(0, 0)] = 0;
   d[std::make_pair(1, 2)] = 1;
   d[std::make_pair(2, 1)] = 2;
   d[std::make_pair(2, 3)] = 3;
   d[std::make_pair(3, 2)] = 4;

   for (It it(d.begin()); it != d.end(); ++it)
   {
      int i(it->first.first);
      int j(it->first.second);
      std::cout <<it->second <<   
                <<d[std::make_pair(j, i)] << 
 ;
   }
}

Answer 2

The type is

std::map< std::pair<int,int>, int>

The code to add entries to map is like here:

typedef  std::map< std::pair<int,int>, int> container;

container m;

m[ make_pair(1,2) ] = 3; //...

for(container::iterator i = m.begin();  i != m.end(); ++i){
   std::cout << i.second <<    ; 
   // not really sure how to translate [i,j] [j,i] idiom here easily
}

Answer 3

Have a look at Boost.python. It s for interaction between python and C++ (basically building python libs using C++, but also for embedding python in C++ programs). Most pythons data structures and their C++ equivalents are described (didn t checked for the one you want).

Answer 4

std::map or more likely std::tr1::unordered_map / boost::unordered_map (aka hash_map) is what you want.

Also, as kriss said, Boost.Python is a good idea to look at here. It provides a C++ version of python s dict class already, so if you re doing cross-language stuff, it might be useful.

Answer 5

Map is often implemented as a balanced binary tree not a hash table. This not the case for a Python dict. So you need a C++ O(1) equivalent data structure to use your pairs with.

Answer 6

Do you want to call an optimized C++ routine via Python? If so, read on:

Often times I use PyYaml when dealing with dictionaries in Python. Perhaps you could link in something like LibYAML or yamlcpp to:

Translate a Python dictionary into a YAML string
Use Python to call a C++ function wrapped using something like SWIG, taking the YAML string as a parameter.
Use a C++ library to parse the YAML & obtain a std::map object
Operate on std::map object

Warning: I have never tried this, but using everyone s favorite search engine on "yaml std::map" yields lots of interesting links

Answer 7

As a direct answer to your question (for the python part look at my other answer). You can forget the tuple part if you want. You can use any mapping type key/value (hash, etc.) in C++, you just have to find a unique key function. In some cases that can be easy. For instance if you two integers are integers between 1 and 65536 you just could use a 32 bits integer with each 16 bits part one of the keys. A simple shift and an or or + to combine the two values would do the trick and it s very efficient.

友情链接