Maintain an ordered collection of objects

Question

I have the following requirements for a collection of objects:

• Dynamic size (theoretically unlimited, but in practice a couple of thousand should be more than enough).
• It is ordered, but allows reordering and pasting in arbitrary places.
• Allows you to delete
• Indexed Access - Random Access
• Count

The objects that I store are small, several properties, and a small array or two (256 booleans)

Are there any built-in classes that I should know about before writing a linked list?

Answer 1

Original answer: This sounds like a std::list (doubly linked list) from the standard library.

New answer: After changing the specification, std::vector can work as long as there are no more than several thousand elements in the middle of the vector, and not a huge number of inserts and exceptions. The linear complexity of inserting and deleting in the middle can be outweighed by the small constants of the vector operations. If you do a lot of attachments and deletions only at the beginning and end, std::deque can also work.

Answer 2

You have not indicated enough of your requirements to select the best container.

Dynamic size (theoretically unlimited, but in practice a couple of thousand should be more than enough)

STL containers are designed to grow as needed.

Ordered, but allows reordering and pasting in arbitrary places.

Allow reordering? It is not possible to reorder std :: map: you can delete from one std :: map and insert into another using a different order, but as different instances of the template, the two variables will have different types. std :: list has a member function sort() [thanks Blastfurnace for pointing this out], especially effective for large objects. A std :: vector can be easily used with the non-member function std::sort() , which is especially effective for tiny objects.

Effective pasting at random locations can be done on a map or list, but how do you find these locations? The search in the list is linear (you should start with what you already know and scan the element forward or backward by element). std :: map provides an efficient search, like an already sorted vector, but pasting into a vector involves moving (copying) all subsequent elements to create space: this is an expensive operation in the scheme of things.

Allows you to delete

All containers allow deletion, but you have the same performance problems as for insertion (for example, fast for a list, if you already know the location, fast for a map, deletion in vectors is slow, although you can “mark” the elements are deleted without deleting them, for example, if the string is empty, with a Boolean flag in the structure).

Indexed Access - Random Access

the vector is indexed numerically (but can be binary), display an arbitrary key (but not a numerical index). the list is not indexed and a linear search should be performed from a known element.

Count

std::list provides an O (n) size() function (so that it can provide an O (1) connection), but you can easily track the size yourself (assuming you won't merge). Other STL containers already have O (1) time for size() .

conclusions

Consider whether using std :: list will result in many inefficient linear searches for the desired item. If not, the list gives you efficient insertion and deletion. The sanctuary is good.

A map or hash map allows you to quickly find and easily insert / delete, cannot be used, but you can easily move data to another map with other sorting criteria (with moderate efficiency.

The vector allows you to quickly search and apply in place, but worse to insert / remove. It is the fastest for random access searches using the item index.

Answer 3

-Insertion and Deletion: This is possible for any STL container, but the question is how long does it take to execute it. Any container of a linked list (list, map, set) will do this in constant time, while containers (vector) like an array will do this in linear time (with distribution with constant depreciation).

-Sorting. Given that you can store a sorted collection at all times, this is not a problem, any STL container will allow this. For maps and sets, you don’t need to do anything, they already make sure that sorting is always sorted. For a vector or list, you need to do this work, i.e. You need to perform a binary search for the place where the new elements will go, and insert them there (but for the STL algorithms there are all the elements necessary for this).

-Resorting: If you need to take the current collection that you sorted by rule A and resort to the collection with respect to rule B, this can be a problem. Containers, such as map and set, are parameterized (as a type) according to the sorting rule, which means that to use it you will need to extract each element from the original collection and insert them into a new collection with a new sorting rule. However, if you use a vector container, you can simply use the STL sort function at any time to resort to any rule that you like.

-Random Access: You said you need random access. Personally, my definition of random access means that any item in the collection can be accessed (by index) in constant time. With this definition (which I think is quite standard), any implementation of linked lists is not suitable, and this leaves you with the only possibility of using a container of type type (for example, std :: vector).

Conclusion, in order to have all these properties, it would be best to use std :: vector and implement your own sorted insertion and delete sorting (doing a binary search in the vector to find the element to delete or the place to insert the new element). If your objects that you need to store are significant, and the data according to which they are sorted (name, identifier, etc.) is small, you can consider sharing the problem by holding an unsorted linked list of objects (with full information) and saving the sorted key vector along with a pointer to the corresponding node in the linked list (in this case, of course, use std :: list for the first and std :: vector for the last).

By the way, I'm not a great expert with STL containers, so I could be wrong in the above, just think about yourself. Explore STL for yourself, I'm sure you will find what you need, or at least all the parts you need. Perhaps look also at the Boost libraries.