Need sorted dictionary designed to find values with keys less or greater than search value

Question

I need to have objects sorted by price (decimal) value for fast access. I need to be able to find all objects with price more then A or less than B. I was thinkg about SortedList, but it does not provide a way to find ascending or descending enumerator starting from given key value (say give me all objects with price less than $120).

Think of a system that accepts cars for sale from sellers and stores them into that collection. Then buyers want to find cars cheaper than $1000.

Basically what i need is tree-based collection and functionality to find node that is smaller\greater\equal to provided key.

Please advice.

As I understand, you have to store objects in memory somehow and be able to select some of them quickly. Why are you asking about this? (May be you have some details?) Such operation are so fast (cause it all in memory, instead of SQL queries) that you have to just go ahead and implement this somehow. You may encapsulate logic in some class and provide an interface. When hardtimes come (if they ever come) you have to profile and optimize you class (interface should be constant). And for the first implementation of your class Marcelo Cantos's solution is good enough. Don't be scared of LINQ:) — lak-b, Apr 23 '10 at 12:49
possible duplicate of [Efficiently find nearest dictionary key](http://stackoverflow.com/questions/12412869/efficiently-find-nearest-dictionary-key) — nawfal, Jun 11 '14 at 13:14

score 9 · Answer 1 · edited May 23 '17 at 12:25

9

You can use BinarySearch on SortedList to search first and last indexes satisfying your conditions and then just get range of items from list.

edited May 23 '17 at 12:25

Community

1
1

answered Apr 23 '10 at 12:35

Alex

2,438
23
30

Marcelo Cantos · Accepted Answer · 2010-04-23T12:15:50.737

4

The answer depends on your usage patterns. If this a one-off exercise of consuming an unsorted input set and finding suitable objects, you are much better off just using LINQ:

list.Where(e => A < e.Price || e.Price < B);

If the list is static, and you want to query multiple ranges, then stick the objects into an array, sort them by price, and then use a binary chop to find ranges of interest.

edited Apr 23 '10 at 12:15

answered Apr 23 '10 at 12:03

Marcelo Cantos

181,030
38
327
365

I don't need closed range, just less OR greater – Captain Comic Apr 23 '10 at 12:11
1

That's a fairly simple change. – Marcelo Cantos Apr 23 '10 at 12:16
3

That is indeed. I am reluctant to use LINQ due to performance issues. – Captain Comic Apr 23 '10 at 12:22
2

Don't optimise prematurely. LINQ code is quite fast enough for most uses, and can even outperform hand-written list-manipulation logic in some cases. – Marcelo Cantos Apr 23 '10 at 12:31

score 2 · Answer 3 · answered Apr 23 '10 at 13:24

Please think of a SortedList. Alternatively you can use just any collection and query it with LINQ. For example plain generic List:

        List<Int32> tempList = new List<Int32>();

        tempList.Where(singleItem => singleItem > 100)
            .ToList<Int32>();

Need sorted dictionary designed to find values with keys less or greater than search value

3 Answers3