Написать метод emplace для контейнера list

328

17 сентября 2017, 01:07

Не знаю как написать метод emplace для листа. Вот мой лист:

#pragma once
#include <iostream>
#include <iterator>
#include <algorithm>
#include <initializer_list>
#include <memory>
#include <utility>

using std::ostream;
using std::istream;
template <class T>
class LinkedList
{
protected:
    struct Node
    {
        T _value;
        Node *_pNext;
        Node *_pPrev;
        Node(T val) : _value(val), _pNext(NULL), _pPrev(NULL) {};
        Node() : _value(0), _pNext(NULL), _pPrev(NULL) {};

        T GetValue()
        {
            return _value;
        }
    };
private:
  Node *_pHead;
    Node *_pTail;
    int _size;  
public: 
    LinkedList() : _pHead(NULL), _pTail(NULL), _size(0) {}
    LinkedList(const LinkedList<T>& other) : _pHead(NULL), _pTail(NULL), _size(0)
    {
        if (this == &other)
        {
            return;
        }
        for (auto it = other.begin(); it != other.end(); it++)
        {
            AddFirst(*it);
        }
    }

    LinkedList(std::initializer_list<T> _list)
    {
        for (auto it = _list.begin(); it != _list.end(); it++)
        {
            AddLast((*it));
        }
    }
    LinkedList(LinkedList<T>&& other) : _pHead(NULL), _pTail(NULL), _size(0)
    {
        _pHead = other._pHead;
        _pTail = other._pTail;
        _size = other._size;
        other._pHead = NULL;
        other._pTail = NULL;
        other._size = 0;
        std::cout << "create move LinkedList" << std::endl;
    }

   bool operator==(const LinkedList &other) const
    {
        Node* current = _pHead;
        Node* other_cur = other._pHead;
        if (_size != other.GetSize())
        {
            return false;
        }
        if (_size == 0 && other._size == 0)
        {
            return true;
        }
        while (current->_pNext != 0)
        {
            if (current->_value != other_cur->_value)
            {
                return false;
            }
            current = current->_pNext;
            other_cur = other_cur->_pNext;
        }
        if (current->_value != other_cur->_value)
        {
            return false;
        }
        return true;
    }

    class iterator : public std::iterator<std::input_iterator_tag, T>
    {
        Node* _node;
    public:
        iterator(Node* temp) : _node(temp) {}
        iterator(const iterator& iter) : _node(iter._node) {}
        iterator& operator++()
        {
            _node = _node->_pNext;
            return *this;
        }
        iterator operator++(int)
        {
            iterator temp(*this);
            operator++();
            return temp;
        }
        bool operator==(const iterator& it) { return _node == it._node; }
        bool operator!=(const iterator& it) { return _node != it._node; }
        T& operator*() { return _node->_value; }
    };
    iterator begin() const { return iterator(_pHead); }
    iterator end() const { return iterator(_pTail->_pNext); }
    void AddFirst(const T val)
    {
        Node* node = new Node(val);
        Node* temp = _pHead;
        _pHead = node;
        _pHead->_pNext = temp;
        if (_size == 0)
        {
            _pTail = _pHead;
        }
        else
        {
            temp->_pPrev = _pHead;
        }
        _size++;
    }
    void AddLast(const T val)
    {
        Node* node = new Node(val);
        if (_size == 0)
        {
            _pHead = node;
        }
        else
        {
            _pTail->_pNext = node;
            node->_pPrev = _pTail;
        }
        _pTail = node;
        _size++;
    }
    void Add(const T val)
    {
        AddLast(val);
    }

    template <typename ...Args >
    void Emplace(Args && ...args)
    {       
    }
};

Буду благодарна за помощь)

Answer 1

Я бы реализовал это примерно так:

#include <utility>
#include <type_traits>
#include  <memory>
#include <iostream>
template <class T>
class List{
private: // Не используйте Protected, если точно не знаете, что он вам нужен
    struct Node
    {
      // Это для того, чтобы избежать рекурсии при удалении, и обеспечить безопасность исключений
      struct NodeDeleter{
            void operator() (Node* node){
                if(node){
                    auto nextNode = std::move(node->next_);
                    while(nextNode){
                        auto tmp = std::move(nextNode->next_);
                         // nextNode->next_ == nullptr
                        nextNode.swap(tmp);
                        delete tmp.release(); // Это для того, что бы не вызывать deleter
                    }
                    delete node;
                }
            }
        };
        std::unique_ptr<Node, NodeDeleter> next_;
        Node* prev_;
        T value_;
        template<class... Args>
        Node(Node* prev, Args&&... args) 
        : next_{nullptr}
        , prev_{prev}
        , value_{std::forward<Args>(args)...} {}
        Node(Node* prev)
        : next_{nullptr}
        , prev_{prev}
        , value_{} {}
    };
    public:
    List()
    : head_{nullptr}
    , tail_{nullptr}
    , size_{0}
    { }
    List(const List&) = delete; // Реализовать можно, но сложнее
    void swap(List& rha){
        std::swap(head_, rha.head_);
        std::swap(tail_, rha.tail_);
        std::swap(size_, rha.size_);
    }
    List(List&& in)
    : List{}{
        swap(in);
    }
    List(std::initializer_list<T> init){
        for(auto&& v: init){
            emplace_back(std::forward<decltype(v)>(v));
        }
    }
    List& operator = (const List&) = delete;
    List& operator = (List&& in){
        swap(in);
    }

    T& push_back(const T& v){
       return emplace_back(v);
    }
    template<class... Args>
    T& emplace_back(Args&&... args){
        auto node = std::make_unique<Node>(tail_, std::forward<Args>(args)...);
        if(!head_){
            head_.reset(node.release());
            tail_ = head_.get();
        } else{
            tail_->next_.reset(node.release());
            tail_ = tail_->next_.get();
        }
        ++size_;
        return *tail_;
    }
    template<class Fn>
    void for_each(Fn fn){
      for(Node* node = head_.get(); node; node = node->next_.get()){
        fn(node->value_);
      }
    }
    template<class Fn>
    void for_each(Fn fn) const{
        for(Node* node = head_.get(); node; node = node->next_.get()){
            fn(node->value_);
        }
    }
    private:
    decltype(Node::next_) head_;
    Node* tail_; 
    std::size_t size_;
};
struct test{
    int v1;
    std::unique_ptr<double> v2;
    test(test&&) = default;
    ~test(){std::cout << "\ndelete " << v1; }
};
int main(){
  List<test> list1;
  list1.emplace_back(1);
  list1.emplace_back(2, std::make_unique<double>(5.5));
  list1.emplace_back(3, std::make_unique<double>(6.5));
  auto visitor = [](auto& v){
    std::cout << "{ " << v.v1 << ", ";
    if(v.v2)
      std::cout << *v.v2;
    else
      std::cout << "nullptr";
    std::cout << " }";
  };
  std::cout<< "\n-"; list1.for_each(visitor);
  auto list2 = std::move(list1);
  std::cout<< "\n-"; list2.for_each(visitor);
  std::cout<< "\n-"; list1.for_each(visitor);
  list1 = std::move(list2);
  std::cout<< "\n-"; list1.for_each(visitor);
}