I am trying to reimplement the STL map container and I have a problem where each time I insert a value to make a node I am overwriting the previous node, i.e. i insert an std::pair<int , std::string>(1, “hello”) and then I insert another std::pair<int , std::string>(2, “hi”) but when I output my root nodes first value it changes from 1 to 2. My code for my tree node is as follows :
#ifndef CONTAINERS_MAP_NODE_H
#define CONTAINERS_MAP_NODE_H
#define RED 0
#define BLACK 1
namespace ft {
template<typename T>
class rb_tree_node {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree_node<T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
public:
rb_tree_node<T> *parent;
rb_tree_node<T> *left;
rb_tree_node<T> *right;
// 1 for black, 0 for red
int color;
value_type *data;
public:
rb_tree_node() :
parent(NULL),
left(NULL),
right(NULL),
color(BLACK),
data(NULL) {}
rb_tree_node(value_type *v, int color = BLACK) :
parent(NULL),
left(NULL),
right(NULL),
color(color),
data(v) {}
rb_tree_node(const rb_tree_node &src) :
parent(src.parent),
left(src.left),
right(src.right),
color(src.color),
data(src.data) {}
~rb_tree_node() {}
self_type &operator=(const self_type &rhs)
{
this->data = rhs.data;
this->parent = rhs.parent;
this->left = rhs.left;
this->right = rhs.right;
this->color = rhs.color;
return (*this);
}
};
}
#endif //CONTAINERS_MAP_NODE_H
for my insert function for the tree :
#ifndef CONTAINERS_RB_TREE_H
#define CONTAINERS_RB_TREE_H
#include "map_node.h"
namespace ft {
template<typename Key, typename Mapped, typename T>
class rb_tree {
public:
typedef rb_tree_node<T> *node_ptr;
typedef rb_tree<Key, Mapped, T> self_type;
typedef T value_type;
typedef T *pointer;
typedef T &reference;
typedef Key key_type;
typedef Mapped mapped_type;
private:
node_ptr root;
public:
rb_tree() : root(NULL) {}
rb_tree(const rb_tree &src) : root(src.root) {}
node_ptr find(key_type k) {
node_ptr n = this->root;
if (!n)
return NULL;
if (k == n->data->first)
return n;
else {
while (n) {
if (!n->data->first)
return NULL;
if (k > n->data->first)
n = n->right;
else if (k < n->data->first)
n = n->left;
else
return n;
}
}
return n;
}
void left_rotate(node_ptr x) {
node_ptr y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
this->root = y;
}
else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void right_rotate(node_ptr x) {
node_ptr y = x->left;
x->left = y->right;
if (y->right != NULL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
y = this->root;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
void print(node_ptr p,int start)
{
start++;
if (p->right != NULL)
{
print(p->right , start);
}
for (int i = 0; i <= start; i++)
{
std::cout<<" ";
}
std::cout << ((p->data) ? p->data->first : 0) << " " << ((p->color == 1) ? "B" : "R") << std::endl;
if (p->left != NULL)
{
print(p->left, start);
}
}
void check_rb_violation(node_ptr node) {
if (node == this->root || node->parent->color == BLACK) {
return ;
}
else {
while (node->parent && node->parent->color == RED) {
if (node->parent == node->parent->parent->right) {
node_ptr u = node->parent->parent->left;
if (u->color == RED) {
u->color = BLACK;
node->parent->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
}
else if (node == node->parent->left) {
node = node->parent;
left_rotate(node);
node->parent->color = BLACK;
node->parent->parent->color = RED;
right_rotate(node);
}
}
else if (node->parent == node->parent->parent->left) {
node_ptr u = node->parent->parent->right;
if (u->color == RED) {
u->color = BLACK;
node->parent->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
}
else if (node == node->parent->right) {
node = node->parent;
right_rotate(node);
node->parent->color = BLACK;
node->parent->parent->color = RED;
left_rotate(node);
}
}
}
this->root->color = BLACK;
}
}
node_ptr insert_data(value_type data) {
node_ptr node = new rb_tree_node<T>(&data, 0);
if (this->root == NULL) {
this->root = node;
node->color = 1;
}
else {
node_ptr x = this->root;
node_ptr y = NULL;
while (x && x->data) {
y = x;
if (x->data->first == node->data->first) {
std::cout << x->data->first << node->data->first << std::endl;
std::cout << "Cannot add duplicate key" << std::endl;
return x;
}
if (x->data->first > node->data->first) {
x = x->left;
}
else {
x = x->right;
}
}
x = node;
node->parent = y;
if (y->data->first > node->data->first) {
if (y->left)
delete y->left;
y->left = node;
}
else {
if (y->right)
delete y->right;
y->right = node;
}
}
node->right = new rb_tree_node<T>();
node->left = new rb_tree_node<T>();
node->right->parent = node;
node->left->parent = node;
check_rb_violation(node);
return (node);
}
};
}
#endif //CONTAINERS_RB_TREE_H
and this is the insert function I have as my interface between my map container and the tree library :
std::pair<iterator,bool> insert (const value_type& val) {
node_pointer n = this->tree.find(val.first);
if (n) {
return std::pair<iterator, bool>(n, false);
}
else {
n = this->tree.insert_data(val);
this->t_size++;
return std::pair<iterator, bool>(n, true);
}
}
My current thinking is that it may have something to do with the fact that i am passing by reference in my insert function as seen above but then passing by value in my insert_data function in my tree library.
