Chapter 12. Order of Insertion

Chapter 12. Order of Insertion

Whenever you hear the words “order of insertion” in a set of requirements, it should be associated with certain ideas. Note that this is exactly the same as First-In-First-Out (FIFO), which means that any type of queue is good at this:

• Linked list queue — std::queue container.
• Doubly-linked list queue — std::deque container.
• Array queue or dequeue — a ring buffer.

However, order-of-insertion is not necessarily a queue data structure. If the requirements include insertion or deletion in the middle of the sequence, then it’s not really a queue (nor even a dequeue).

These types of requirements that combine order-of-insertion traversal along with generalized insertions and deletions can arise in several practical contexts:

• Least-Recently-Used (LRU) cache.
• Operating system paging algorithms.
• Order book updates (trading engine).
• Rate limiting (throttling) of requests.

These all have a time element that causes them to have queue-like need for insertion-ordering. However, there needs to also be key-based searches, insertions and deletions, so a basic queue is not adequate.

Hash Table with Order-of-Insertion

As an example, let’s consider a dream list of requirements for such a data structure:

1. Fast search, insert and deletion, and

2. Traversal in order-of-insertion.

To get to the first three, with fast search, insertion, and deletion, you should immediately think: hash tables.

Hash tables have average case O(1) complexity for search, insertion and deletions. Admittedly, hash table can degrade to linear complexity in the worst case. Furthermore, hash tables have a poor traversal cost generally, and totally fail at maintaining any order in the traversal. We can’t maintain “order of insertion” with just a hash table.

Hence, to implement traversal in the insertion order we need another data structure. The first idea is to have two totally distinct containers, and search them both when we’re doing our operations. A better idea is that in our hash table nodes, we can insert a pointer to some other node in another data structure, so that we don’t need to do two lookups. Two options come to mind:

• Array or vector — contiguous data with good cache locality.
• Doubly-linked list — non-contiguous linked data structure.

Let’s look at each of these options.

Contiguous Array Version

The idea is to maintain traversal in the order of insertion by maintaining the items in a separate std::vector or std::array container. For example, you could maintain an array of pointers to the hashed nodes in the array. And each hash node would need either a pointer back to the array or an index offset of where the element is found in the array.

The use of an array or vector makes the traversal of items super-fast, by scanning the array, in contiguous memory locations. Okay, so actually the cache locality isn’t that great, since scanning the pointers in the array has good locality, but then it’s jumping via the pointers to the nodes in the hash table, which are in different places in memory.

It’s easy to maintain order-of-insertion in the array, simply by always inserting at the end. Our array or vector data structure has a count of how many elements are in the array, and we can insert a new item at the end.

Problems arise with deletion, however. If the need for deletion was only to remove an item from a fixed-size array to make room for the next one, then we could address this by using a ring buffer implemented as an array (i.e., a fixed-size queue in an array).

However, if we want to remove arbitrary items from our hash table, and hence from our array, the use of a contiguous array causes difficulties. The difficulty is not in finding the location for removal, but at the end of this sequence:

1. Search the hash table for the key.

2. Find the pointer or index into the array in the hash node.

3. Remove the node from the hash table container.

4. Remove the pointer from the array or vector container.

However, once we try to remove the entry from the array, there’s a gap. There are three possible approaches:

1. Mark the item as “deleted” (i.e., leave a gap).

2. Shuffle the array elements down.

3. Move the end array element down into the gap (“swap and pop”).

None of these solutions are great. They all lead to suboptimal complexity in one or other of the methods.

Marking each item with a “deleted” flag works fine on deletion, but the insertion-order scan has to skip extra unused elements. There are a few ways to mark the elements:

• Boolean flag inside each element.
• Separate array of Boolean flags.
• Packed bit vector representing the Boolean flags.

Furthermore, with the marking-as-deleted method, the array will fill up, and need to have its gaps removed eventually. This is a costly type of “garbage collection” or “memory reclamation” algorithm that will have linear complexity. And until it’s cleaned up, the method will waste extra memory space for all the deleted gaps.

Shuffling all of the elements down to fill the gap does maintain the correct order in the array. However, it’s an O(n) operation and will also invalidate all the pointers into the array from other non-removed elements in our hash table. So, we’d need some way of finding all those elements (e.g., reverse pointers), and also the cost of updating them all.

Finally, the “move end element down” array trick is an O(1) method to cover our gap, and would only require updating one non-removed hash node, which is also O(1). Admittedly, the need to store reverse pointers from the array back to the hash nodes adds O(n) more space. However, it fails completely, because the array is no longer sorted in order of insertion.

Is there a way to salvage the dream of maintaining a contiguous array that is sorted by insertion order? There are some tricks to try, like permutation arrays, but I can’t see a good solution.

Doubly-Linked List Version

A more natural solution is to thread a doubly-linked list through our hash nodes. The advantages of a doubly-linked list are:

1. No fixed size limits.

2. Easier deletion with O(1) complexity.

3. Maintains order-of-insertion naturally.

Note that the linked list has to be doubly-linked so that deletion is easy once we find a node to remove. If it’s only a singly-linked list, then we cannot find the element before the current node, so we can’t easily unlink the current node.

The doubly-linked list method is not without downsides. There are problems with time and space:

• Extra space for previous and next pointers in each node.
• Non-contiguous memory usage for scanning (it’s a linked list!)

To implement the interleaved doubly-linked list, each node in our hash table needs to have “next” and “previous” pointers. We also need to track the head and tail of this list at the container level.

The idea is that a scan in order of insertion is just to run down the doubly-linked list in one direction. Hence, when we insert a new item it has to be inserted at the end of the list.

The reason that this method is better than an array or vector is that it’s easy to remove in a linked data structure. There’s no “gap” when we remove an item from a linked list. We just update the pointers to the adjacent list elements to point around the removed list node.

Could we use a separate doubly-linked list, such as the std::list container, rather than manually threading pointers through our hash table? Yes, but this wouldn’t really avoid the space cost of storing “next” and “previous” pointers in each hash node, but just move them elsewhere. Additionally, we’d need a pointer to the list node in the doubly-linked list stored in the hash nodes. And each insertion would need two separate memory allocations for the hash nodes and linked list nodes. Hence, threading our doubly-linked list through the nodes themselves seems more efficient overall.

• Online: Table of Contents • PDF: Free PDF book download • Buy: Advanced C++ Memory Techniques: Efficiency and Safety

Advanced C++ Memory Techniques: Efficiency & Safety: Memory optimization techniques Memory-efficient data structures DIY memory safety techniques Intercepting memory primitives Preventive memory safety Memory reduction optimizations Get your copy from Amazon: Advanced C++ Memory Techniques