Data Structures [WIP]

[Nineshadow]

WORK IN PROGRESS

 

A data structure is a particular technique used to organize and store information in a computer with efficiency in mind. They can store both primitive and abstract data types and they are quite varied.I will be using C++ to demonstrate most examples , as that is my language of choice, and I will also be implementing some data structures myself. While most programming languages have them built-in, it's always good to know how everything works.

 

Arrays

The most simple data structure is the array, which I think most of us are familiar with. In an array, each element can be identified by its index, also known as its key, and all elements are stored in a continuous area in memory. So, an array of 10 32-bit integers with indeces going from 0 to 9 will be stored in memory at the addresses of , let's say 2000, 2004, 2008, ... , 2036. Most programming languages recognize the data type of an array, so you can simply increment the pointer to reach the next element.

 

While they are very simple to understand and to work with, usually they're all you need, there is one problem with arrays : due to their nature, they have a fixed size. Of course, you can reserve aditional storage in memory, but where's the fun in that? D:

 

The declaration for an array is quite simple, in C/C++ :

So, to create an array which will store 10 integers:

You can also make 2-dimensional array, which is pretty much a 2D table/grid, this kind of array being called a matrix.

- number 58 is the element found at [5][7]

Note, in most programming languages, the indexes grow from left to right and from top to bottom when you imagine a matrix as in the picture above.

 

Declaration of 2D arrays :

For example :

will create a 2D array with the sizes of 10, and 10, just like in the picture above. This kind of matrix with the same numbers of columns and rows is called a square matrix.

Note that in the declaration of a 2D array, the first size specifies the number of rows, and the second the number of columns.

 

In reality, a 2D array is simply an array of arrays.

Honestly, an array can have an infinite amount of dimensions.

 

While arrays are most of the times sufficient for everything we need and they are very efficient at acessing its elements, but they have a simple drawback : they occupy a continuous area in memory, and, as such, they aren't dynamic. You can't add or remove an element from an array, not without reserving memory space. (for those features, we could make a container, which is exactly what the vector in the STL does)

So, what can we do to solve our issue? The answer consists of dynamic sequence containers, which include lists, deques , queues and stacks.

 

 

Stacks

 

A stack is a container of objects based on the LIFO principle (last-in-first-out). Its name is pretty descriptive , I think. Imagine you have a stack of books. You can add books on top of it, and you can easily remove the book on top. That's how a stack works. You can add an object to the top, and only the top element can be removed with a single operation. A stack supports 2 main operations:

push(obj) , which adds an object to the top of the stackpop() , which removes the object on the top of the stack

Of course, we'll also want to include a few other operations :

top() , which returns a reference to the object at the top of the stacksize() , which returns the number of elements from the stackisEmpty() , which I think you know what it should do.

Let's go ahead and make our own stack , it's pretty easy.

 

A stack is a container of any kind of objects, which means it should support stuff like integers, booleans, floats, even your own custom objects, and since we won't be writing a different stack for each data type, we'll make a generic stack class with the wonderful power of templates!

Let's go ahead and build our base :

That's pretty simple. However, you can notice that in our top() function we return a constant reference to the object of type T. Why don't we simply return the object itself, and instead we return a reference to it? Due to efficiency. When you return a reference you don't create an unnecessary overhead. The compiler won't allocate space for the returned object or for the formal parameter. The reference is constant because we don't want to access the referenced variable directly for the reason of avoiding mistakes , such as modifying the referenced object, our input, and hence our returned object, unwittingly, not to mention you wouldn't be able to parse concrete values(eg. 8, 4.3, 'c' , etc.).

Now, we need to make our elements. We can only access the stack from top to bottom, so we for each object we'll need a reference to the one underneath it. Thus, we'll make a structure which will be the base of our elements inside the stack. Obviously, it needs to store the data we need, and the reference I told you about.We'll make it private for good reasons.

Note that we also want to have a reference to the top object all the time, and we will also keep the count of elements.

 

We end up with :

Now, let's initialize our stack, which means making a null stack, which has a null top object. If you are using newer compilators , such as the one in Visual Studio, use nullptr instead of NULL , since NULL is just a macro(it's the integer 0, representing a null address).

A stack is null(has no elements) if its top is null, so that's what we'll use for our isEmpty() function :

