Skip to content

A custom container built in C++ which is compatible with the STL library

License

Notifications You must be signed in to change notification settings

IamShubhamGupto/Splay-Tree-as-a-Container

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

83 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Splay-Tree as a Container

This project recreates the std::map class of C++ using the self-balancing tree data structure Splay Trees. The implementation is generic. Most functionality has been added to the container however there is room for improvements and additional functions.

How to Compile & Test

Linux & Mac

Compilation

git clone https://github.com/IamShubhamGupto/Splay-Tree-as-a-Container.git
cd Splay-Tree-as-a-Container
make clientfile=<ENTER PATH TO CLIENT FILE NAME HERE>
./bin/a.out

EXAMPLE

make clientfile=examples/client1.cpp
./bin/a.out

Testing

Prerequiste:

pip3 install matplotlib

EXAMPLE

python3 tests/run_test.py 

Clean Up

In order to clean the generated files, run make clean.

Member Types

Member Type Definition
key_type template type of the key in the pair
mapped_type template type of the value in the pair
root_ stores root node of the splay tree.
iterator a bidirectional iterator to mapped_type.
const_iterator a bidirectional iterator to constant mapped_type.
reverse_iterator a bidirectional iterator to mapped_type.
const_reverse_iterator a bidirectional iterator to constant mapped_type.

Member Functions

Member Function Definition
(constructor) Splay tree constuctor.
(destructor) Splay tree destructor.
operator= Copy container contents.
Iterators
begin Return iterator to first in-order element.
end Return iterator to beyond-the-last element.
cbegin Return a constant iterator to first in-order element. Read Only.
cend Return a constant iterator to beyond-the-last element. Read Only.
rbegin Return iterator to last in-order element.
rend Return iterator to beyond-the-first element.
crbegin Return a constant iterator to last in-order element. Read Only.
crend Return a constant iterator to beyond-the-first element. Read Only.
Element Access
operator[] Access element using key. If not present, (default) value is inserted.
at Access element using key. If not preseed, out_of_range exception is thrown.
Modifiers
insert Insert new key-value pair into the tree. Incase key already exists, update value and return an iterator to inserted element.
erase Delete a key-value pair based on key. If key does not exist, do nothing.
clear Free the entire splay tree.
Operations
find Search for a key-value pair based on a given key. Return an iterator to pair if found else return end()
printTree Visually print the splay tree.

By

Special thanks to Faraz , Reuben and Madhoolika for testing the container during the early stages of the project 😄