I'm using IAR as compiler for embedded project. I'm trying to introduce some templates for basic types like list, but each STL list object created increases code size by about 200 bytes relatively to our current C style implementation. I tried to implement a small portion of the STL list myself hoping to get a smaller code footprint, but ended up being more heavy than the full STL list. Am I doing something horribly wrong in my usage of templates?
Thanks
P.S. Please note that the code is untested so it may contain dragons.
#ifndef __LINK_LIST_HPP__
#define __LINK_LIST_HPP__
#include <stdint.h>
#include <stdlib.h>
template <typename T> class list
{
private:
struct LinkListElement
{
T payload;
LinkListElement* next;
LinkListElement* prev;
};
public:
class iterator
{
// Need access to LinkListElement struct
friend class list;
public:
iterator() : m_cur_item(NULL){}
iterator(LinkListElement* elem) : m_cur_item(elem){}
iterator(const iterator& other) : m_cur_item(other.m_cur_item){}
~iterator(){}
iterator& operator=(const iterator& other)
{
m_cur_item = other.m_cur_item;
return *this;
}
bool operator==(const iterator& other) const
{
// Compare by position, ignoring the payload contents when comparing iterators.
return (m_cur_item->next == other.m_cur_item->next) &&
(m_cur_item->prev == other.m_cur_item->prev);
}
bool operator!=(const iterator& other) const
{
return !(*this == other);
}
// Prefix increment operator.
iterator& operator++()
{
increment();
return *this;
}
// Postfix increment operator.
iterator operator++(int)
{
iterator copy(*this);
increment();
return copy;
}
// Prefix decrement operator.
iterator& operator--()
{
decrement();
return *this;
}
// Postfix decrement operator.
iterator operator--(int)
{
iterator copy(*this);
decrement();
return copy;
}
T& operator*()
{
// Just so we won't crash, but behavior is undefined.
if (m_cur_item == NULL)
{
return dummy;
}
return m_cur_item->payload;
}
T* operator->()
{
if (m_cur_item == NULL)
{
return NULL;
}
return &(m_cur_item->payload);
}
private:
void increment()
{
if (m_cur_item == NULL || m_cur_item->next == NULL)
{
return;
}
m_cur_item = m_cur_item->next;
}
void decrement()
{
if (m_cur_item == NULL || m_cur_item->prev == NULL)
{
return;
}
m_cur_item = m_cur_item->prev;
}
LinkListElement* m_cur_item;
static T dummy;
};
// Need access to internal LinkListElement pointer
friend class iterator;
list()
{
// Add sentinel to mark end of list.
m_tail = new LinkListElement;
m_tail->next = m_tail;
m_tail->prev = m_tail;
m_head = m_tail;
}
~list()
{
// Clear entire list except for sentinel
clear();
// Destroy sentinel
delete m_tail;
m_head = NULL;
m_tail = NULL;
}
T& back()
{
// empty list with only sentinel. Result of back() is undefined
if (empty())
{
// TODO: Show some debug error
}
return m_tail->prev->payload;
}
T& front()
{
if (empty())
{
// TODO: Show some debug error
}
// m_head is always defined even if list is empty
return m_head->payload;
}
size_t size()
{
return m_count;
}
bool empty()
{
// head == tail means the list is empty
return m_head == m_tail;
}
iterator begin()
{
return iterator(m_head);
}
iterator end()
{
return iterator(m_tail);
}
iterator insert(iterator position, const T& payload)
{
// Validate position by finding it in our list
iterator find = begin();
while (find != end() && find != position)
{
++find;
}
if (find == end())
{
// TODO: Show some debug error
return position;
}
return insert_before(find.m_cur_item, payload);
}
void push_back(const T& payload)
{
insert_before(m_tail, payload);
}
void push_front(const T& payload)
{
insert_before(m_head, payload);
}
iterator erase(iterator position)
{
// Validate position by finding it in our list
iterator find = begin();
while (find != end() && find != position)
{
++find;
}
if (find == end())
{
// TODO: Show some debug error
return position;
}
return remove_at(find.m_cur_item);
}
//iterator erase(iterator first, iterator last); // Implement only if needed
void pop_back()
{
if (!empty())
{
// Don't remove the sentinel
remove_at(m_tail->prev);
}
}
void pop_front()
{
if (!empty())
{
remove_at(m_head);
}
}
void remove(const T& value)
{
iterator iter = begin();
while (iter != end())
{
iterator remove = iter++;
if (*remove == value)
{
remove_at(remove.m_cur_item);
}
}
}
void clear()
{
while (!empty())
{
pop_back();
}
}
private:
iterator insert_before(LinkListElement* existing, const T& payload)
{
// Allocate memory and save the element
LinkListElement* new_elem = new LinkListElement;
// For classes types (not pointer to object) this should invoke copy constructor
new_elem->payload = payload;
new_elem->prev = existing->prev;
new_elem->next = existing;
existing->prev = new_elem;
++m_count;
if (existing == m_head)
{
m_head = new_elem;
}
return iterator(new_elem);
}
iterator remove_at(LinkListElement* to_remove)
{
// Allocate memory and save the element
LinkListElement* prev = to_remove->prev;
LinkListElement* next = to_remove->next;
prev->next = next;
next->prev = prev;
--m_count;
if (to_remove == m_head)
{
m_head = next;
}
delete to_remove;
return iterator(prev);
}
LinkListElement* m_head;
LinkListElement* m_tail;
uint32_t m_count;
};
template <typename T> T list<T>::iterator::dummy;
#endif
You code has all kinds of features and checks that the STL doesn't have. So it makes sense that you would wind up with more code.
Yes, the STL has lots of features your code doesn't have. But you aren't using any of them, so they don't show up in your code footprint. The STL is designed using templates so that you don't pay for what you don't use.
It's unlikely you can improve on the STL. If you need to add features, add them. You don't need to reinvent the wheel.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments