Collection modify item

Question

I have read tons of articles on choosing the correct collection for a specific implementation, and I understand that in the end it will come down to benchmarking real data, but while I'm busy doing that:

• What sorted collection in c# allows the modification of an item contained?I can't seem to find any?

• Is this because a modify would probably be implemented as a removal then re-insertion, thus making an explicit 'Modify' function pointless?

I am in need of a collection (custom or standard library), with the following operations performed on it.

• Insert - often
• Remove - often
• Modify - very often
• Select Top X elements - every time any of the above happens, and more, concurrently.

Currently I am using a SortedSet, as it provides O(logn) inserts,but I am unclear on removal performance and how to best modify an item.

Answer 1

First, we need to clarify the meaning of modifying a collection.

Generally, manipulating collection refers to insert/delete items from the list. To modify an individual item, it's basically accessing the item and modify its properties. Cost of accessing an item depends on the collection implementation, but modification of item propertis is not dependant on the collection. Also note, you cannot modify a collection item if it's not mutable.

If you are just looking to find the best built-in collections, you are basically choosing between SortedList and SortedSet (SortedDictionary is the same as SortedSet).

SortedList stores data internally as array, so it has efficient access by index (for getting top X items); SortedSet has faster insertion and removal (by constant factor), indexed access however will require searching through the tree for next item which in worst case is O(log n) and best caes O(1).

Aside from that, difference between the two is quite small, as they both implements Red Black Tree, just differs in implementation details.

Actual performance will have to be measured for your user cases. But you already know that.