1

I'm looking for ideas to implement a templatized sequence container data structure which can beat the performance of std::vector in as many features as possible and potentially perform much faster. It should support the following:

  • Finding the minimum element (and returning it's index)
  • Insertion at any index
  • Removal at any index
  • Accessing and updating any element by index (via operator[])

What would be some good ways to implement such a structure in C++?

17andLearning
  • 477
  • 1
  • 8
  • 19
  • 1
    If it were possible to create a magic data structure that did everything the best, wouldn't we already be using it? – Neil Kirk Apr 12 '15 at 01:43
  • 2
    Wrap a vector and a priority queue in a single data structure, and expose the member functions that you need.Operations that change the vector will have to update the queue as well. – Sergey Kalinichenko Apr 12 '15 at 01:44
  • A 'magic data structure' isn't required. What is required is an implementation that can perform just these operations faster than the implementation in the std::vector library. – 17andLearning Apr 12 '15 at 01:45
  • You can't have both superior access by index and superior insertion/removal at index than vector at the same time. It's impossible. Assuming the implementation of vector is suitably optimized. – Neil Kirk Apr 12 '15 at 01:48
  • Is it possible to create something that would beat the performance of a vector in as many features as possible, then? The first thing that came to my mind was using a circular queue with a stack to maintain the minimum element. – 17andLearning Apr 12 '15 at 01:53
  • 1
    I believe the fastest data structure is the array. It appears that you might want to use a list, but std::list is probably one of the slower data structures in a library. A map might also do good but I don't have experience with maps all that much. – CinchBlue Apr 12 '15 at 01:56
  • You should state your actual requirements, which appear to be keeping track of the minimum element. In that case I would use an embedded vector or array, and a pointer to the current lowest element. Upon any modifications etc, update the pointer if necessary. – Neil Kirk Apr 12 '15 at 01:59
  • Purely algorithmically, you could perhaps achieve the stated goals with a linked list as the primary data structure, a vector of list iterators for the fast lookup, and another vector of iterators in heap or BST order to find the minimal element. It wouldn't necessarily have better performance than a simple vector on your real use case, though. – Kerrek SB Apr 12 '15 at 01:59
  • It's also possible, if the data you are storing is small, that simply looking up the minimum element each time is fast enough. This might be premature optimization! – Neil Kirk Apr 12 '15 at 02:00
  • For the required features, `std::list`'s performance is worse than `std::vector`, so I can't use that. The data stored will not be uniform each time, so I don't think looking up the minimum element each time would be feasible. If I maintain a pointer to the current minimum, finding the new minimum each time the current minimum is deleted would be expensive as well. – 17andLearning Apr 12 '15 at 02:02

1 Answers1

2

You generally be pretty sure that the STL implementations of all containers tend to be very good at the range of tasks they were designed for. That is to say, you're unlikely to be able to build a container that is as robust as std::vector and quicker for all applications. However, generally speaking, it is almost always possible to beat a generic tool when optimizing for a specific application.

First, let's think about what a vector actually is. You can think of it as a pointer to a c-style array, except that its elements are stored on the heap. Unlike a c array, it also provides a bunch of methods that make it a little bit more convenient to manipulate. But like a c-array, all of it's data is stored contiguously in memory, so lookups are extremely cheap, but changing its size may require the entire array to be shifted elsewhere in memory to make room for the new elements.

Here are some ideas for how you could do each of the things you're asking for better than a vanilla std::vector:

  1. Finding the minimum element: Search is typically O(N) for many containers, and certainly for a vector (because you need to iterate through all elements to find the lowest). You can make it O(1), or very close to free, by simply keeping the smallest element at all times, and only updating it when the container is changed.
  2. Insertion at any index: If your elements are small and there are not many, I wouldn't bother tinkering here, just do what the vector does and keep elements contiguously next to each other to keep lookups quick. If you have large elements, store pointers to the elements instead of the elements themselves (boost's stable vector will do this for you). Keep in mind that this make lookup more expensive, because you now need to dereference the pointer, so whether you want to do this will depend on your application. If you know the number of elements you are going to insert, std::vector provides the reserve method which preallocates some memory for you, but what it doesn't do is allow you to decide how the size of the allocated memory grows. So if your application warrants lots of push_back operations without enough information to intelligently call reserve, you might be able to beat the standard std::vector implementation by tailoring the growth function of your container to your particular needs. Another option is using a linked list (e.g. std::list), which will beat an std::vector in insertions for larger containers. However, the cost here is that lookup (see 4.) will now become vastly slower (O(N) instead of O(1) for vectors), so you're unlikely to want to go down this path unless you plan to do more insertions/erasures than lookups.
  3. Removal at any index: Similar considerations as for 2.
  4. Accessing and updating any element by index (via operator[]): The only way you can beat std::vector in this regard is by making sure your data is in the cache when you try to access it. This is because lookup for a vector is essentially an array lookup, which is really just some pointer arithmetic and a pointer dereference. If you don't access your vector often you might be able to squeeze out a few clock cycles by using a custom allocator (see boost pools) and placing your pool close to the stack pointer.

I stopped writing mainly because there are dozens of ways in which you could approach this problem.

At the end of the day, this is probably more of an exercise in teaching you that the implementation of std::vector is likely to be extremely efficient for most compilers. All of these suggestions are essentially micro-optimizations (which are the root of all evil), so please don't blindly apply these in important code, as they're highly likely to end up costing you a lot of time and headache.

However, that's not to say you shouldn't tinker and learn for yourself, so by all means go ahead and try to beat it for your application and let us know how you go! Good luck :)

Community
  • 1
  • 1
quant
  • 21,507
  • 32
  • 115
  • 211
  • How would you maintain the minimum element when an operation deletes that element? Wouldn't you still need to search for it in the worst case? – Jordi Vermeulen Apr 12 '15 at 09:14
  • @JordiVermeulen the minimum value would be unaffected in element deletion unless you happen to delete the smallest element, in which case you would trigger a new search. Deletion complexity is therefore amortised O(1). – quant Apr 12 '15 at 11:05
  • That is *not* how amortised complexity works. Amortised complexity is the worst case average over any string of operations. If you repeatedly remove the smallest element, every single operation would be O(n). If the probability of this happening is small (say you only delete random elements), one might say it is expected O(1), but not amortised O(1). – Jordi Vermeulen Apr 12 '15 at 11:26
  • @JordiVermeulen [Amortised Analysis](http://en.m.wikipedia.org/wiki/Amortized_analysis): *Unlike other analyses that focus on an algorithm's run time in a worst case scenario, known as asymptotic analysis, amortized analysis examines how an algorithm will perform in practice or on average.* – quant Apr 12 '15 at 23:39
  • Wikipedia has a very poor description of amortised analysis in its introduction. The "method" section does a better job. From Introduction to Algorithms: "In an amortized analysis, we average the time required to perform a sequence of data-structure operations over all the operations performed. With amortized analysis, we can show that the average cost of an operation is small, if we average over a sequence of operations, even though a single operation within the sequence might be expensive. (...) amortized analysis guarantees the *average performance of each operation in the worst case*." – Jordi Vermeulen Apr 13 '15 at 11:46
  • @JordiVermeulen you're right. It looks like I've had it backwards all this time! Thanks. – quant Apr 13 '15 at 22:04