James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 136 , comments - 1076 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in Seattle, WA. I've been doing C++/C#/Java development for over 18 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

MCC Logo MVP Logo

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

C#/.NET Little Wonders–The List<T> Range Methods

Once again, in this series of posts I look at the parts of the .NET Framework that may seem trivial, but can help improve your code by making it easier to write and maintain. The index of all my past little wonders posts can be found here.

LINQ has added so many goodies that can be used to query IEnumerable<T> sequences that it can be easy to lose sight of some of the methods that are unique to each of the collection classes. This week, we will look at the range series of methods in the List<T> collection, which are useful for getting, adding, inserting, and deleting ranges to/from a List<T>.

AddRange() – Appends a sequence to end

Sometimes, you may have a list of items and need to append another sequence of items to the end of a List<T>. The AddRange() method can be used for this very purpose:

  • AddRange(IEnumerable<T> sequence)
    • Adds the elements of the sequence of type T to the end of the List<T>.

The elements of the sequence are added to the end of the existing list. If the list is empty, the elements from the sequence will be the only thing in the list. If the sequence itself is empty, the list will be unchanged.

   1: var primes = new[] {2, 3, 5, 7, 11 };
   2: var list = new List<int>();
   3:  
   4: // list was empty, now contains 2, 3, 5, 7, 11
   5: list.AddRange(primes);
   6:  
   7: // list still contains 2, 3, 5, 7, 11 since seqeunce empty
   8: list.AddRange(Enumerable.Empty<int>());
   9:  
  10: // list now contains 2, 3, 5, 7, 11, 13, 17
  11: list.AddRange(new[] { 13, 17 });

This method can be very handy if you are looking to consolidate the results from several methods that return sequences into one List<T>, you could construct a List<T> and then use AddRange() to add each subsequent result sequence at the end of the list:

   1: var allSymbols = new List<string>(); 
   2:  
   3: foreach (var securityType in availableTypes)
   4: {        
   5:     IEnumerable<string> symbolsForType = GetSymbols(securityType);     
   6:     
   7:     // AddRange() adds sequence to end of list    
   8:     allSymbols.AddRange(symbolsForType);
   9: } 
  10:  
  11: // allSymbols now contains all of the results
  12: return allSymbols;

While AddRange() does not cause any elements of the existing List<T> to need to shift, it may cause a re-allocation if the new size of the list would exceed it’s current capacity. 

Also, we could accomplish something similar with Linq’s Enumerable.Concat() extension method, but since the LINQ extension methods tend to be query-only and not mutate the sequence, we would have to create a new List<T> containing the combined sequences and then assign it back to the original, which is not as efficient:

   1: var list = new List<int> { 2, 3, 5, 7 };
   2: var more = new[] { 9, 11 };
   3:  
   4: // This is logically identical to list.AddRange(more),
   5: // but less efficient
   6: list = list.Concat(more).ToList();

InsertRange() – Inserts a sequence of items at a given position

The InsertRange() method is very similar to AddRange(), except that InsertRange() allows you to specify an index of between 0 and the list’s Count where the sequence should be inserted. It’s format is:

  • InsertRange(int index, IEnumerable<T> sequence)
    • Inserts the sequence of type T into the List<T> at the index specified. All elements currently at the specified index and beyond will be moved after the inserted sequence.

If the index is 0, then the sequence will be inserted before everything else in the list, and if the index is equal to the list’s Count, then the new sequence will be appended to the end of the list (exactly as if AddRange() was called).

That is, the following two calls are identical:

   1: // AddRange() adds to end   
   2: someList.AddRange(aSequence);    
   3:  
   4: // same as InsertRange() with index == Count   
   5: someList.InsertRange(someList.Count, aSequence);

Thus, given various indexes, you can insert items at any valid position, moving all items at that index and beyond down to make room for the new items from the sequence:

   1: var primes = new List<int>(); 
   2:  
   3: // when list is empty, can only insert at 0 (the Count)
   4: primes.InsertRange(0, new[] { 2, 3 }); 
   5:  
   6: // inserting at position 2 in a list of size 2 appends to end
   7: // list is now 2, 3, 11, 13
   8: primes.InsertRange(2, new[] { 11, 13 }); 
   9:  
  10: // inserting again at position 2 moves the 11 and 13 down
  11: // list is now 2, 3, 5, 7, 11, 13
  12: primes.InsertRange(2, new[] { 5, 7 });

This is a good general purpose method for inserting sequences anywhere in a List<T>, though obviously if you just want to append the sequence to the end, AddRange() is more readable.

Because InsertRange() adds a sequence, possibly in the middle or beginning of the list, this can cause the rest of the elements to need to be shifted down to make room for the new sequence, which may in turn cause a reallocation to occur if the resulting size exceeds the list’s current capacity. 

RemoveRange() – Removes elements at given position

