如何从 SortedDictionary 获取上一个键?

发布于 2024-10-12 20:06:02 字数 270 浏览 4 评论 0原文

我有包含键值对的字典。

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

我想从已知的键值中获取先前的键值对。在上面的例子中,如果我有密钥4,那么我怎样才能得到<2,20>

I have dictionary containing key value pairs.

SortedDictionary<int,int> dictionary=new SortedDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

I want to get previous key value pair from a known key value. In the above case, if I have key 4, then how can I get <2,20>?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(7

或十年 2024-10-19 20:06:02

使用 SortedDictionary 很难有效地实现这一点,因为它是作为不公开前驱或后继的二叉搜索树实现的。

您当然可以枚举每个 KeyValuePair,直到找到“已知”键。使用一点 LINQ,这看起来像(假设该键肯定存在并且不是第一个键):

SortedDictionary<int, int> dictionary = ...
int knownKey = ...

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                            .Last();

如果这些假设不成立,您可以这样做:(

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                                 .Cast<KeyValuePair<int, int>?>()
                                 .LastOrDefault();

检查 maybePreviousKvp != null 以确定先前的 KeyValuePair 已成功检索。)

但这根本不会有效。


如果可行,请考虑使用 SortedList< /code>相反(显然,如果您不能接受其较慢的插入和删除,这可能是不可能的)。该集合支持通过有序索引进行高效的键和值检索,因为它是作为可增长数组实现的。然后,您的查询变得非常简单:

SortedList<int, int> dictionary = ...
int knownKey = ...

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1;

// if "known" key exists and isn't the first key
if(indexOfPrevious >= 0)
{
   // Wrap these in a KeyValuePair if necessary
   int previousKey = dictionary.Keys[indexOfPrevious];
   int previousValue = dictionary.Values[indexOfPrevious];      
}

IndexOfKey 在键列表上运行二分搜索,运行时间为 O(log n)。其他一切都应该以恒定时间运行,这意味着整个操作应该以对数时间运行。


否则,您必须自己实现/找到一个确实公开前驱/后继的 BST 集合。

It's hard to implement this efficiently with a SortedDictionary<TKey, TValue> since it is implemented as a binary search tree that does not expose predecessors or successors.

You could of course just enumerate each KeyValuePair until you find the "known" key. With a little bit of LINQ, this would look like (assuming the key definitely exists and isn't the first key):

SortedDictionary<int, int> dictionary = ...
int knownKey = ...

var previousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                            .Last();

If those assumptions don't hold, you could do:

var maybePreviousKvp = dictionary.TakeWhile(kvp => kvp.Key != knownKey)
                                 .Cast<KeyValuePair<int, int>?>()
                                 .LastOrDefault();

(Check that maybePreviousKvp != null to ascertain that the previous KeyValuePair was retrieved successfully.)

But this isn't going to be efficient at all.


If feasible, consider using a SortedList<TKey, TValue> instead (obviously, this may not be possible if you can't take its slower inserts and deletes). This collection supports efficient key and value-retrieval by ordered index since it is implemented as a growable array. Then your query becomes as simple as:

SortedList<int, int> dictionary = ...
int knownKey = ...

int indexOfPrevious = dictionary.IndexOfKey(knownKey) - 1;

// if "known" key exists and isn't the first key
if(indexOfPrevious >= 0)
{
   // Wrap these in a KeyValuePair if necessary
   int previousKey = dictionary.Keys[indexOfPrevious];
   int previousValue = dictionary.Values[indexOfPrevious];      
}

IndexOfKey runs a binary search on the keys-list, running in O(log n) time. Everything else should run in constant time, meaning the entire operation should run in logarithmic time.


Otherwise, you'll have to implement yourself / find a BST collection that does expose predecessors / successors.

回首观望 2024-10-19 20:06:02

我也在寻找这个问题的答案,我认为比这里所有答案更好的解决方案是使用 TreeDictionary来自 TreeDictionarydk/research/c5/index.html" rel="noreferrer">C5 集合 (GitHub/NuGet),这是红黑树的实现。

它具有 Predecessor/TryPredecessorWeakPredessor/TryWeakPredecessor 方法(以及后继者的等效方法),它们的作用完全一样你想要什么。

例如:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

// applied to the dictionary itself, returns KeyValuePair<int,int>
var previousValue = dictionary.Predecessor(4);
Assert.Equals(previousValue.Key, 2);
Assert.Equals(previousValue.Value, 20);

// applied to the keys of the dictionary, returns key only
var previousKey = dictionary.Keys.Predecessor(4);
Assert.Equals(previousKey, 2);

// it is also possible to specify keys not in the dictionary
previousKey = dictionary.Keys.Predecessor(3);
Assert.Equals(previousKey, 2);

I was also looking for an answer to this problem, and I thought a better solution than all of the answers here is to use the TreeDictionary<K, V> from the C5 Collections (GitHub/NuGet), which is an implementation of a red-black tree.

It has Predecessor/TryPredecessor and WeakPredessor/TryWeakPredecessor methods (as well as equivalent methods for successors) which does exactly what you want.

For example:

TreeDictionary<int,int> dictionary = new TreeDictionary<int,int>();
dictionary.Add(1,33);
dictionary.Add(2,20);
dictionary.Add(4,35);

// applied to the dictionary itself, returns KeyValuePair<int,int>
var previousValue = dictionary.Predecessor(4);
Assert.Equals(previousValue.Key, 2);
Assert.Equals(previousValue.Value, 20);

// applied to the keys of the dictionary, returns key only
var previousKey = dictionary.Keys.Predecessor(4);
Assert.Equals(previousKey, 2);

// it is also possible to specify keys not in the dictionary
previousKey = dictionary.Keys.Predecessor(3);
Assert.Equals(previousKey, 2);
慢慢从新开始 2024-10-19 20:06:02
KeyValuePair<int, int> lookingForThis = dictionary
  .Reverse()
  .SkipWhile(kvp => kvp.Key != 4)
  .Skip(1)
  .FirstOrDefault();
KeyValuePair<int, int> lookingForThis = dictionary
  .Reverse()
  .SkipWhile(kvp => kvp.Key != 4)
  .Skip(1)
  .FirstOrDefault();
土豪我们做朋友吧 2024-10-19 20:06:02

我猜你可以循环遍历字典并跟踪值。像这样:

public int GetPreviousKey(int currentKey, SortedDictionary<int, int> dictionary)
{
    int previousKey = int.MinValue;
    foreach(KeyValuePair<int,int> pair in dictionary)
    {
        if(pair.Key == currentKey)
        {
            if(previousKey == int.MinValue)
            {
                throw new InvalidOperationException("There is no previous key.");
            }
            return previousKey;
        }
        else
        {
            previousKey = pair.Key;
        }
    }
}

然而,这是一个非常奇怪的操作。您需要它的事实可能表明您的设计存在问题。

You could loop through the dictionary and keep track of values, I guess. Something like this:

public int GetPreviousKey(int currentKey, SortedDictionary<int, int> dictionary)
{
    int previousKey = int.MinValue;
    foreach(KeyValuePair<int,int> pair in dictionary)
    {
        if(pair.Key == currentKey)
        {
            if(previousKey == int.MinValue)
            {
                throw new InvalidOperationException("There is no previous key.");
            }
            return previousKey;
        }
        else
        {
            previousKey = pair.Key;
        }
    }
}

However, this is a pretty odd operation to require. The fact that you need it might be pointing at a problem with your design.

束缚m 2024-10-19 20:06:02

Dictionary 未排序,因此某些项目没有先前内容。相反,您可以使用 SortedDictionary

编辑:抱歉我只看了标题哈哈。

如果您必须使用 LINQ:

int givenKey = 4;
var previousItem = dict.Where((pair, index) => 
                                   index == dict.Count || 
                                   dict.ElementAt(index + 1).Key == givenKey)
                       .FirstOrDefault();

Dictionary<TKey,TValue> is unsorted, so there is no previous thing for some item. Instead you can use SortedDictionary<TKey,TValue>.

EDIT: Sorry I read the title only LOL.

If you have to use LINQ:

int givenKey = 4;
var previousItem = dict.Where((pair, index) => 
                                   index == dict.Count || 
                                   dict.ElementAt(index + 1).Key == givenKey)
                       .FirstOrDefault();
南城追梦 2024-10-19 20:06:02

如果是这样的话,我更愿意使用 linq...尝试一下它肯定会起作用

SortedDictionary<int,int> dictionary = new SortedDictionary<int,int>();
dictionary.add(1, 33);
dictionary.add(2, 20);
dictionary.add(4, 35);

int SelectedKey = 4;

var ResutValue = ( from n in dictionary    
               where n.Key < TheSelectedKey
               select n.Value).Last();

this.txtResult.Text = ResultValue.ToString();

I would prefer to use linq if that's the case... try this it will surely work

SortedDictionary<int,int> dictionary = new SortedDictionary<int,int>();
dictionary.add(1, 33);
dictionary.add(2, 20);
dictionary.add(4, 35);

int SelectedKey = 4;

var ResutValue = ( from n in dictionary    
               where n.Key < TheSelectedKey
               select n.Value).Last();

this.txtResult.Text = ResultValue.ToString();
(り薆情海 2024-10-19 20:06:02

这个怎么样?虽然我还没有测试过它,但应该给出一些东西来开始朝这个方向思考。希望有帮助。

        int input = 4;
        List<int> lKeys = dictionary.Keys.ToList();
        int reqIndex = lKeys.IndexOf(input) - 1;
        int reqAnswer = dictionary[reqIndex];

测试其他条件,例如 if (reqIndex != -1) 等。

How about this? I havent tested it though, but should give something to start think in this direction. Hope it helps.

        int input = 4;
        List<int> lKeys = dictionary.Keys.ToList();
        int reqIndex = lKeys.IndexOf(input) - 1;
        int reqAnswer = dictionary[reqIndex];

test for other conditions like if (reqIndex != -1) etc..

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文