The deadline for this project is January 7, 2022, at midnight.
Fork the repository, populate the file list_pool.hpp then push on the master branch of the fork. I will not accept any other form (e.g., you send me a tar.gz). I will check just the master branch. You can write additional tests, but your code is required to be compliant to the given ones. You can run the test suite by typing make check.
In this project, you must write a pool for fast linked lists. The pool stores each node in a std::vector<node_t>. The "address" of a node is 1+idx, where idx is the index where the node is stored in the vector. This trick allows us to use address 0 as end, so we can use unsigned integers type. The first node stored in the vector will be put at idx == 0, but it will be referenced as 1.
list_pool<int, std::size_t> pool{};
auto l = pool.new_list();
// l == pool.end() == std::size_t(0)
l = pool.push_front(42,l);
// l == std::size_t(1)The pool maintains a list of free nodes, i.e., available positions in the vector. The free_node_list is empty at the beginning.
list_pool<int, std::size_t> pool{};
auto l = pool.new_list();
l = pool.push_front(10,l); // l == std::size_t(1)
l = pool.push_front(11,l); // l == std::size_t(2) <-- later, this node will be deleted
auto l2 = pool.new_list();
l2 = pool.push_front(20,l2); // l2 == std::size_t(3)
l = pool.free(l); // that node is deleted, so it is added to free_node_list
l2 = pool.push_front(21,l2); // l2 == std::size_t(2)Here is the class template (without the noexcepts, remember to use them). The following functions must be implemented, and you don't have to change the names. Of course, you are free to implement more private and public methods. Remember to write a good class for iterators to avoid code duplication for iterator and const_iterator.
template <typename T, typename N = std::size_t>
class list_pool{
struct node_t{
T value;
N next;
};
std::vector<node_t> pool;
using list_type = N;
using value_type = T;
using size_type = typename std::vector<node_t>::size_type;
list_type free_node_list; // at the beginning, it is empty
node_t& node(list_type x) noexcept { return pool[x-1]; }
const node_t& node(list_type x) const noexcept { return pool[x-1]; }
public:
list_pool();
explicit list_pool(size_type n); // reserve n nodes in the pool
using iterator = ...;
using const_iterator = ...;
iterator begin(list_type x);
iterator end(list_type ); // this is not a typo
const_iterator begin(list_type x) const;
const_iterator end(list_type ) const;
const_iterator cbegin(list_type x) const;
const_iterator cend(list_type ) const;
list_type new_list(); // return an empty list
void reserve(size_type n); // reserve n nodes in the pool
size_type capacity() const; // the capacity of the pool
bool is_empty(list_type x) const;
list_type end() const noexcept { return list_type(0); }
T& value(list_type x);
const T& value(list_type x);
list_type& next(list_type x);
const list_type& next(list_type x) const;
list_type push_front(const T& val, list_type head);
list_type push_front(T&& val, list_type head);
list_type push_back(const T& val, list_type head);
list_type push_back(T&& val, list_type head);
list_type free(list_type x); // delete first node
list_type free_list(list_type x); // free entire list
};Finally, there is an example of the usage of the iterators.
#include <cassert>
#include <algorithm> max_element, min_element
list_pool<int> pool{22};
auto l1 = pool.new_list();
// credits: pi as random number generator :)
l1 = pool.push_front(3, l1);
l1 = pool.push_front(1, l1);
l1 = pool.push_front(4, l1);
l1 = pool.push_front(1, l1);
l1 = pool.push_front(5, l1);
l1 = pool.push_front(9, l1);
l1 = pool.push_front(2, l1);
l1 = pool.push_front(6, l1);
l1 = pool.push_front(5, l1);
l1 = pool.push_front(3, l1);
l1 = pool.push_front(5, l1);
auto l2 = pool.new_list();
l2 = pool.push_front(8, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(7, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(3, l2);
l2 = pool.push_front(1, l2);
l2 = pool.push_front(1, l2);
l2 = pool.push_front(5, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(9, l2);
l2 = pool.push_front(7, l2);
auto M = std::max_element(pool.begin(l1), pool.end(l1));
assert(*M == 9);
auto m = std::min_element(pool.begin(l2), pool.end(l2));
assert(*m == 1);
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent