이 목록 구현이 stl list보다 많은 공간을 차지하는 이유는 무엇입니까?

Question

임베디드 프로젝트 용 컴파일러로 IAR을 사용하고 있습니다. 목록과 같은 기본 유형에 대한 템플릿을 소개하려고하지만 각 STL 목록 객체는 현재 C 스타일 구현에 비해 약 200 바이트만큼 코드 크기가 증가합니다. 필자는 작은 코드 공간을 얻기를 희망하는 STL 목록의 일부를 구현하려고 시도했지만 전체 STL 목록보다 무거웠습니다. 서식 파일을 잘못 사용하여 무언가 잘못하고 있습니까?

감사합니다.

P. 이 코드는 테스트되지 않았으므로 용을 포함 할 수 있습니다.

#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

코드에는 모든 종류의 기능이 있으며 STL에없는 기능이 있습니다. 따라서 더 많은 코드로 마무리 할 수 ​​있습니다.

예, STL에는 코드에없는 많은 기능이 있습니다. 그러나 이들 중 어느 것도 사용하지 않으므로 코드 발자국에 나타나지 않습니다. STL은 템플릿을 사용하여 사용하지 않는 것에 대해 비용을 지불하지 않도록 설계되었습니다.

STL에서 개선 할 수있는 가능성은 거의 없습니다. 기능을 추가해야하는 경우 추가하십시오. 바퀴를 재발 명할 필요가 없습니다.