What is the best C# Data Structure(s) For the Following Situation

Question

The requirements for my application are as follows. I need to store orders which look like this:

• Each order pertains to a specific stockcode(string) and has a price, volume and whether or not it is being bought or sold(boolean) associated with it.

• I need to do several operations on all orders that pertain to a specific stock, for example get the sum of the volume of orders for stockcode "abc".

• I need to be able to add an order to the data structure

• I need to be able to remove an order from the data structure

• I need to be able to find out which order is offering the best price after an order is added or removed.

Here is what I am thinking so far:

public class Order : IComparable
{

   private string _StockCode;
   private bool _BidSide;
   private int _Volume;
   private decimal _Price;
   private int _ExchangeOrderId;

   public int CompareTo(Order other)
   {
        if (_BidSide != other.BidSide)
        {
            return _BidSide ? 1 : -1;
        }
        return decimal.Compare(_Price, other.Price);
   }
}

And then I would store the orders in a Dictionary<string, List<Order>>. Where each stock code would be a key in the dictionary pointing to a list of orders for that stock. I would also maintain Dictionary matching an order id to a stock code.

• For adding a new order, I simply find the appropriate list of orders in the dictionary based on the current stock code, and insert the order. I would also add an entry in the orderstock dictionary matching the current order with the approrpriate list.

• For finding the best price, I look up the order list in the dictionary for the current stock code, sort the list and print out the highest order.

• Removing is tricky. I would first need to look up the appropriate list by stock code. I would then need to iterate through all the orders for that stock code and find the one that matches the current order id and remove it. This is obviously inefficient if there are a lot of orders for the current stock code. Is this the best way of storing this information?

Answer 1

If you're going to do this with a lot of data, put it in a database. This is not something you want to do in a class.

However, if you are using a small set of data, you could do this in code using LINQ.

I think you should make Order implement IEnumerable and then use a List<Order> to store your orders. Make StockCode a public property on the Order and then you can retrieve orders by using Linq:

List<Order> orders = GetOrderList();

var ibmOrders = from o in orders
    where o.StockCode == "IBM"
    select o;

Removing items from the list is quite simple:

List<Order> orders = GetOrderList();

var orderToRemove = (from o in orders
  where o.ExchangeId == 1315
  select o).FirstOrDefault();

if (orderToRemove != null) {
    orders.Remove(orderToRemove);
}

Finding by best price using Linq is quite nice:

Order bestPricedOrder = (from o in orders 
        orderby Price 
        select o).FirstOrDefault(); 

For more great LINQ tricks, see 101 LINQ Samples.

Answer 2

I would add an additional dictionary, which consists of key = orderid, value = reference to order in the list in the initial dictionary of stock codes.

This will act like an index and give you constant time deletion. Assuming you Order ID is distinct it will map 1:1. Just make sure you delete it from both dictionaries.

As suggested in comments I would recommend an additional dictionary of the computed sums that you need accessible by stock code. This is trading off constant time access for memory. Unless memory is an issue this would seem favourable to calculating it every time you need it. If you get a new order in you can just update the sums, averages, etc. Just keep in mind if you are doing stuff in parallel you'll need some locking to ensure you don't have issues.