Time-stamped, thread-safe data structure for time-based lookup?

Question

I want to implement a list type data structure that can be appended to, with an associated time-stamp. The point of this is that I can then get all the data that is newer than a certain time-stamp.

I have tried doing this with a ConcurrantDicitionary but I'm not confident this is the best way to do it. I would much prefer to have a List< decimal[2] > for applications which I won't go into here. The first value of the array can have the timestamp and the second will be the value. Alternatively, could use List< TimeStampedObject >. However, apparently there is no such thing as a concurrent list in C#.

For the record, my data is ordered with regards to timestamp.

I want to be able to do things like:

public static Dictionary<DateTime, decimal> GetLatest(DateTime since, Dictionary<DateTime, decimal> requestedDict)
{
    Dictionary<DateTime, decimal> returnList = new Dictionary<DateTime, decimal>();
    returnList = requestedDict.Where(x => x.Key > since).ToDictionary(x => x.Key, x => x.Value);
    return returnList;
}

• UPDATE:

Here is the List item I have come up with; please let me know if this has any potential downfalls:

public class ConcurrentList: List<StampedValue>
    {

        ReaderWriterLockSlim _samplesLock = new ReaderWriterLockSlim();

        public ConcurrentList() : base()
        {
        }

        public void AddThreadSafe(StampedValue item){

            this._samplesLock.EnterWriteLock();
            try
            {
                this.Add(item);

            }
            finally
            {
                this._samplesLock.ExitWriteLock();
            }

        }

        public List<StampedValue> GetLatest(long since){
            return this.Where( s => s.Timestamp > since ).ToList();
        }

        public List<StampedValue> GetLatest(DateTime since){
            throw new NotImplementedException();
        }
    }


    public class StampedValue
    {
        public long Timestamp { get; set; }
        public decimal Value { get; set; }

        public StampedValue(long t, decimal v){
            this.Timestamp = t;
            this.Value = v;
        }

    }

Answer 1

Seems to me your best bet is just a List<T> that you protect with a ReaderWriterLockSlim. For example:

class Sample
{
    public DateTime EventTime { get; set; }
    public decimal Value { get; set; }
}

List<Sample> _samples = new List<Sample>();

ReaderWriterLockSlim _samplesLock = new ReaderWriterLockSlim();

// to get items after a particular date
List<Sample> GetSamplesAfterDate(DateTime dt)
{
    _samplesLock.EnterReadLock();
    try
    {
        return _samples.Where(s => s.EventTime >= dt).ToList();
    }
    finally
    {
        _samplesLock.ExitReadLock();
    }
}

If your list is known to be in chronological order, then you can improve the performance by using binary search on the list to find the first item that's greater than or equal to your passed time stamp. I just used the LINQ version here because the point is to illustrate the locking.

Appending to the list is similar: acquire the write lock, append, and release the lock:

void AppendSample(Sample s)
{
    _samplesLock.EnterWriteLock();
    try
    {
        _samples.Add(s);
    }
    finally
    {
        _samplesLock.ExitWriteLock();
    }
}

An alternative is to use List<KeyValuePair<DateTime, decimal>> rather than List<Sample>. The locking would remain the same.

This should perform quite well in most situations.

Answer 2

Have you looked at the SynchronizedCollection<T> class? It seems to me to be what you are looking for. You could also specialize SynchronizedKeyedCollection<K, T>

EDIT (2014/May/8):

The documentation I linked to above is not as clear or useful as one would like, as such it may be helpful to look at the reference implementation.