diff --git a/mercurial/util.py b/mercurial/util.py
--- a/mercurial/util.py
+++ b/mercurial/util.py
@@ -252,6 +252,12 @@ class sortdict(dict):
     def __delitem__(self, key):
         dict.__delitem__(self, key)
         self._list.remove(key)
+    def pop(self, key, *args, **kwargs):
+        dict.pop(self, key, *args, **kwargs)
+        try:
+            self._list.remove(key)
+        except ValueError:
+            pass
     def keys(self):
         return self._list
     def iterkeys(self):