Just as AddRange() and InsertRange() can be used to add elements from a sequence into a List<T>, the RemoveRange() method can be used to remove elements from the List<T>.  The basic format of the RemoveRange() method is:

  • RemoveRange(int index, int count)
    • Removes the specified count of items from the List<T> starting at the specified index.  The index and count must specify a valid range.

Note the last part about the index and count needing to specify a valid range.  That is, you cannot specify a range beyond the bounds of the List<T>.  This means that the index can go from 0 to the list’s Count property, and the count can go from 0 to the list’s Countindex.

So, in short, if you are removing items from the list at position index, then you may remove up to but not over a count of the list’s Countindex.  For example, assume that list1, list2, list3, and list4 all contain exactly four items.  In that case, you could remove any of the following:

   1: // remove four items starting at index 0
   2: list1.RemoveRange(0, 4);
   3:  
   4: // remove three items starting at index 1
   5: list2.RemoveRange(1, 3);
   6:  
   7: // remove two items starting at index 2
   8: list3.RemoveRange(2, 2);
   9:  
  10: // remove one item starting at index 3
  11: list4.RemoveRange(3, 1); 
  12:  
  13: // remove no items starting at index 4
  14: list5.RemoveRange(4, 0);

So, this is useful for removing items from the middle of a List<T>, but be aware that this causes the remainder of the list to need to shift down to fill the gap, which can be non-trivial.  However, it will not require a reallocation of the list because the size is potentially shrinking, not growing.

GetRange() – Retrieve elements from a given position

So, we’ve seen how to manipulate a List<T> to add and remove ranges of elements, but another useful thing is to be able to get a “sub-list” of a list (much like a substring of a string).  While RemoveRange() can be used to remove a range, it doesn’t return them, it simply removes them.  If we want to query a range of elements, we need to use the GetRange():

  • GetRange(int index, int count)
    • Returns a new List<T> containing the sequence of elements designated by the range specified.  The range must be a valid range in the list.

Notice that just like RemoveRange(), the index and count specified must be valid.  So again, the index can go from 0 to the list’s Count property, and the count can go from 0 to the list’s Countindex.

The results are returned in a List<T> of the appropriate length.  Even if you ask for a range of zero elements, you will just get back an empty List<T>, not a null.

   1: var list = new List<int> { 2, 3, 5, 7, 9 };
   2:  
   3: // range1 contains 2, 3, 5, 7, 9
   4: var range1 = list.GetRange(0, 5);
   5:  
   6: // range2 contains 7, 9
   7: var range2 = list.GetRange(3, 2);
   8:  
   9: // range3 contains nothing
  10: var range3 = list.GetRange(5, 0);

Since GetRange() doesn’t modify the original list, there are no concerns about reallocating or shifting items and it performs very well.  We could also accomplish this with LINQ’s Enumerable.Skip() and Enumerable.Take() of course, though it wouldn’t be quite as efficient:

   1: var list = new List<int> { 2, 3, 5, 7, 9 };
   2:  
   3: // Roughly equivalent to list.GetRange(2, 3)
   4: var subList = list.Skip(2).Take(3).ToList();

So GetRange() is very handy for creating a sub-list of a List<T>, which can be useful for partitioning work and other such tasks.

Summary

While LINQ gives a lot of power to query IEnumerable<T> sequences in general, many of the collections themselves have specialized methods that allow manipulation and efficient queries.  In particular, the List<T> class contains four methods to query and manipulate ranges of items: AddRange(), InsertRange(), RemoveRange(), and GetRange().

 

Technorati Tags: , , , , , , , , ,

Print | posted on Thursday, February 23, 2012 6:01 PM | Filed Under [ My Blog C# Software .NET Little Wonders ]

Feedback

Gravatar

# re: C#/.NET Little Wonders–The List<T> Range Methods

Nice refresher. Thanks!
2/28/2012 1:41 PM | Dave
Gravatar

# re: C#/.NET Little Wonders–The List<T> Range Methods

When I was a student at the university, I learnt this program. It's so useful for class structure. Very complex problems can be solved by this program.
Thanks for this good post.
2/28/2012 2:16 PM | bayrak
Gravatar

# re: C#/.NET Little Wonders–The List<T> Range Methods

Can you explain why list reallocation is such a bad thing?
As long as your list is made of reference types, the list internal array does not contain the actual data but only references to the objects.
So the objects don't move in memory and the reallocating of the array should not be a big performance penalty (unless you're dealing with 100 000+ objects)
Same thing if your list is made of basic value types (except structs).
3/5/2012 3:35 AM | Wizou
Gravatar

# re: C#/.NET Little Wonders–The List<T> Range Methods

Its not a bad thing per se, its just a performance item to be aware of.

That's one of the reasons List<T> has a constructor that lets you specify your expected capacity, so you can pre size the List buffer and avoid the cost of a resize.
3/5/2012 6:44 AM | james michael hare
Gravatar

# re: C#/.NET Little Wonders–The List<T> Range Methods

Good post. Thank you very much for this share.
7/24/2012 8:15 PM | canadian provincial flags
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 
 

Powered by: