Is there a Python data structure which is sortable and searchable?

Question

I'm using python to manage a queue of strings to process. It has a couple of requirments:

• Each string is matched to a priority and is processed based solely on that value.
• Strings can be added to this queue dynamically but no duplicate Strings are allowed in the queue. If a duplicate is submitted then it must be identified and ignored.

So is there any python datatype that will allow something like this? Or do I have to write my own?

If there isn't a native one then, I'm thinking of maintaining two structures.

1. A heapq which will maintain the strings and their priority
2. A list which maintains a hash of the strings to check whether the string is already stored

As long as these do not fall out of sync it should solve the problem.

Answer 1

That sounds like a reasonable approach. I would use a set instead of a list since it has more efficient membership checking and you don't need to maintain order (since you do it in the heapq)

Answer 2

An ordered dictionary may be of help.

See this page (an ordered dictionary) where it states:

The ordered dictionary keeps keys in insertion order. This is sometimes called a created order dictionary.

There are potential use cases for dictionaries that keep their keys in order, but the ordering being based on other criteria.

You are free to change the order using the setkeys method, but you may prefer a dictionary that used these different criteria. For example you might need a dictionary that kept keys in order of the last accessed key.