33

Okay, so this is a little hard to explain, but here goes:

I have a dictionary, which I'm adding content to. The content is a hashed username (key) with an IP address (value). I was putting the hashes into an order by running them against base 16, and then using Collection.orderedDict. So, the dictionary looked a little like this:

d = {'1234': '8.8.8.8', '2345':'0.0.0.0', '3213':'4.4.4.4', '4523':'1.1.1.1', '7654':'1.3.3.7', '9999':'127.0.0.1'}

What I needed was a mechanism that would allow me to pick one of those keys, and get the key/value item one higher and one lower. So, for example, If I were to pick 2345, the code would return the key:value combinations '1234:8.8.8.8' and '3213:4.4.4.4'

So, something like:

for i in d:
  while i < len(d)
   if i == '2345':
     print i.nextItem
     print i.previousItem
     break()
16
  • 10
    Dicts are not ordered. There is no next or previous item.
    – Aran-Fey
    Commented Jan 19, 2015 at 23:44
  • 1
    I have mine ordered using 'collections.orderedDict'. If There isn't a way of doing this in a dict, can I take the keys out, and put them into a list (or tuple, or whatever), and then search for the next and previous item, and then use that to re-query the dictionary for their values?
    – Brewer
    Commented Jan 19, 2015 at 23:49
  • 1
    collections.OrderedDict objects have a list of 2-tuples internally. If you iterate through them using .items() you should get them in the order they are added. Commented Jan 19, 2015 at 23:51
  • 9
    If you're using an OrderedDict, you should definitely mention that, in the question itself.
    – jonrsharpe
    Commented Jan 19, 2015 at 23:51
  • 1
    @jamylak OP was already using a for to iterate through the keys, might as well iterate through that using items(). As you noted, question is misleading and unclear hence I just left a comment to hopefully guide him to figure something out. Commented Jan 20, 2015 at 2:25

11 Answers 11

12

Edit: OP now states that they are using OrderedDicts but the use case still requires this sort of approach.

Since dicts are not ordered you cannot directly do this. From your example, you are trying to reference the item like you would use a linked list.

A quick solution would be instead to extract the keys and sort them then iterate over that list:

keyList=sorted(d.keys())
for i,v in enumerate(keyList):
    if v=='eeee':
        print d[keyList[i+1]]
        print d[keyList[i-1]]

The keyList holds the order of your items and you have to go back to it to find out what the next/previous key is to get the next/previous value. You also have to check for i+1 being greater than the list length and i-1 being less than 0.

You can use an OrderedDict similarly but I believe that you still have to do the above with a separate list as OrderedDict doesn't have next/prev methods.

8

As seen in the OrderedDict source code, if you have a key and you want to find the next and prev in O(1) here's how you do that.

>>> from collections import OrderedDict
>>> d = OrderedDict([('aaaa', 'a',), ('bbbb', 'b'), ('cccc', 'c'), ('dddd', 'd'), ('eeee', 'e'), ('ffff', 'f')])
>>> i = 'eeee'
>>> link_prev, link_next, key = d._OrderedDict__map['eeee']
>>> print 'nextKey: ', link_next[2], 'prevKey: ', link_prev[2]
nextKey:  ffff prevKey:  dddd

This will give you next and prev by insertion order. If you add items in random order then just keep track of your items in sorted order.

4
  • 8
    That's not good practice - __map is a private attribute and is not guaranteed to exist or continue to function the same way in different versions or different platforms.
    – Adam Kerz
    Commented Jan 20, 2015 at 4:17
  • 1
    @AdamKerz It's the only way to access the OrderedDict linked list if you need it for whatever purpose, it doesn't matter, you need this if you want to find the next and prev in O(1). Keep in mind I answered the actual question, and the title was misleading for the actual problem OP is having
    – jamylak
    Commented Jan 20, 2015 at 10:43
  • 1
    I never said that it doesn't work, or that there's another way to access OrderedDict's linked list, just that it's not good practice. The OP never mentioned O(1) complexity, and yet my solution is also generally O(1) complexity (assuming dict lookup is O(1) or close as it is in normal cases).
    – Adam Kerz
    Commented Jan 21, 2015 at 4:15
  • @AdamKerz Yes I agree it is bad practise if the logic of the program can be redesigned this should not be needed. Your solution is never O(1) because you sort the keys.
    – jamylak
    Commented Mar 12, 2020 at 3:28
3

You could also use the list.index() method.

This function is more generic (you can check positions +n and -n), it will catch attempts at searching a key that's not in the dict, and it will also return None if there's nothing before of after the key:

def keyshift(dictionary, key, diff):
    if key in dictionary:
        token = object()
        keys = [token]*(diff*-1) + sorted(dictionary) + [token]*diff
        newkey = keys[keys.index(key)+diff]
        if newkey is token:
            print None
        else:
            print {newkey: dictionary[newkey]}
    else:
        print 'Key not found'


keyshift(d, 'bbbb', -1)
keyshift(d, 'eeee', +1)
1
  • This one is good as well, i think the usage should be considered, if the access to prev/next element will happen very often or how often the inserts to the dictionary will happen. Commented Jan 20, 2015 at 0:43
3

Another way that seems simple and straight forward: this function returns the key which is offset positions away from k

def get_shifted_key(d:dict, k:str, offset:int) -> str:
    l = list(d.keys())
    if k in l:
        i = l.index(k) + offset
        if 0 <= i < len(l):
            return l[i]
    return None    
2

Try:

pos = 0
d = {'aaaa': 'a', 'bbbb':'b', 'cccc':'c', 'dddd':'d', 'eeee':'e', 'ffff':'f'}

