# Finding all elements between two in a list

• August 2nd, 2012, 06:22 PM
Learned
Finding all elements between two in a list
I am used to using STL in C++ and kind of dabbling with C-sharp right now. So, I have a sorted array and I want to find all elements between two given quantities.

I have the following:

key,value
11,22
13,26
15,30
17,34
19,38 ,etc.

I want to extract all elements whose key is between 12 and 16 i.e. I want to extract 26 and30 since their key 13 and 15 is between 12 and 16. In C++ I would have used STL maps to easily do this. How do Ido this in c-sharp.

Thanks
• August 3rd, 2012, 06:18 AM
S_M_A
Re: Finding all elements between two in a list
• August 3rd, 2012, 07:23 AM
Learned
Re: Finding all elements between two in a list
Thanks for reply. I think I have seen links about dictionary before. I would like not to iterate through the entire dictionary to find first key greater than 12 and first key smaller than 16. Is there no inbuilt function to do this in one shot like in STL maps?

Thanks again
• August 3rd, 2012, 07:40 AM
S_M_A
Re: Finding all elements between two in a list
I'm not using C# that much (mostly for smaller quick and dirty apps where I need a GUI) but as far as I read (well browsed...) it they said that SortedDictionary is quite similar to std::map
• August 3rd, 2012, 07:49 AM
TheGreatCthulhu
Re: Finding all elements between two in a list
Well you could use LINQ. Language Integrated Query is a set of keywords that let you query various collections, but it's just syntactic sugar for a bunch of methods.
You can also use SortedList<TKey, TValue> or SortedDictionary<TKey, TValue> if you want automatic sorting.

Quote:

Originally Posted by MSDN
The SortedDictionary<TKey, TValue> generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList<TKey, TValue> generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal:

• SortedList<TKey, TValue> uses less memory than SortedDictionary<TKey, TValue>.
• SortedDictionary<TKey, TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for SortedList<TKey, TValue>.
• If the list is populated all at once from sorted data, SortedList<TKey, TValue> is faster than SortedDictionary<TKey, TValue>.

Query syntax:
Code:

```var query = from elem in sorted             where (elem.Key >= min && elem.Key < max)             select elem.Value;```

The first line declares elem as a member of sorted (that is, the compiler infers the type), the second filters the elements, and the third projects each KeyValuePair<int, int> to elem.Value.
The var keyword just means that the compiler will infer the type for you - still strongly typed, but avoids extra work. You can replace it with IEnumerable<int>.

Equivalent method syntax:
Code:

`var query = sorted.Where((elem) => (elem.Key >= min && elem.Key < max)).Select((elem) => { return elem.Value; });`
The "strange" parameters to the methods are lambdas, which are just anonymous functions; the format is (param_list) => expression, or (param_list) => { method_body }

Notice that I named the variable query - it's because it's recommended to think of results returned by LINQ methods as queries, rather than collections; LINQ uses lazy evaluation, so the query will not be executed until you actually try to enumerate the elements later on in the code (use the foreach construct).