Now we got to adding an object on top! Quite exciting, ey? It's really easy though. We make a new element with a certain data. The reference in that element to the element below it will be the reference to our top element, then we'll make our new element the top one. We then increment our counter. Told you it was simple. We'll also want a special case for when we add the first element.

Removing the top element is easy too. We save the adress of the top , the element underneath it becomes our new top, we delete our old top and we decrement the counter.

Getting the constant reference to the top object :

We could have also just used our pop() function, but that would also keep the counter.

 

Our stack class , in its full glory, is :

You can easily add it into a header file, let's call it "Stack.h". Make sure to include it when you want to use it.

To initialize a stack :

For example :

Queues

A queue is a container,  very similar to a stack, based on the FIFO(first-in-first-out) principle. Basically, you can add elements on the bottom of the queue, but you can only remove elements from the top. Or better said, you can only add elements to the back of the queue, and you can only remove elements from the front of the queue. You can iterate through it from the back to the front.

 

A queue has a few basic functions :

enque(obj) , which adds an object at the back of the queuedeque() , which removes the object at the front of the queuefront() , which returns a reference to the front.back() , which returns a reference to the back.size() , which returns the number of elements.isEmpty()

Again, a queue is a container of objects, and we'll make a generic class. It will be very similar to our Stack class.

A queue can only be iterated through from the back to the front, so for each element we'll want a reference to the next one. We know we reach the top when the top element has a null reference.

 

Initialization implies both the back and the top have a null reference.

A queue is empty when our front is null :

count() :

Adding an element at the back : we make a new element with the given data, the reference "next" will point to the current back, then our new element becomes the back. Increment count.

Removing an element from the front :

Reference to the object in the front element :

Same thing for the back :

Deconstructor : destroy every element, turn by turn, untill we reach the top which we know since it has a null reference :

Our Queue class is :

Again, to use it, put all that code in a header file and include it in your main class.

 

Deque

 

A deque is basically a double-ended queue, implying it can be expanded and contracted at both ends.

Will make this later.

 

Linked Lists

 As I've said before, arrays are simple and efficient structures to store data in a certain order , but they have disadvantages. You can't adapt them too much, you can't easily remove or insert an element while not using extra memory. Linked lists are our alternatives to arrays which fix all those issues. Each linked list has nodes(elements) which whilest containing our data, they also contain references to other nodes so they can be connected in a certain order.

 

Simple Linked List

A simple linked list contains in a node, a reference to the next one.

Knowing its first node, called a head, and using these references, we can get through all our data and reach its last node, called a tail, which has a null reference. That null reference signals the end of the list.

 

I will update this later, but until then, here's the full code, it's a bit messy, but I'll fix it :

Doubly Linked List

A doubly linked list is a lot like a single linked list, but it has an additional pointer in its node which reference the previous one. This allows us to iterate through the list in any direction. We have null pointers to signal both the begining and the end this time.

 

Here's a quick code again :

Note that this was made only for the integer data type, and it also has a sorting function.

 

This , however , was made using templates and supports any data type :

<data_type> <array_name>[<size>];

int arr[10];

<data_type> <name>[<size1>][<size2>]

int m[10][10]

