Thanks for all the suggestions... but I think I really do want an API like a Vec where there are no keys and where items themselves are not ordered. Instead the structure should define the order, not the items. I'll update this post with a better description of my uses cases soon.
Use Case 1
I have a large file tree and I want to maintain a list of DirEntry from that tree that match a given query. I want this list of matches ordered according to a depth first traversal of the file tree.
If this is my file tree:
And my query is for "*" ... then my matches list will look like this:
Over time the tree will change and post events (file changed, file inserted, file removed, etc). The code that maintains the matches list will re-run the query and needs to update the matches list. Updating the list is one of the tricky parts... because I need to figure out proper location to insert new matches... I need to be able to quickly compare depth first ordering of any two items in the file tree.
One way to do this is to maintain an ordered list (the data structure that I want) of the depth first traversal of the file tree. I keep this list updated as the tree changes and can use it to quickly compare the depth first ordering of any two items in the tree.
Use Case 2
I also want to fire events when my list of matches changes. So lets say file "b*" is changed to "b". It then gets removed from the list of matches since it no longer has a "". I wan to communicate that change through an event that says (removed item at index 1). But with a big list it's expensive to determine that "b" was located at index one...
So again for the matches list I'll also use this same ordered list data structure, so that I can efficiently update the list of matches, and post events with the indexes of items that have changed, inserted, or been removed.