for i in d:
    pos+=1
    if i == 'eeee':
        listForm = list(d.values())
        print(listForm[pos-1])
        print(listForm[pos+1])

As in @AdamKerz's answer enumerate seems pythonic, but if you are a beginner this code might help you understand it in an easy way.

And I think its faster + smaller compared to sorting followed by building list & then enumerating

1
  • Note this only works if you actually use an OrderedDict... :-) And you are also creating a list there: list(d.values()). And possibly multiple lists if the conditional matches more than one key (no, it won't in this example). Note that sorted does build a list (but that is necessary if you are interested in alphabetical order rather than insert order (as was the original request)). And finally, enumerate returns an iterator so that is basically the same in terms of efficiency as what you are doing and less verbose.
    – Adam Kerz
    Commented Jan 20, 2015 at 4:28
2

You could use a generic function, based on iterators, to get a moving window (taken from this question):

import itertools

def window(iterable, n=3):
    it = iter(iterable)
    result = tuple(itertools.islice(it, n))
    if len(result) == n:
        yield result
    for element in it:
        result = result[1:] + (element,)
        yield result

l = range(8)
for i in window(l, 3):
    print i

Using the above function with OrderedDict.items() will give you three (key, value) pairs, in order:

d = collections.OrderedDict(...)

for p_item, item, n_item in window(d.items()):
    p_key, p_value = p_item
    key, value = item
    # Or, if you don't care about the next value:
    n_key, _ = n_item

Of course using this function the first and last values will never be in the middle position (although this should not be difficult to do with some adaptation).

I think the biggest advantage is that it does not require table lookups in the previous and next keys, and also that it is generic and works with any iterable.

2

Maybe it is an overkill, but you can keep Track of the Keys inserted with a Helper Class and according to that list, you can retrieve the Key for Previous or Next. Just don't forget to check for border conditions, if the objects is already first or last element. This way, you will not need to always resort the ordered list or search for the element.

from collections import OrderedDict

class Helper(object):
    """Helper Class for Keeping track of Insert Order"""
    def __init__(self, arg):
        super(Helper, self).__init__()

    dictContainer = dict()
    ordering = list()

    @staticmethod
    def addItem(dictItem):
        for key,value in dictItem.iteritems():
            print key,value
            Helper.ordering.append(key)
            Helper.dictContainer[key] = value

    @staticmethod
    def getPrevious(key):
        index = (Helper.ordering.index(key)-1)
        return Helper.dictContainer[Helper.ordering[index]]


#Your unordered dictionary
d = {'aaaa': 'a', 'bbbb':'b', 'cccc':'c', 'dddd':'d', 'eeee':'e', 'ffff':'f'}

#Create Order over keys
ordered = OrderedDict(sorted(d.items(), key=lambda t: t[0]))

#Push your ordered list to your Helper class
Helper.addItem(ordered)


#Get Previous of    
print Helper.getPrevious('eeee')
>>> d
1

You can store the keys and values in temp variable in prior, and can access previous and next key,value pair using index.

It is pretty dynamic, will work for any key you query. Please check this code :

d = {'1234': '8.8.8.8', '2345':'0.0.0.0', '3213':'4.4.4.4', '4523':'1.1.1.1', '7654':'1.3.3.7', '9999':'127.0.0.1'}
ch = raw_input('Pleasure Enter your choice : ')
keys = d.keys()
values = d.values()
#print keys, values
for k,v in d.iteritems():
    if k == ch:
        ind = d.keys().index(k)
        print keys[ind-1], ':',values[ind-1]
        print keys[ind+1], ':',values[ind+1]
0

I think this is a nice Pythonic way of resolving your problem using a lambda and list comprehension, although it may not be optimal in execution time:

import collections

x = collections.OrderedDict([('a','v1'),('b','v2'),('c','v3'),('d','v4')])

previousItem = lambda currentKey, thisOrderedDict : [
    list( thisOrderedDict.items() )[ z - 1 ] if (z != 0) else None
    for z in range( len( thisOrderedDict.items() ) )
    if (list( thisOrderedDict.keys() )[ z ] == currentKey) ][ 0 ]

nextItem = lambda currentKey, thisOrderedDict : [
    list( thisOrderedDict.items() )[ z + 1 ] if (z != (len( thisOrderedDict.items() ) - 1)) else None
    for z in range( len( thisOrderedDict.items() ) )
    if (list( thisOrderedDict.keys() )[ z ] == currentKey) ][ 0 ]

assert previousItem('c', x) == ('b', 'v2')
assert nextItem('c', x) == ('d', 'v4')
assert previousItem('a', x) is None
assert nextItem('d',x) is None
0

i know how to get next key:value of a particular key in a dictionary:

flag = 0
for k, v in dic.items():
    if flag == 0:
        code...
        flag += 1
        continue
    code...{next key and value in for}
1
  • Welcome to stackoverflow! Unfortunately, it's not so clear to me what your answer adds to the existing accepted answer. Moreover, your code does not run. It would be helpful to have full working code to understand what you're suggesting here, and perhaps also explain why your solution might be better than some of the other solutions posted. This might be helpful too: stackoverflow.com/help/how-to-answer Good luck! Commented Jun 27, 2021 at 8:02
0

if correct :

d = { "a": 1, "b":2, "c":3 }
l = list( d.keys() )  # make a list of the keys
k = "b"               # the actual key
i = l.index( k )      # get index of the actual key

for the next :

i = i+1 if i+1 < len( l ) else 0        # select next index or restart 0
n = l [ i ]
d [ n ]

for the previous :

i = i-1 if i-1 >= 0 else len( l ) -1    # select previous index or go end
p = l [ i ]
d [ p ]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.