template<typename T>class Stack {public :Stack(); // constructor~Stack(); // destructorint size() const; // returns number of elements in stackbool isEmpty() const; // pretty obvious...const T& top() const; // returns a constant reference to the top objectvoid push(const T& obj); // adds an object to the topvoid pop(); // removes the object from top}

private :struct Element {T data;Element *below;};Element *top;int count;

template<typename T>class Stack{public :    Stack();    ~Stack();    int size() const;    bool isEmpty() const;    const T& top() const;    void push(const T& obj);    void pop();private :    struct Element    {        T data;        Element *below;    };    Element *top;    int count;};

template<typename T> Stack::Stack(){top = NULL; // initializng the stack implies the top being nullcount = 0; // also count must be 0}

template<typename T> bool Stack<T>::isEmpty() const{    return top == NULL;}Returning the number of elements is pretty easy :template<typename T> int Stack<T>::size() const{return count;}

template<typename T> void Stack<T>::push(const T& ob){if(isEmpty()){top = new Element;top->data = ob;top->below = nullptr;count = 1;}else{Element * newElement = new Element;newElement->data = ob;newElement->below = top;top = p;++count;}}

template<typename T> void Stack<T>::pop(){if(isEmpty()) throw "Error. Empty stack.";Element * oldTop = top;top = top->below;delete oldTop;--count;}

template<typename T> const T& Stack<T>::top() const{if(isEmpty()) throw "Error. Empty stack.";return top->data;}Deconstructor :template<typename T> Stack<T>::~Stack(){while(top != nullptr){Element *oldTop = top;top = top->below;delete q;}}

template<typename T>class Stack{public :Stack();~Stack();int size() const;bool isEmpty() const;const T& top() const;void push(const T& obj);void pop();private :struct Element{T data;Element *below;};Element *top;int count;};template<typename T> Stack::Stack(){top = NULL;count = 0;}template<typename T> bool Stack<T>::isEmpty() const{return top == NULL;}template<typename T> int Stack<T>::size() const{return count;}template<typename T> void Stack<T>::push(const T& ob){if(isEmpty()){top = new Element;top->data = ob;top->below = nullptr;count = 1;}else{Element * newElement = new Element;newElement->data = ob;newElement->below = top;top = p;++count;}}template<typename T> void Stack<T>::pop(){if(isEmpty()) throw "Error. Empty stack.";Element * oldTop = top;top = top->below;delete oldTop;--count;}template<typename T> const T& Stack<T>::top() const{if(isEmpty()) throw "Error. Empty stack.";return top->data;}template<typename T> Stack<T>::~Stack(){while(top != nullptr){Element *oldTop = top;top = top->below;delete oldTop;}}

Stack< <data_type> > <variable_name>;

Stack<int> stack;

template<typename T>class Queue{public:    Queue(); // Constructor    ~Queue(); // Destructor    void enqueue(const T& obj); // add an element in back    void dequeue(); // remove element from front    const T& front() const; // return reference to front    const T& back() const; // return reference to back    int size() const; // return number of elements    bool isEmpty() const;private:    struct Element    {        T data;        Element *next;    };    Element * front;    Element * back;    int count;};

template<typename T> Queue<T>::Queue(){    front = back = NULL;    count = 0;}

template<typename T> bool Queue<T>::isEmpty() const{    return front == NULL;}

template<typename T> int Queue<T>::size() const{    return count;}

template<typename T> void Queue<T>::enqueue(const T& ob){    if(isEmpty())     {        front = new Element;        front->data = ob;        front->next = nullptr;         back = front;        count = 1;    }    else    {        Element * p = new Element;        p->data = ob;        p->next = back;         back = p;        ++count;      }}

template<typename T> void Queue<T>::dequeue(){    if(isEmpty()) throw "Error. Empty Queue.";    Element * q = front;     front = front->next;     delete q;    --count;}

template<typename T> const T& Queue<T>::front() const{    if(isEmpty()) throw "Error. Empty Queue.";    return front->data;}

template<typename T> const T& Queue<T>::back() const{    if(isEmpty()) throw "Error. Empty Queue.";    return back->data;}

template<typename T> Queue<T>::~Queue(){    while(front != NULL)    {        Element * q = front;        front = front->next;        delete q;    }}

template<typename T>class Queue{public:    Queue();    ~Queue();    void enqueue(const T& obj);    void dequeue();    const T& front() const;    const T& back() const;    int size() const;    bool isEmpty() const;private:    struct Element    {        T data;        Element * next;    };    Element *front;    Element *back;    int count;};template<typename T> Queue<T>::Queue(){    front = back = NULL;    count = 0;}template<typename T> bool Queue<T>::isEmpty() const{    return front == NULL;}template<typename T> int Queue<T>::size() const{    return count;}template<typename T> void Queue<T>::enqueue(const T& ob){    if(isEmpty())    {        front = new Element;        front->data = ob;        front->next = nullptr;        back = front;        count = 1;    }    else    {        Element * p = new Element;        p->data = ob;        p->next = NULL;        back->next = p;        back = p;        ++count;    }}template<typename T> void Queue<T>::dequeue(){    if(isEmpty()) throw "Error. Empty Queue.";    Element * q = front;    front = front->next;    delete q;    --count;}template<typename T> const T& Queue<T>::front() const{    if(isEmpty()) throw "Error. Empty Queue.";    return front->data;}template<typename T> const T& Queue<T>::back() const{    if(isEmpty()) throw "Error. Empty Queue.";    return back->data;}template<typename T> Queue<T>::~Queue(){    while(front != NULL)    {        Element * q = front;        front = front->next;        delete q;    }}

class Lista{public :    struct Iterator;    Lista()    {        head = tail = NULL;    }    ~Lista()    {        if(!isEmpty()) clear();    }    void push_back(int elem);    void push_front(int elem);    void insert_before(int elem, Iterator nod);    void insert_after(int elem, Iterator nod);    void pop_front();    void pop_back();    void remove(Iterator nod);    bool isEmpty() const    {        return head == NULL;    }    void clear();    Iterator front() const    {        return Iterator(head);    }    Iterator end() const    {        return Iterator(NULL);    }    Iterator search(int value) const;private :    struct Nod    {        int data;        Nod *next;    };    Nod *head;    Nod *tail;public :    struct Iterator    {        friend class Lista;        Iterator()        {            list = NULL;        }        Iterator(Nod *ls)        {            list = ls;        }        int& operator*()        {            if(list != NULL) return list->data;            else throw "Null iterator!";        }        //postfix        Iterator operator++(int)        {            Iterator temp = *this;            ++(*this);            return temp;        }        //prefix        Iterator& operator++()        {            list = list->next;            return *this;        }        bool operator==(const Iterator& it) const        {            if(it.list == this->list) return true;            else return false;        }        bool operator!=(const Iterator& it) const        {            if(!(it==*this)) return true;            else return false;        }    private :        Nod *list;    };};void Lista::push_front(int elem){    if(isEmpty())    {        head = new Nod;        head -> data = elem;        head -> next = NULL;        tail = head;    }    else    {        Nod *nod = new Nod;        nod->data=elem;        nod->next=head;        head=nod;    }}void Lista::push_back(int elem){    if(isEmpty())    {        head = new Nod;        head -> data = elem;        head -> next = NULL;        tail = head;    }    else    {        Nod *nod = new Nod;        nod->data=elem;        nod->next=NULL;        tail->next = nod;        tail = nod;    }}void Lista::insert_after(int elem, Iterator nod){    Nod *newNod = new Nod;    newNod -> data = elem;    newNod -> next = nod.list->next;    nod.list->next = newNod;    if(nod.list == tail) tail = newNod;}void Lista::insert_before(int elem, Iterator nod){    Nod *newNod = new Nod;    newNod -> data = nod.list->data;    nod.list->data=elem;    newNod -> next = nod.list->next;    nod.list->next = newNod;    if(nod.list == tail) tail = newNod;}Lista::Iterator Lista::search(int value) const{    for(Nod* it = head; it != NULL; it = it->next)    {        if(it->data == value) return Iterator(it);    }    return end();}void Lista::pop_front(){    if(isEmpty()) throw "Empty List";    if(head==tail) delete head;    head = tail = NULL;    Nod *temp = head;    head = head->next;    delete temp;}void Lista::pop_back(){    if(isEmpty()) throw "Empty List";    if(head==tail) delete head;    head = tail = NULL;    Nod *pred;    for(pred = head; pred->next->next != NULL; pred = pred->next);    pred->next = NULL;    delete tail;    tail = pred;}void Lista::clear(){    Nod *it = head, *temp;    while(it!=NULL)    {        temp = it;        it = it->next;        delete temp;    }    head = tail = NULL;}

class ListD{private :    struct Node    {        int data;        Node *next;        Node *prev;    };    Node *tail;    Node *head;public :    struct Iterator    {    private:        Node * list;    public:        friend class List;        Iterator()        {            list == NULL;        }        Iterator(Node *ls)        {            list = ls;        }        int& operator*() const        {            if(list!=NULL) return list->data;            else throw "Null Iterator";        }        Iterator& operator++()        {            list = list->next;            return *this;        }        Iterator operator++(int)        {            Iterator temp = *this;            ++(*this);            return temp;        }        bool operator==(const Iterator& it) const        {            if(it.list == this->list) return true;            else return false;        }        bool operator!=(const Iterator& it) const        {            if(!(it==*this)) return true;            else return false;        }    };    bool isEmpty()    {        return head == NULL;    }    List()    {        head=tail=NULL;    }    ~List()    {        if(!isEmpty())clear();    }    Iterator end() const    {        return Iterator(NULL);    }    Iterator front() const    {        return Iterator(head);    }    Iterator search(int value) const    {        for(Node *i = head; i !=NULL; i=i->next)            if(value==i->data) return Iterator(i);    }    void pop_back()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = tail->prev;            delete tail;            temp->next = NULL;            tail = temp;        }    }    void pop_front()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = head->next;            delete head;            temp->prev = NULL;            head = temp;        }    }    void remove(Iterator node)    {        if(isEmpty()) throw "Empty List";        else if(head==tail)        {            delete head;            head=tail=NULL;            return;        }        else if(node==this->end())        {            pop_back();        }        else if(node==this->front())        {            pop_front();        }        else        {            node.list->prev->next= node.list->next;            node.list->next->prev = node.list->prev;        }    }    void insert_after(int value, Iterator node)    {        Node *newNode = new Node;        newNode->data=value;        newNode->prev=node.list;        newNode->next=node.list->next;        node.list->next->prev=newNode;        node.list->prev->next=newNode;    }    void insert_before(int value, Iterator node)    {        Node *newNode = new Node;        newNode->data=value;        newNode->next=node.list;        newNode->prev=node.list->prev;        node.list->prev->next=newNode;        node.list->next->prev=newNode;    }    void push_back(int value)    {        if(isEmpty())        {            head = new Node;            head->data=value;            head->next=NULL;            head->prev=NULL;            tail=head;        }        else        {            Node *newNode = new Node;            newNode->data=value;            newNode->next=NULL;            newNode->prev=tail;            tail->next=newNode;            tail=newNode;        }    }    void push_front(int value)    {        if(isEmpty())        {            Node newNode;            head = tail = &newNode;            newNode.data = value;            newNode.prev = NULL;            newNode.next = NULL;        }        else        {            Node newNode;            newNode.data = value;            newNode.prev=NULL;            newNode.next = head;            head->prev = &newNode;            head = &newNode;        }    }    void clear()    {        Node *i = head, *temp;        while(i!=NULL)        {            temp=i;            i=i->next;            delete temp;        }        head=tail=NULL;    }    void print()    {        for(List::Iterator it = this->front(); it!=this->end(); it++)std::cout << *it << ' ';            std::cout<<"\n";    }    void swap(Iterator node1, Iterator node2){    int temp = node1.list->data;    node1.list->data = node2.list->data;    node2.list->data=temp;    }    void sort(){    bool is_sorted;    do    {        is_sorted = true;        for(Iterator it = this->front(); Iterator(it.list->next)!=this->end(); it++)            if(it.list->data > it.list->next->data)            {                is_sorted = false;                swap(it.list,it.list->next);            }    }    while(!is_sorted);    }};

template <class T>class List{    struct Node    {        T data;        Node *prev;        Node *next;    };    Node *head;    Node *tail;public:    struct Iterator    {    private:        Node *node;    public:        friend class List;        Iterator()        {            node = NULL;        }        Iterator(Node *n)        {            node = n;        }        T& operator*() const        {            if(node!=NULL) return node->data;            else throw "Null operator";        }        Iterator& operator++()        {            if(node->next==NULL)node=NULL; //throw "Iterator out of bounds";            else {            node=node->next;            return *this;            }        }         Iterator operator++(int)        {            if(node->next==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            Iterator temp = *this;            ++(*this);            return temp;            }        }        Iterator& operator--()        {            if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            node = node->prev;            return *this;            }        }        Iterator operator--(int)        {            if(node->prev==NULL)node=NULL ;//throw "Iterator out of bounds";            else {            Iterator temp = *this;            --(*this);            return temp;            }        }        bool operator==(const Iterator& it) const        {            if(it.node == this->node)return true;            else return false;            }        bool operator!=(const Iterator& it) const        {            if(!(it==*this)) return true;            else return false;            }    };    bool isEmpty()    {        return head ==NULL;    }    List()    {        head=tail=NULL;    }    ~List()    {        if(!isEmpty()) clear();        }    void clear()    {        Node *i = head, *temp;        while(i!=NULL)        {            temp = i;            i=i->next;            delete temp;        }        head=tail=NULL;    }    Iterator end() const    {        return Iterator(tail);    }    Iterator front() const    {        return Iterator(head);    }    void pop_back()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = tail->prev;            delete tail;            temp->next = NULL;            tail=temp;        }    }    void pop_front()    {        if(isEmpty()) throw "Empty List";        else if(head==tail) delete head;        else        {            Node *temp = head->next;            delete head;            temp->prev = NULL;            head=temp;        }    }    void remove(Iterator it)    {        if(isEmpty()) throw "Empty List";        else if(head==tail)        {            delete head;            head = tail = NULL;            return;        }        else if(it==this->end())            pop_back();        else if(it==this->front())            pop_front();        else        {            it.node->prev->next = it.node->next;            it.node->next->prev = it.node->prev;            delete it.node;        }    }    void push_back(T value)    {        if(isEmpty())        {            head = new Node;            head->data = value;            head->next=NULL;            head->prev=NULL;            tail=head;        }        else        {            Node *newNode = new Node;            newNode->data = value;            newNode->next=NULL;            newNode->prev=tail;            tail->next=newNode;            tail=newNode;        }    }    void push_front(T value)    {        if(isEmpty())        {            head = new Node;            head->data = value;            head->next=NULL;            head->prev=NULL;            tail=head;        }        else        {            Node *newNode = new Node;            newNode->data = value;            newNode->prev=NULL;            newNode->next=head;            head->prev=newNode;            head=newNode;        }    }    void swap(Iterator node1, Iterator node2)    {        T temp = node1.node->data;        node1.node->data = node2.node->data;        node2.node->data=temp;    }    void insert_before(T value, Iterator it)    {        Node *newNode = new Node;        newNode->data = value;        it.node->prev->next = newNode;        newNode->prev=it.node->prev;        it.node->prev=newNode;        newNode->next=it.node;    }    void insert_after(T value, Iterator it)    {        Node *newNode = new Node;        newNode->Data = value;        newNode->prev=it.node;        newNode->next=it.node->next;        it.node->next->prev=newNode;        it.node->next=newNode;    }};

[Nineshadow]

At the time of posting it :

Finished the intoduction, arrays and stacks.

 

UPDATE 1 :

Finished queues.

 

Update 2 :

Added code and general description for single linked lists and doubly linked lists.

Added spoilers for better readability.

[Gala]

Uhm...nice? Backstory on topic?

[The Pizza Thief]

6 other members and I are analyzing the information trying to figure out if we can even. 

[CydiaDash]

Definitely will find time to read this....

[Gala]

6 other members and I are analyzing the information trying to figure out if we can even. 

 

It's a tutorial on storing integers better in C code. Usefull if you are into microcontroller programming or software design.

[The Pizza Thief]

It's a tutorial on storing integers better in C code. Usefull if you are into microcontroller programming or software design.

 

Thanks Captain. 

 

In the absence of a rekt meme I have to post this.

 

[Gala]

Thanks Captain. 

 

In the absence of a rekt meme I have to post this.

 

 

 

Piss off. Trying to answer quesstions, and not be a faggot

[The Pizza Thief]

Piss off. Trying to answer quesstions, and not be a faggot

 

You did a good job though, don't be ashamed. I was the one that didn't know what this was all about. 

[Gala]

You did a good job though, don't be ashamed. I was the one that didn't know what this was all about. 

Your PC is fucking awsome. Love the twin 970's. And the blue WINDFORCE logos.

[The Pizza Thief]

Your PC is fucking awsome. Love the twin 970's. And the blue WINDFORCE logos.

 

Thanks a lot mate! Now it looks a little bit better, I changed the case to a Corsair 760t white and it's all looking sexier white/black/blue. 

[Gala]

Thanks a lot mate! Now it looks a little bit better, I changed the case to a Corsair 760t white and it's all looking sexier white/black/blue. 

Got pics? Drolling on your pics @ pcpartpicker. Man that goes all so well together!

[The Pizza Thief]

Got pics? Drolling on your pics @ pcpartpicker. Man that goes all so well together!

I'm yet to take some pictures and update the PCPP page. I will do a new one and post it here somewhere during the rest of August. 

[Gala]

I'm yet to take some pictures and update the PCPP page. I will do a new one and post it here somewhere during the rest of August. 

naaaiceeee m8!

[Nineshadow]

Uhm...nice? Backstory on topic?

I bet I'll have to do this next year at school.

You know, a presentation of all data structures.

[Nineshadow]

6 other members and I are analyzing the information trying to figure out if we can even. 

It's exactly what it says : data structures. Ways of organizing information. Some more abstract than others.

 

I haven't gotten to binary indexed trees yet, that's hard(er) to figure out.

[Gala]

I bet I'll have to do this next year at school.

You know, a presentation of all data structures.

Funny fact, i actually will learn it next year!

 

[Nineshadow]

Funny fact, i actually will learn it next year!

Better get on to it then .

 

When the time comes.

[Gala]

Better get on to it then .

 

When the time comes.

I actually am learning programming Atmel AVR code. Can i rely on you if some stuff gets hairy, some simple questions? Like how to make user input, pause the program and that sort of stuff.

[Nineshadow]

I actually am learning programming Atmel AVR code. Can i rely on you if some stuff gets hairy, some simple questions? Like how to make user input, pause the program and that sort of stuff.

I don't know that much in that field.

[Ciccioo]

nice post as usual :lol:

 

i'll leave a couple comments

 

about arrays:

it's not actually a problem to extend or shrink an array if you created it dynamically (malloc/new). C/C++ does that with realloc(), which allows you to add or remove elements at the end of the array. This makes arrays perfectly fine for representing more complex data structures such as stacks, queues, trees, and that's great because you can't beat the zero memory overhead of an array (no pointers hanging around). STL implementations of vector and stack are probably array-based.

 

and about 2d arrays:

reading the description it looks like 2d arrays are kind of a 1d-array of pointers to 1d-arrays (especially the image looks like that). That is kind of a way that you could do it, but arrays declared in the classic way are different:

// this allocates contiguous memory for n*m integers. there are no pointersint matrix[n][m];// this is pretty much equivalent, in terms of what and where goes into memoryint array[n*m];

[Nineshadow]

 

nice post as usual :lol:

 

i'll leave a couple comments

 

about arrays:

it's not actually a problem to extend or shrink an array if you created it dynamically (malloc/new). C/C++ does that with realloc(), which allows you to add or remove elements at the end of the array. This makes arrays perfectly fine for representing more complex data structures such as stacks, queues, trees, and that's great because you can't beat the zero memory overhead of an array (no pointers hanging around). STL implementations of vector and stack are probably array-based.

 

and about 2d arrays:

reading the description it looks like 2d arrays are kind of a 1d-array of pointers to 1d-arrays (especially the image looks like that). That is kind of a way that you could do it, but arrays declared in the classic way are different:

// this allocates contiguous memory for n*m integers. there are no pointersint matrix[n][m];// this is pretty much equivalent, in terms of what and where goes into memoryint array[n*m];

About the dynamic arrays, I somehow forgot to include that.

[Ciccioo]

About the dynamic arrays, I somehow forgot to include that.

Dynamically allocated arrays are pretty important in C/C++ as they are the standard and only real way to decide the array size at runtime. In your examples and in my previous post we used VLAs, which is a kind of obscure C99 feature that didn't even make it to the C++ standard. Also, that's what makes people say "arghh only use C if you want to do all the memory management hur durr"

[Nineshadow]

Dynamically allocated arrays are pretty important in C/C++ as they are the standard and only real way to decide the array size at runtime. In your examples and in my previous post we used VLAs, which is a kind of obscure C99 feature that didn't even make it to the C++ standard. Also, that's what makes people say "arghh only use C if you want to do all the memory management hur durr"

Honestly, the vector in STL does everything you'd want it to. It even supports "multiple dimensions".

 

My post was more about the techniques behind it . It's fun to know how to do all that stuff.

[Ciccioo]

Honestly, the vector in STL does everything you'd want it to. It even supports "multiple dimensions".

 

My post was more about the techniques behind it . It's fun to know how to do all that stuff.

sure, but it's a high level abstraction that works on dynamic arrays

 

sure, now i'm just nitpicking, feel free to flip me the bird :unsure: the plan was to add something to the thread

i really like to study these things too, just last week i tried to implement some fancy trees that i knew just in theory, and i liked it!