Containers like vector, list, deque, stack, queue, priority_queue, map and unordered_map were implemented.
Also, some generic algorithms like sort, list_sort and make_heap were done at last.
All the code were checked with valgrind to ensure that there's no memory leak. Suggestions are welcome!
The key parts of a vector are the erase and insert operations, whose time complexity are O(n).
Attention should be paid to the so called "deep copy" operations when moving the objects inside or using the assignment operator, since objects may have pointers pointing to dynamic memory outside the vector.
To handle this, I generally calls the placement new operator to construct an new object in target address and calls the destructor to destroy the original object later.
Additionally, The iterator I design can check the validity of itself, and the time complexity is O(1). That is, given a pointer pointing to a vector, the isValid function can tell if the iterator belongs to the given vector, and if the iterator is still valid after insert or erase operations were taken, since these operations may cause the vector to allocate a larger memory block and to release the original one.
The key parts of a list are the erase and insert functions, whose time complexity are O(1). Proper construction, destruction and memory management plays a significant role in the implementation as well.
With an additional node named "last" inside each list, it's much easier to indicate the end() position, which is post to the last data node. Also, we benefit a lot from this structure when implementing other member functions.
Although the erase and insert operations on certain data node won't cause iterators pointing to other data nodes to be invalid, I implement the isValid function inside the iterator to check if the iterator belongs to the given list and if the iterator is still valid after inserting or erasing with O(n) time complexity.
Here the deque was implemented with Block List, which combines the advantages of vector and list and provides O(sqrt(n)) performance for search, insert and erase operations.
However, it's frustrating to realize that efficiency and standards are not always compatible. For example, if we want to improve the performance, we can adopt a "lazy" strategy in push and insert operations to get better amortized performance, where maintain operation is postponed until an access operation is detected. This is just like what were done in Splay or Fibonacci Heap, but things got changed when iterator was introduced. We must follow the basic semantics and requirements of iterator: if there's no insert nor erase operations, existing iterators must be valid! This is impossible if we do following operations:"auto itA=insert(pos,val); auto itB=begin();" as itA may become invalid after maintain operations were done in begin(). So, after each operations that related to iterator, we must keep the internal structure stable for next operation, which hindered us from using more advanced tactics to further optimized the performance.
Meanwhile, it's of great importance to keep something invariant when designing the program. They were helpful in handling corner cases and avoid making mistakes. The "KISS" principle should be reminded so that it won't be too complicated to figure them out. Besides, be careful to avoid low-level mistakes like wrong operating direction or wrongly used variable... sigh...
Actually, stack is an adapter instead of a container. It's based on the vector or list so that the push, pop and top can be realized easily by calling corresponding functions in specified container. Also, we needn't to worry about the memory management since it has been guaranteed before.
Since the elements inside a stack are not allowed to be accessed, we don't have to provide relevant iterator.
Similarly, queue is also an adapter instead of a container. As we need to support operations on the front, vector is not suitable any more. Thus, it was implemented with the list we created before. Operations like push, pop and front can be done easily by calling their counterparts in list.
Since the elements inside a queue are not permitted to be traversed, we needn't to provide relevant iterator.
Here I implemented the priority_queue with both binary heap and fibonacci heap. The difference is that binary heap supports all the ordinary operations except the merge operation while fibonacci heap can handle it well.
For a binary heap, when the top element get extracted, a percolateDown process will be taken to select the new front element and to re-balance the heap. Similarly, a percolateUp process will be applied after a new element was appended to the back so that it can be properly placed. Both of these two operations have logarithmic complexity, so the time cost of the pop and push operations are O(log(n)).
Theoretically, the time consumption of the pop operation for a fibonacci heap is O(log(n)) and the push operation is O(1) since fibonacci heap adopts a "lazy" strategy to store new elements. That is, it simply inserts the element into its data list when a new element comes, so the time consumption is constant. However, a consolidate process will be taken after the root node was extracted, which effectively re-ordered the heap and takes logarithmic time complexity.
Naturally, iterator is not needed for this data structure as the traversal of a heap is meaningless.
Although there're many kinds of balance tree can be applied like Binary Tree, AVL, RB, AA, Splay, Treap, Skip List and so on, we use the famous Red-Black Tree as the internal infrastructure for map. It's important to clarify why we choose RB instead of AVL, which is more balanced than RB.
As we know, the mostly used operations of a map are insert and erase. After a new node was inserted, the tree may get unbalanced, and the re-balance process will be taken. For both AVL and RB, it will take at most 2 times of rotation in the worst cases. Thus, the time complexity of the insert operation for a map is O(1).
However, when it comes to the re-balance process for an erase operation, all the nodes along the path from root to the erased node may be maintained for AVL while RB needs at most 3 times of rotation. Thus, the time complexity of the erase operation for AVL is O(log(n)) while RB is O(1). Surely, the search efficiency of AVL is much better than RB since AVL is more stable, but it's a compromise among the search, insert and erase operations in engineering practice to choose RB.
Beside the choice of internal balance tree, designs of interface with the use of template also define the quality of the program. One thing we need to handle is that the key and the value are paired while the search routine only knows the key, thus a getKey functor is needed to extract the key from the pair. Also a compare object is needed for further comparison.
When it comes to implementation, an extra node named header is set to be the parent node of the root node, and it's left and right pointer points to the min and max node in logical order so that the increment and decrement progress of an iterator will be done much easier. Further more, proper construction and destruction of the header also play a vital role in this program so that classes without default constructor can be accepted as well.
Based on hashtable, this data structure provides O(1) time complexity to access, insert and erase an element when the load factor is less than 0.5. We adopt the "separate chaining" strategy, and the hash function by default is std::hash.
It doesn't take much effort to implement the insert and erase functions, and the search function is rather trivial. But we need to resize the hashtable dynamically when it grows to keep the load factor under 1/2. Note that there's no backward-marching for the iterator, special attention should be paid to the forward-marching operation of an iterator when it reaches the margin of two buckets.
sort:
Generally, we adopt the quick sort algorithm and some optimization work were done to handle the extreme cases.
Firstly, the program use the so called introspective sort method to get a rough result. Then the insertion sort were carried out to get final result. If the operating sequence deteriorated with too much nesting, heap sort algorithm will be used to eliminate unnecessary recursive calls.
list_sort:
As we don't have to operate on internal data, I thought of the in-place merge method. Although the in-place merge method based on list is free of the heavy cost when reversing the data blocks, it suffers from the expense to traverse to the middle of the list every time when the iteration step is called.
Learning from SGI STL, we use a different style of iterative merge sort algorithm to effectively sort the elements with O(nlog(n)) time complexity and O(1) space complexity. In this way, the data nodes were merged in sequence, and the continuously merging of sub-sequence acts just like the carry-over of binary numbers when doing addition. Thus, we avoided unnecessary traversal. The testing results shows that sorting 100,000,000 elements only costs 10+ seconds!
make_heap:
Just start from the last node that is not leaf, then adjust each sub-tree until root node is adjusted, so that the property of heap is maintained. The time complexity of this algorithm is O(n) since each adjust on sub-tree takes O(h) time consumption, where h stands for the height of the heap.
Just cd to "./script" and type "python3 test-XXX.py" to run corresponding tests.
These python scripts are based on following commands:
- Compile: g++ -std=c++11 -O2 test/XXX/YYY.cc -o results/XXX/YYY.exe
- Common check: ./results/XXX/YYY.exe > ./results/XXX/YYY.txt
- Memory check: valgrind --tool=memcheck --leak-check=full ./results/XXX/YYY.exe > ./results/XXX/YYY.txt
As the testing scripts don't carry out memory checking work, you need to use valgrind manually or modify related scripts.
The framework and test cases of this project are based on the course project of DS2016, ACM Class, SJTU. I'm full of admiration for the wonderful work they've done!