Click here to Skip to main content
5,787,682 members and growing! (20,790 online)
Email Password   helpLost your password?
General Programming » Algorithms & Recipes » Data Structures     Beginner License: The Code Project Open License (CPOL)

Fixed Index Array

By mpustovoyt

'FixIndexArray' provides direct access like a List, and has a fixed index position like a Dictionary.
C#, Windows (Win2K, WinXP, Win2003, Vista, Windows), Architect, Dev, Design

Posted: 18 Nov 2008
Updated: 18 Nov 2008
Views: 2,237
Bookmarked: 14 times
Announcements
Loading...



Search    
Advanced Search
Sitemap
8 votes for this Article.
Popularity: 2.94 Rating: 3.25 out of 5
1 vote, 12.5%
1
1 vote, 12.5%
2
1 vote, 12.5%
3
2 votes, 25.0%
4
3 votes, 37.5%
5

Introduction

The idea about the FixIndexArray class came to me when I was looking for an array structure which will allow:

  • To have direct access to an item by index, like a List<T>.
  • To guarantee the same index during deleting an item, like a Dictionary<int,T> (analogue of a DB primary key).
  • To have higher performance of deleting/adding an item than a Dictionary<int,T>.

As a result, Ideveloped the class FixIndexArray. The final performance result shown on the picture below proves that it meets all the above requirements.

1c.JPG

Using the code

Using the class cFixIndexArr is very straightforward, and API is very similar to List<T>.

//
// This code demonstrates how to use Enumerator  
//
private void PrintArr(cFixIndexArr<int> arr) {
    Console.Write("Array : "); 
    foreach(int val in arr) {
        Console.Write(string.Format("{0}, ", val));
    }
}
//
// This code demonstrates the most common use cases  
// 
[Test]
public void UseCase() {
    Console.WriteLine(
      "Create the FixIndexArr of integers with default capacity 10"
    );  
    cFixIndexArr<int> arr = new cFixIndexArr<int>(10);
    Console.WriteLine("Load array: {0,10,20,...90}");
    for(int i=0; i<10; i++) {
        arr.Add(i*10); 
    }
    this.PrintArr(arr);
    Console.WriteLine("\r\n\r\nDelete elements 1, 3, 5, 7, 9"); 
    arr.Remove(1); 
    arr.Remove(3); 
    arr.Remove(5);
    arr.Remove(7);
    arr.Remove(9);
    this.PrintArr(arr);
    Console.WriteLine(
       "\r\n\r\nAdd element '11', '22', '33', '44', '55', '66','77'"
    );
    arr.Add(11);
    arr.Add(22);
    int index33 = arr.Add(33);
    arr.Add(44);
    arr.Add(55);
    arr.Add(66);
    arr.Add(77);
    this.PrintArr(arr);
    Console.WriteLine("\r\n\r\nReplacing element 33 by 3333");
    arr[index33] = 3333;
    this.PrintArr(arr);
    Console.WriteLine(
       "\r\n\r\nDelete element 3333 and use it for element 4444"
    );
    arr.Remove(index33);
    arr[index33] = 4444;
    this.PrintArr(arr);
}

This code produces the following result:

2c.JPG

How does it work?

The idea behind is simple: The class FixIndexArr<T> uses an array valArr of type List<T> for elements itself, and a helper array deletedIndexArr of type List<cItem> for tracking the deleted indexes. The structure cItem is a helper, and contains information about deleted indices in a double linked list manner:

3c.JPG

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

mpustovoyt


Developer Pascal, c, c++, VB, Java, C#
Occupation: Software Developer (Senior)
Company: SSI
Location: United States United States

Article Top
Sign Up to vote for this article
You must Sign In to use this message board.
FAQ FAQ Noise ToleranceSearch Search Messages 
 Layout  Per page   
 Msgs 1 to 2 of 2 (Total in Forum: 2) (Refresh)FirstPrevNext
GeneralHave you tried KeyedCollection<k,>?memberPaul B.4:44 25 Nov '08  
GeneralRe: Have you tried KeyedCollection<k,>?membermpustovoyt16:29 25 Nov '08  

General General    News News    Question Question    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

PermaLink | Privacy | Terms of Use
Last Updated: 18 Nov 2008
Editor: Smitha Vijayan
Copyright 2008 by mpustovoyt
Everything else Copyright © CodeProject, 1999-2009
Web10 | Advertise on the Code Project