0

I am looking for python equivalent to these data structure in C++

map<string,set<string>>
  1. sorted by key
  2. the value to be a set

and

map<key,val>
  1. sorted by key

After reading this: https://docs.python.org/2/library/collections.html#collections.OrderedDict I still didn't find anything suitable.

Noa Yehezkel
  • 468
  • 2
  • 4
  • 20
  • Please elaborate on what exactly you mean by "sorted by key". – timgeb Nov 11 '17 at 08:22
  • I used defaultdict for the dictionary of sets: https://docs.python.org/3/library/collections.html#defaultdict-objects the extracing in Olog(n) *easily* remained a puzzle for me. The solution I have now: sort the dictionary, do a binary search yourself... – Noa Yehezkel Nov 12 '17 at 08:35

2 Answers2

0

In python do you have 4 data structures: lists, tuples, sets and dicts. You can create your own structure combining them:

First:

data = {'my_set':set()}

Second:

data = {'key': 'value'}

And you can sort this data structures using the collections module. How can I sort a dictionary by key?

Gui
  • 763
  • 1
  • 7
  • 20
  • "And you can sort this data structures using the collections module." What do you mean, exactly? – timgeb Nov 11 '17 at 08:20
  • This structures are not ordered by default, are hashable data structures, if you want that the information to be ordered you will need to use OrderedDict like Masque said in the another answer. – Gui Nov 11 '17 at 08:25
  • like @timgeb said ordereddict orders by the order we inserted the elements.... The point for me of having a sorted dictionary is that I could search in Olog(n) If I sort the data structure each time it only hurts my performance. – Noa Yehezkel Nov 11 '17 at 13:40
-1

There is no perfect mapping between c++ and python; python is dynamically typed.

map<string,set<string>> is equivalent to (using OrderedDict to preserve the order of the keys, otherwise, dict suffice.): OrderedDict(), where the keys are strings, and the values are sets in which you insert strings

from collections import OrderedDict  
a = OrderedDict()

a['my_key'] = set()
a['my_key'].add('my_string')

note. The OrderedDict will not be ordered "by key", but by insertion order of the keys (thanks to @timgeb in the comments)

Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
  • 2
    That would have been my answer, too. Just a note. The `OrderedDict` will not be ordered "by key", but by insertion order of the keys. – timgeb Nov 11 '17 at 08:19
  • like @timgeb said ordereddict orders by the order we inserted the elements.... The point for me of having a sorted dictionary is that I could search in Olog(n) – Noa Yehezkel Nov 11 '17 at 13:39
  • You can sort the dictionary keys, using the ordering you like, before accessing the values. – Reblochon Masque Nov 11 '17 at 13:44
  • @ReblochonMasque but when pulling an element out of the dictionary: example: a['my_key'] how it would know it is sorted and to use binary search? – Noa Yehezkel Nov 11 '17 at 14:45
  • You can extract the values in a sequence following an ordering of the keys`[(k, data[k]) for k in sorted(data.keys())]` – Reblochon Masque Nov 11 '17 at 14:52
  • @NoaYehezkel The answer is that `OrderedDict` is not equivalent to `std::map` regarding element order. AFAIK, there is no equivalent in the python standard library. – juanchopanza Nov 12 '17 at 08:17