Question
Im having some weird logic error and was wondering if someone can double check my code and tell me whats wrong code: #include // size_t
Im having some weird logic error and was wondering if someone can double check my code and tell me whats wrong
code:
#include
#include
#include
#include
#include
#include "primes.h"
template
class UnorderedMap {
public:
using key_type = Key;
using mapped_type = T;
using const_mapped_type = const T;
using hasher = Hash;
using key_equal = Pred;
using value_type = std::pair
using reference = value_type &;
using const_reference = const value_type &;
using pointer = value_type *;
using const_pointer = const value_type *;
using size_type = size_t;
using difference_type = ptrdiff_t;
private:
struct HashNode {
HashNode *next;
value_type val;
HashNode(HashNode *next = nullptr) : next{next} {}
HashNode(const value_type & val, HashNode * next = nullptr) : next { next }, val { val } { }
HashNode(value_type && val, HashNode * next = nullptr) : next { next }, val { std::move(val) } { }
};
size_type _bucket_count;
HashNode **_buckets;
HashNode * _head;
size_type _size;
Hash _hash;
key_equal _equal;
static size_type _range_hash(size_type hash_code, size_type bucket_count) {
return hash_code % bucket_count;
}
public:
template
class basic_iterator {
public:
using iterator_category = std::forward_iterator_tag;
using value_type = _value_type;
using difference_type = ptrdiff_t;
using pointer = value_type *;
using reference = value_type &;
private:
friend class UnorderedMap
using HashNode = typename UnorderedMap
const UnorderedMap * _map; // ++ operator
HashNode * _ptr;
explicit basic_iterator(UnorderedMap const * map, HashNode *ptr) noexcept{
_ptr = ptr;
_map = map;
}
public:
basic_iterator() : _ptr(nullptr) {};
basic_iterator(const basic_iterator &) = default;
basic_iterator(basic_iterator &&) = default;
~basic_iterator() = default;
basic_iterator &operator=(const basic_iterator &) = default;
basic_iterator &operator=(basic_iterator &&) = default;
reference operator*() const {return _ptr->val;}
pointer operator->() const {return &(_ptr->val);}
basic_iterator &operator++() {
if (_ptr == nullptr){
return *this;
}
else if (_ptr->next == nullptr){
size_type bucket = _map->_bucket(_ptr->val);
while ((bucket +1) !=_map->_bucket_count ){
bucket ++;
if (_map->_buckets[bucket] != nullptr){
_ptr = _map->_buckets[bucket];
return *this;
}
}
_ptr = nullptr;
return *this;
}
_ptr = _ptr->next;
return *this;
}
basic_iterator operator++(int) {
basic_iterator temp(_map, this->_ptr);
if (_ptr == nullptr){
return temp;
}
else if (_ptr->next == nullptr){
size_type bucket = _map->_bucket(_ptr->val);
while ( (bucket+ 1) != _map->_bucket_count ){
bucket ++;
if (_map->_buckets[bucket] != nullptr){
_ptr = _map->_buckets[bucket];
return temp;
}
}
_ptr =nullptr;
return temp;
}
else{
_ptr= _ptr->next;
}
return temp;
}
bool operator==(const basic_iterator &other) const noexcept {return _ptr == other._ptr;}
bool operator!=(const basic_iterator &other) const noexcept {return !(*this == other);}
};
using iterator = basic_iterator
using const_iterator = basic_iterator
class local_iterator {
public:
using iterator_category = std::forward_iterator_tag;
using value_type = std::pair
using difference_type = ptrdiff_t;
using pointer = value_type *;
using reference = value_type &;
private:
friend class UnorderedMap
using HashNode = typename UnorderedMap
HashNode * _node;
explicit local_iterator( HashNode * node ) noexcept{
_node = node;
}
public:
local_iterator() : _node(nullptr){}
local_iterator(const local_iterator &) = default;
local_iterator(local_iterator &&) = default;
~local_iterator() = default;
local_iterator &operator=(const local_iterator &) = default;
local_iterator &operator=(local_iterator &&) = default;
reference operator*() const {return _node->val;}
pointer operator->() const { return &(_node->val);}
local_iterator & operator++(){
if (_node == nullptr){
return *this;
}
_node =_node->next;
return *this;
}
local_iterator operator++(int){
if (_node == nullptr){
local_iterator it(nullptr);
return it;
}
local_iterator temp(this->_node);
this->_node = _node->next;
return temp;
}
bool operator==(const local_iterator &other) const noexcept {return _node == other._node;}
bool operator!=(const local_iterator &other) const noexcept {return !(*this == other);}
};
private:
size_type _bucket(size_t code) const {return _range_hash(code, _bucket_count);}
size_type _bucket(const Key & key)const {return _bucket(_hash(key));}
size_type _bucket(const value_type & val) const {return _bucket(val.first);}
HashNode*& _find(size_type code, size_type bucket, const Key & key){
HashNode** cur = &_buckets[bucket];
while (*cur != nullptr){
if (_equal((*cur)->val.first, key)){
return *cur;
}
cur = &((*cur)->next);
}
return *cur;
}
HashNode*& _find(const Key & key) {
size_type code = _hash(key);
size_type bucket = _bucket(code);
return _find(code, bucket, key);
}
HashNode * _insert_into_bucket(size_type bucket, value_type && value) {
HashNode* new_node = new HashNode(std::move(value), _buckets[bucket]);
_buckets[bucket] = new_node;
if (!_head || _bucket(_head->val) > bucket) {
_head = new_node;
}
return new_node;
}
void _move_content(UnorderedMap & src, UnorderedMap & dst) {
src._buckets = new HashNode *[_bucket_count]();
src._head = nullptr;
src._size = 0;
dst._bucket_count = std::move(src._bucket_count);
dst._buckets = std::move(src._buckets);
dst._head = std::move(src._head);
dst._size = src._size;
dst._hash = src._hash;
dst._equal = src._equal;
}
public:
explicit UnorderedMap(size_type bucket_count, const Hash & hash = Hash { },
const key_equal & equal = key_equal { }) {
_bucket_count = next_greater_prime(bucket_count);
_hash = hash;
_equal = equal;
_head = nullptr;
_size = 0;
_buckets = new HashNode * [_bucket_count]();
}
~UnorderedMap() {
clear();
delete [] _buckets;
}
UnorderedMap(const UnorderedMap & other){
_bucket_count = other._bucket_count;
_buckets = new HashNode*[_bucket_count]{};
_head = nullptr;
_size = 0;
iterator it(&other, other._head);
while (it._ptr != nullptr){
this->insert((*it));
it ++;
}
_hash = other._hash;
_equal = other._equal;
}
UnorderedMap(UnorderedMap && other) {
_move_content(other, *this);
}
UnorderedMap & operator=(const UnorderedMap & other) {
if (this == &other){
return *this;
}
clear();
delete [] _buckets;
_bucket_count = other._bucket_count;
_buckets = new HashNode*[_bucket_count]{};
_head = nullptr;
_equal = other._equal;
_hash = other._hash;
iterator it(&other, other._head);
while (it._ptr != nullptr){
this->insert((*it));
it ++;
}
return *this;
}
UnorderedMap & operator=(UnorderedMap && other) {
if (this == &other){
return *this;
}
this->clear();
delete[]_buckets;
_move_content(other, *this);
return *this;
}
void clear() noexcept {
if (_head == nullptr){
return;
}
iterator it(this,_head);
while (it._ptr!= nullptr){
erase((*it).first);
it++;
}
_size = 0;
}
size_type size() const noexcept {return _size;}
bool empty() const noexcept {return _size == 0;}
size_type bucket_count() const noexcept {return _bucket_count;}
iterator begin() {iterator it(this, _head); return it;}
iterator end() {iterator it(this, nullptr); return it;}
const_iterator cbegin() const {const_iterator it(this, _head);return it;};
const_iterator cend() const {const_iterator it(this, nullptr);return it;};
local_iterator begin(size_type n) {return local_iterator(_buckets[n]);}
local_iterator end(size_type n) {return local_iterator(nullptr);}
size_type bucket_size(size_type n) {
HashNode* ptr = _buckets[n];
size_type size = 0;
if (ptr == nullptr){
return 0;
}
while (ptr != nullptr){
size ++;
ptr = ptr->next;
}
return size;
}
float load_factor() const {
float bucket = bucket_count();
float size1= size();
return size1/bucket;
}
size_type bucket(const Key & key) const {return _bucket(key);}
std::pair
HashNode* cur = _find(value.first);
if (cur == nullptr){
_insert_into_bucket(_bucket(value),std::move(value));
iterator it(this, _find(value.first));
return std::pair
}
else{
iterator it(this, nullptr);
return std::pair
}
}
std::pair
HashNode* cur = _find(value.first);
if (cur == nullptr){
value_type copy = value;
_insert_into_bucket(_bucket(value),std::move(copy));
iterator it(this, _find(value.first));
return std::pair
}
else{
iterator it(this, nullptr);
return std::pair
}
}
iterator find(const Key & key) {
iterator it(this, _buckets[_bucket(key)]);
while (it._ptr != nullptr){
if (_equal(it->first,key)){
return it;
}
++it;
}
it._ptr = nullptr;
return it;
}
T& operator[](const Key & key){
iterator it = find(key);
if (it._ptr == nullptr){
mapped_type map = key;
size_type bucket = _bucket(key);
value_type value(key, map);
HashNode* ptr = _insert_into_bucket(bucket, std::move(value));
return ptr->val.second;
}
else{
return (*it).second;
}
}
iterator erase(iterator pos) {
if (pos._ptr == nullptr){
return pos;
}
size_type bucket = _bucket(*pos);
iterator it(this, _buckets[bucket]);
if (it == pos){
if (_head == it._ptr){
iterator newhead(this, it._ptr);
newhead++;
_head = newhead._ptr;
}
_buckets[bucket] = it._ptr->next;
it++;
delete pos._ptr;
_size --;
return it;
}
while (it._ptr->next != pos._ptr){
it++;
}
it._ptr->next = pos._ptr->next;
delete pos._ptr;
_size --;
it++;
return it;
}
size_type erase(const Key & key) {
iterator pos = find(key);
if (pos._ptr != nullptr){
pos = erase(pos);
return 1;
}
return 0;
}
template
friend void print_map(const UnorderedMap
};
template
void print_map(const UnorderedMap
using size_type = typename UnorderedMap
using HashNode = typename UnorderedMap
for(size_type bucket = 0; bucket
os
HashNode const * node = map._buckets[bucket];
while(node) {
os val.first val.second
node = node->next;
}
os
}
}
ERRORS:
10) constructor_copy (0/5) * * * * *STDOUT & STDERR* * * * * --CMD : 0-- -STDOUT- make: Entering directory '/autograder/source/tests' g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission ../. ./submiss g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission ../. ./submiss g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/m g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/x g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/t g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/a g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./../submission tests/constru [ ========== ] Running 1 test cases. [ RUN UnorderedMap . constructor_copy Expected : (shad_map. size( ) + 1) == (mh.n_allocs( ) ) Actual : 143 vs 137 FAILED UnorderedMap . constructor_copy (254000ns) ====] 1 test cases ran. PASSED 1 0 tests. FAILED 1 tests, listed below: FAILED ] UnorderedMap . constructor_copy rm rtest/utils/memhook.o rtest/utils/xoshiro256.0 ../. ./submission/primes.ortest/utils/typegen.o ../. make: Leaving directory ' / autograder/source/tests' --STDERR- make: *** [rtest/makefile: 94: run/constructor_copy ] Error 1 + +++++++++++++ ++ Test exited with 2 on cmd make -C tests RTEST_SRC_DIR=. ./. ./submission -j12 run/constructor_copy10) operator_copy (0/6) * * * * *STDOUT & STDERR* * * * * CMD : 0-- -STDOUT--- make: Entering directory '/autograder/source/tests' g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission ../. ./submission g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission ../../submission g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./../submission rtest/utils/memh g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./../submission rtest/utils/xosh g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/type g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/asse g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission tests/operator_c =zzz====] Running 1 test cases. [ RUN UnorderedMap . operator_copy Expected : (src_shad_map . size ( ) + 1) == (mh.n_allocs( ) ) Actual : 749 vs 724 FAILED UnorderedMap . operator_copy (2780000ns) ====] 1 test cases ran. PASSED 1 0 tests. FAILED ] 1 tests, listed below: FAILED ] UnorderedMap . operator_copy rm rtest/utils/memhook.o rtest/utils/xoshiro256.0 ../../submission/primes.ortest/utils/typegen.o ../. ./s make: Leaving directory '/ autograder/source/tests' -STDERR-- make: *** [rtest/makefile : 94: run/operator_copy] Error 1 + +++++++++++++ ++ Test exited with 2 on cmd "make -C tests RTEST_SRC_DIR=. ./ . ./submission -j12 run/operator_copy"10) iterator (0/4) * * * * *STDOUT & STDERR* * * * * -CMD : 0--- -STDOUT---- make: Entering directory '/ autograder/source/tests' g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission ../. ./submission g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission . . / . ./submission g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/meml g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/xosh g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/type g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission rtest/utils/asse g++ -std=c++17 -Wall -pedantic -DDEBUG -g -Irtest/include -Iinclude -I. ./. ./submission tests/iterator.c [ ==========] Running 1 test cases. [ RUN UnorderedMap . iterator Expected : (shad_map. size( ) ) == (map. size( ) ) Actual : 748 vs 0 FAILED UnorderedMap . iterator (815000ns) ====] 1 test cases ran. PASSED 1 0 tests. FAILED 1 tests, listed below: FAILED UnorderedMap . iterator rm rtest/utils/memhook.o rtest/utils/xoshiro256.0 ../. ./submission/primes.ortest/utils/typegen.o . ./. ./s make: Leaving directory ' / autograder/source/tests' -STDERR--- make: *** [rtest/makefile: 94: run/iterator] Error 1 + +++++++++++++++ Test exited with 2 on cmd "make -C tests RTEST_SRC_DIR=. ./. ./submission -j12 run/iteratorStep by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started