Pourquoi cette implémentation de liste prend-elle plus d'espace que la liste stl?

Question

J'utilise IAR comme compilateur pour un projet incorporé. J'essaie d'introduire des modèles pour des types de base comme la liste, mais chaque objet de liste STL créé augmente la taille du code d'environ 200 octets par rapport à notre implémentation de style C actuelle. J'ai essayé d'implémenter moi-même une petite partie de la liste STL en espérant obtenir une empreinte de code plus petite, mais j'ai fini par être plus lourd que la liste STL complète. Est-ce que je fais quelque chose d'horriblement mauvais dans mon utilisation des modèles?

Merci

post-scriptum Notez que le code n'est pas testé et qu'il peut contenir des 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 

Answer 1

Votre code a toutes sortes de fonctionnalités et de contrôles que la STL n'a pas. Il est donc logique que vous vous retrouvez avec plus de code.

Oui, la STL a beaucoup de fonctionnalités que votre code n'a pas. Mais vous n'utilisez aucun d'entre eux, ils n'apparaissent donc pas dans votre empreinte de code. Le STL est conçu en utilisant des modèles afin que vous ne payez pas pour ce que vous n'utilisez pas.

Il est peu probable que vous puissiez améliorer le STL. Si vous devez ajouter des fonctionnalités, ajoutez-les. Vous n'avez pas besoin de réinventer la roue.