Реализовать двунаправленный список в духе списка из STL

@ForEveR · Регистрация: 24.06.2010

Author24 — интернет-сервис помощи студентам

Все-таки видимо у меня всегда останутся с этим проблемы.
Само определение скидывать не буду, я пытаюсь сделать, что-то вроде STL-ного списка.
Спросить хочу только одно.

C++

    void push_back(const T& el)
    {
        Node* tmp=new Node(el);
        if(empty())
        {
            head=tmp;
            tail=tmp;
            ++sz;
            return;
        }
        tail->next=tmp;
        tail=tmp;
        ++sz;
    }

После этого список можно прогонять только в одну сторону. С головы в хвост. В хвосте же только последний элемент и в prev ничего нет. В чем мб проблема?
Хотя вообще как я понял это для однонаправленного только катит... А вот как сделать для двунаправленного - второй день догнать не могу.

@volovzi · 13.02.2011, 02:06

Ну да, это не решение. Сейчас подумаю.

Добавлено через 10 минут
Забавно, у меня та же фигня. При этом если поставить вместо "size_t" "int", то работает.

Добавлено через 3 минуты
Ну всё ясно, это глюк языка.
В СБШ это решается хитрым способом:

C++

      template<typename _InputIterator>
        list(_InputIterator __first, _InputIterator __last,
         const allocator_type& __a = allocator_type())
        : _Base(__a)
        { 
      // Check whether it's an integral type.  If so, it's not an iterator.
      typedef typename std::__is_integer<_InputIterator>::__type _Integral;
      _M_initialize_dispatch(__first, __last, _Integral());
    }

Так что можно оставить инт и не париться.

@ForEveR · 13.02.2011, 02:07 **[ТС]**

volovzi, Ну это тоже не особо решение. Так и отрицательный размер задать можно. Конечно, можно контролировать, но тоже не весело... Первый раз такое вижу. При реализации вектора - этого не было.
Ого. Вот так круто. Спасибо) Попробую.

@volovzi · 13.02.2011, 02:14

ForEveR, не волнуйся, если стд::листу задать отрицательный размер, то он будет точно так же обрабатываться.
Так что на данном этапе я бы забил на лишние сложности и оставил инт.

@ForEveR · 13.02.2011, 11:51 **[ТС]**

Ну вот пока сырой конечно, но реализовано почти все и все проверено. Сырой, так как нету обработки ошибок (буду делать позже), не понимаю как сделать sort. Собственно по сути все) Можно конечно пойти хитрым путем, вкинуть в вектор, отсортировать - вкинуть обратно в список. Но кажись это жульничество. + код не комментирован, функции разбросаны кто где, оформление хромает. Код бросаю под кат.
И с unique(predicate) что-то странное творится. Я не могу найти этому объяснение. При unique сравниваются на равенство - работает как надо. При unique(pred) с предикатом сравнивания на равенство - удаляется лишнее число.

List<T>

C++

/*TODO
list::merge
list::sort
list::unique(pred)
Привести в порядок код.
Написать комментарии.
*/
 
#include <iostream>
#include <algorithm>
#include <utility>
#include <list>
#include <numeric>
#include <vector>
#include <functional>
 
struct bidirectional_iterator_tag:public std::forward_iterator_tag
{
};
 
template<class T>
class List
{
public:
    class Iterator;
    class Const_Iterator;
    class Reverse_Iterator;
    class Const_Reverse_Iterator;
 
    typedef Iterator iterator;
    typedef Const_Iterator const_iterator;
    typedef Reverse_Iterator reverse_iterator;
    typedef Const_Reverse_Iterator const_reverse_iterator;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
 
    explicit List():head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
    }
    explicit List(int n, const T& value=T()):sz(0),head(new Node(T()))
    {
        head->prev=head->next=head;
        for(int i=0; i<n; ++i)
            push_back(value);
    }
    template<class iterator_>
    List(iterator_ first, iterator_ last):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        for(iterator_ beg=first; beg != last; ++beg)
            push_back(*beg);
    }
    List(const List& other):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        for(List<T>::const_iterator iter=other.begin(); iter != other.end(); ++iter)
            push_back(*iter);
    }
    ~List()
    {
        head->prev->next=0;
        delete head;
    }
    List& operator =(const List& other)
    {
        if(this == &other)
            return *this;
        clear();
        for(List<T>::const_iterator iter=other.begin(); iter != other.end(); ++iter)
            push_back(*iter);
        return *this;
    }
    iterator erase(iterator& where_)
    {
        Node* del=where_.MyNode();
        Node* res=del->next;
        del->prev->next=del->next;
        del->next->prev=del->prev;
        del->next=0;
        delete del;
        --sz;
        return iterator(res);
    }
    iterator erase(iterator first, iterator last)
    {
        for(iterator beg=first; beg != last; ++beg)
            erase(beg);
        return last;
    }
    void pop_front()
    {
        erase(begin());
    }
    void pop_back()
    {
        erase(--end());
    }
    void clear()
    {
        erase(begin(), end());
    }
    template<class iterator_>
    void assign(iterator_ first, iterator_ last)
    {
        clear();
        for(iterator_ beg=first; beg != last; ++beg)
            push_back(*beg);
    }
    void assign(int n, const T& value)
    {
        clear();
        for(int i=0; i<n; ++i)
            push_back(value);
    }
    void remove(const T& value)
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(*beg == value)
                erase(beg);
    }
    template<class Predicate>
    void remove_if(Predicate pred)
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(pred(*beg))
                erase(beg);
    }
    void resize(size_t n, const T& value=T())
    {
        if(n < sz)
        {
            for(size_t i=0; i<sz-n; ++i)
                erase(--end());
        }
        if(n > sz)
        {
            for(size_t i=0; i<sz-n; ++i)
                push_back(value);
        }
    }
    iterator insert(iterator position, const T& value)
    {
        Node* tmp=new Node(value);
        Node* current=position.MyNode();
        tmp->prev=current->prev;
        tmp->next=current;
        current->prev->next=tmp;
        current->prev=tmp;
        ++sz;
        return ++iterator(tmp);
    }
    void insert(iterator position, int n, const T& value)
    {
        for(int i=0; i<n; ++i)
            position=insert(position, value);
    }
    template<class iterator_>
    iterator insert(iterator position, iterator_ first, iterator_ last)
    {
        for(iterator_ beg=first; beg != last; ++beg)
            position=insert(position, *beg);
        return position;
    }
    void splice(iterator position, List& other)
    {
        for(iterator beg=other.begin(); beg != other.end(); ++beg)
        {
            position=insert(position, *beg);
            other.erase(beg);
        }
    }
    void splice(iterator position, List& other, iterator i)
    {
        for(iterator beg=other.begin(); beg != other.end(); ++beg)
            if(beg == i)
            {
                position=insert(position, *beg);
                other.erase(beg);
                break;
            }
    }
    void splice(iterator position, List& other, iterator first, iterator last)
    {
        for(iterator beg=first; beg != last; ++beg)
        {
            position=insert(position, *beg);
            other.erase(beg);
        }
    }
    void reverse()
    {
        iterator first=begin();
        iterator last=end();
        while(first != last)
        {
            splice(first, *this, --last);
        }
    }
    void swap(List& other)
    {
        List tmp(other);
        other.assign(begin(), end());
        assign(tmp.begin(), tmp.end());
    }
    void unique()
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(*beg == *(beg+1))
                erase(beg);
    }
    template<class BinPred>
    void unique(BinPred Pred)
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(Pred(*beg, *(beg+1)))
                erase(beg);
    }
    size_t max_size()
    {
        size_t max=size_t(-1)/sizeof(T);
        return 0 < max ? max : 1;
    }
    size_t size() const {return sz;}
    bool empty() const {return sz == 0;}
    iterator begin() {return ++iterator(head);}
    iterator end() {return iterator(head);}
    const_iterator begin() const {return ++const_iterator(head);}
    const_iterator end() const {return const_iterator(head);}
    reverse_iterator rbegin() {return ++reverse_iterator(head);}
    reverse_iterator rend() {return reverse_iterator(head);}
    const_reverse_iterator rbegin() const {return --const_reverse_iterator(head);}
    const_reverse_iterator rend() const {return const_reverse_iterator(head);}
    void push_back(const_reference el)
    {
        Node* tmp=new Node(el);
        tmp->prev=head->prev;
        tmp->next=head;
        head->prev->next=tmp;
        head->prev=tmp;
        ++sz;
    }
    void push_front(const_reference el)
    {
        Node* tmp=new Node(el);
        tmp->prev=head;
        tmp->next=head->next;
        head->next->prev=tmp;
        head->next=tmp;
        ++sz;
    }
    reference front()
    {
        return *begin();
    }
    reference back()
    {
        return *(--end());
    }
    const_reference front() const
    {
        return *begin();
    }
    const_reference back() const
    {
        return *(--end());
    }
private:
    struct Node
    {
        explicit Node(T elem_)
            :elem(elem_), next(0), prev(0)
        {
        }
        ~Node() {delete next;}
        Node* next;
        Node* prev;
        T elem;
    };
    Node* head;
    size_t sz;
};
 
template<class T> class List<T>::Const_Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
 
    Const_Iterator():curr(0), next(0), prev(0)
    {
    }
    explicit Const_Iterator(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    Const_Iterator & operator ++()
    {
        return *this=Const_Iterator(next);
    }
    Const_Iterator operator ++(int)
    {
        Const_Iterator tmp=*this;
        ++(*this);
        return tmp;
    }
    Const_Iterator& operator --()
    {
        return *this=Const_Iterator(prev);
    }
    Const_Iterator operator --(int)
    {
        Const_Iterator tmp=*this;
        --(*this);
        return tmp;
    }
    const_reference operator *() const
    {
        return curr->elem;
    }
    Const_Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            ++(*this);
        return *this;
    }
    Const_Iterator& operator -(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            --(*this);
        return *this;
    }
    Const_Iterator& operator +=(size_t idx)
    {
        return *this=*this+idx;
    }
    Const_Iterator& operator -=(size_t idx)
    {
        return *this=*this-idx;
    }
    const_pointer operator ->() const
    {
        return &curr->elem;
    }
    difference_type operator -(const Const_Iterator& other)
    {
        return curr-other.curr;
    }
    bool operator ==(const Const_Iterator& other)
    {
        return curr == other.curr;
    }
    bool operator !=(const Const_Iterator& other)
    {
        return curr != other.curr;
    }
    Node* MyNode()
    {
        return curr;
    }
private:
    Node* curr;
    Node* next;
    Node* prev;
};
 
template<class T> class List<T>::Iterator:public Const_Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
 
    Iterator():curr(0), next(0), prev(0)
    {
    }
    explicit Iterator(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    reference operator *()
    {
        return curr->elem;
    }
    Iterator& operator ++()
    {
        return *this=Iterator(next);
    }
    Iterator& operator --()
    {
        return *this=Iterator(prev);
    }
    Iterator operator ++(int)
    {
        Iterator tmp=*this;
        ++(*this);
        return tmp;
    }
    Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            ++(*this);
        return *this;
    }
    Iterator& operator -(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            --(*this);
        return *this;
    }
    Iterator& operator +=(size_t idx)
    {
        return *this=*this+idx;
    }
    Iterator& operator -=(size_t idx)
    {
        return *this=*this-idx;
    }
    pointer operator ->()
    {
        return &curr->elem;
    }
    difference_type operator -(const Iterator& other)
    {
        return curr-other.curr;
    }
    bool operator == (const Iterator& other) const 
    {
        return curr == other.curr;
    }
    bool operator != (const Iterator& other) const
    {
        return curr != other.curr;
    }
    Node* MyNode()
    {
        return curr;
    }
private:
    Node* curr;
    Node* prev;
    Node* next;
};
 
template<class T> class List<T>::Const_Reverse_Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
 
    Const_Reverse_Iterator():curr(0), next(0), prev(0)
    {
    }
    explicit Const_Reverse_Iterator(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    Const_Reverse_Iterator& operator ++()
    {
        return *this=Const_Reverse_Iterator(prev);
    }
    Const_Reverse_Iterator& operator --()
    {
        return *this=Const_Reverse_Iterator(next);
    }
    Const_Reverse_Iterator operator ++(int)
    {
        Const_Reverse_Iterator tmp=*this;
        ++(*this);
        return tmp;
    }
    Const_Reverse_Iterator operator --(int)
    {
        Const_Reverse_Iterator tmp=*this;
        --(*this);
        return tmp;
    }
    Const_Reverse_Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            ++(*this);
        return *this;
    }
    Const_Reverse_Iterator& operator -(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            --(*this);
        return *this;
    }
    Const_Reverse_Iterator& operator +=(size_t idx)
    {
        return *this=*this+idx;
    }
    Const_Reverse_Iterator& operator -=(size_t idx)
    {
        return *this=*this-idx;
    }
    const_reference operator *() const
    {
        return curr->elem;
    }
    const_pointer operator ->() const
    {
        return &curr->elem;
    }
    difference_type operator -(const Const_Reverse_Iterator& other)
    {
        return curr - other.curr;
    }
    bool operator ==(const Const_Reverse_Iterator& other)
    {
        return curr == other.curr;
    }
    bool operator !=(const Const_Reverse_Iterator& other)
    {
        return curr != other.curr;
    }
private:
    Node* curr;
    Node* next;
    Node* prev;
};
 
template<class T> class List<T>::Reverse_Iterator:
public Const_Reverse_Iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    
    Reverse_Iterator():curr(0), next(0), prev(0)
    {
    }
    explicit Reverse_Iterator(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    Reverse_Iterator& operator ++()
    {
        return *this=Reverse_Iterator(prev);
    }
    Reverse_Iterator& operator --()
    {
        return *this=Reverse_Iterator(next);
    }
    Reverse_Iterator operator ++(int)
    {
        Reverse_Iterator tmp=*this;
        ++(*this);
        return tmp;
    }
    Reverse_Iterator operator --(int)
    {
        Reverse_Iterator tmp=*this;
        --(*this);
        return tmp;
    }
    Reverse_Iterator& operator +(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            ++(*this);
        return *this;
    }
    Reverse_Iterator& operator -(size_t idx)
    {
        for(size_t i=0; i<idx; ++i)
            --(*this);
        return *this;
    }
    Reverse_Iterator& operator +=(size_t idx)
    {
        return *this=*this+idx;
    }
    Reverse_Iterator& operator -=(size_t idx)
    {
        return *this=*this-idx;
    }
    reference operator *()
    {
        return curr->elem;
    }
    pointer operator ->()
    {
        return &curr->elem;
    }
    difference_type operator -(const Reverse_Iterator& other)
    {
        return curr - other.curr;
    }
    bool operator ==(const Reverse_Iterator& other)
    {
        return curr == other.curr;
    }
    bool operator !=(const Reverse_Iterator & other)
    {
        return curr != other.curr;
    }
private:
    Node* curr;
    Node* next;
    Node* prev;
};

Добавлено через 6 часов 26 минут
Соответственно, я буду рад, если кто-то посмотрит, укажет на недочеты. Подскажет как организовать оставшиеся функции (ну sort к примеру... писать быструю сортировку или сортировку как std::sort вообще как-то желания ноль)...

@volovzi · 13.02.2011, 14:07

Что увидел при первом просмотре:

Можно сделать отдельную функцию для копирования, чтобы не повторять два раза один и тот же цикл в конструкторе копирования о операторе присваивания.
В функции «erase(iterator &)» не нужна ссылка.
Функцию «erase(iterator, iterator)», мне кажется, можно усовершенстовать: не удалять элементы по одному, а переприсвоить соответствующие указатели на крайних узлах и удалить ненужные узлы всем скопом. Правда, всё равно придётся посчитать расстояние между итераторами, но всё равно должно быть побыстрее.
Функция «swap()» должна обменивать только указатели на корневые узлы и размеры списков, т.е. работать за константное время.
Итератор списка в СБШ не умеет продвигаться более, чем на одну позицию в каждую сторону, т.е. не имеет арифметических операторов, кроме ++ и --.
В функции «reverse_iterator rbegin()» опечатка: должно быть --.
И, кстати, можно использовать std::reverse_iterator.

@ForEveR · 13.02.2011, 14:27 **[ТС]**

volovzi, опечатка в const_reverse_iterator rbegin() а не в reverse_iterator rbegin(), проверял вывод через copy на reverse.
Остальное - посмотрю завтра. Спасибо

@ForEveR · 14.02.2011, 19:14 **[ТС]**

volovzi,
1) Согласен
2) Согласен
3) Можно... Но я ведь не собираюсь моделировать полностью работу стандартного списка... Я вообще не знаю, зачем это делаю... Наверное, чтобы понять как это устроено. Если менять, то как по сути должно быть? Алгоритм действий я имею ввиду.
4) Аналогично, немного не понял как делать то, что ты предложил.
5) Подозревал. Перестарался. Но почему-то мне кажется, что так удобнее... Стоит убрать?
7) Можно было... Но в таком случае можно было использовать и iterator/const_iterator. Сделать просто typedef типа typedef std::list<T>::iterator iterator...

Ну и плюс к тому, копии настоящего все равно не получится, ибо с аллокатором парится не очень хочется. Для вектора он реализовался легко, можно его и взять, но там в списке какие-то хитрости с rebind используются. А что ты думаешь насчет сортировки? Как лучше делать? (алгоритм)

@volovzi · 14.02.2011, 19:24

3. В стандартном, как раз, как у тебя

. Просто мне кажется, что это нерационально.
4. См. пример.
5. Можно и оставить, просто если ты будешь передавать список куда-то в алгоритм, который не предназначен для списка, то он может работать неопределённое время.

Вот мой пример. Erase(iter, iter) у меня нестандартный, а вот swap и стандартный, и правильный.

list<T>

C++

template <typename Value>
class list {
 
// ---- Определения -------------------------------------------------------------------------------
 
public:
    typedef Value value_type;
 
// ---- Узел списка -------------------------------------------------------------------------------
 
private:
    struct node {
        explicit node (const value_type & value) : value(value), next(0), previous(0) {}
        ~node () { delete next; }
    
        value_type value;
        
        node * next;
        node * previous;
    };
 
// ---- Итераторы ---------------------------------------------------------------------------------
 
public:
    struct iterator {
        iterator () : current(0), next(0), previous(0) {}
        explicit iterator (node * n) : current(n), next(n->next), previous(n->previous) {}
        
        value_type & operator * () { return current->value; }
        value_type * const operator -> () { return &current->value; }
        
        iterator & operator ++ () { return *this = iterator(next); }
        iterator & operator -- () { return *this = iterator(previous); }
        
        iterator operator ++ (int) {
            iterator result = *this;
            
            *this = iterator(next);
            
            return result;
        }
        
        iterator operator -- (int) {
            iterator result = *this;
            
            *this = iterator(previous);
            
            return result;
        }
        
        bool operator == (const iterator & i) const { return current == i.current; }
        bool operator != (const iterator & i) const { return current != i.current; }
    
        node * current;
        node * next;
        node * previous;
    };
    
    struct const_iterator {
        const_iterator () : current(0), next(0), previous(0) {}
        explicit const_iterator (node * n) : current(n), next(n->next), previous(n->previous) {}
        
        const value_type & operator * () const { return current->value; }
        const value_type * const operator -> () const { return &current->value; }
        
        const_iterator & operator ++ () { return *this = const_iterator(next); }
        const_iterator & operator -- () { return *this = const_iterator(previous); }
        
        const_iterator operator ++ (int) {
            const_iterator result = *this;
            
            *this = const_iterator(next);
            
            return result;
        }
        
        const_iterator operator -- (int) {
            const_iterator result = *this;
            
            *this = const_iterator(previous);
            
            return result;
        }
        
        bool operator == (const const_iterator & i) const { return current == i.current; }
        bool operator != (const const_iterator & i) const { return current != i.current; }
    
        node * current;
        node * next;
        node * previous;
    };
 
// ---- Создание и уничтожение --------------------------------------------------------------------
    
public:
    list () : m_last(new node(value_type())), m_size(0) { m_last->previous = m_last->next = m_last; }
    
    explicit list (int size, const value_type & value = value_type()) : m_last(new node(value_type())), m_size(0) {
        m_last->previous = m_last->next = m_last;
        
        for (size_t i = 0; i < size; ++i) push_back(value);
    }
    
    template <typename InputIterator>
    list (InputIterator first, InputIterator last) : m_last(new node(value_type())), m_size(0) {
        m_last->previous = m_last->next = m_last;
        
        while (first != last) push_back(*first++);
    }
 
    ~list () {
        m_last->previous->next = 0;
        
        delete m_last;
    }
 
// ---- Модификации -------------------------------------------------------------------------------
 
public:
    iterator insert (iterator position, const value_type & value) {
        node * new_node = new node(value);
        node * current_node = position.current;
        
        new_node->next = current_node->next;
        new_node->previous = current_node;
        
        current_node->next->previous = new_node;
        current_node->next = new_node;
        
        ++m_size;
        
        return iterator(new_node);
    }
    
    iterator erase (iterator position) {
        node * node_to_delete = position.current;
        
        node_to_delete->previous->next = node_to_delete->next;
        node_to_delete->next->previous = node_to_delete->previous;
        
        node * result = node_to_delete->next;
        
        node_to_delete->next = 0;
        delete node_to_delete;
        
        --m_size;
        
        return iterator(result);
    }
    
    iterator erase (iterator first, iterator last) {
        for (iterator i = first; i != last; ++i) --m_size;
    
        node * to_delete = first.current;
        node * not_to_delete = last.current;
        
        to_delete->previous->next = not_to_delete;
        
        not_to_delete->previous->next = 0;
        not_to_delete->previous = to_delete->previous;
        
        delete to_delete;
        
        return iterator(not_to_delete);
    }
    
    void push_back (const value_type & value) { insert(--end(), value); }
    void push_front (const value_type & value) { insert(end(), value); }
    
    void pop_back () { erase(--end()); }
    void pop_front () { erase(++end()); }
    
    void swap (list & l) {
        std::swap(m_last, l.m_last);
        std::swap(m_size, l.m_size);
    }
    
    void clear () {
        m_last->previous->next = 0;
        delete m_last->next;
        
        m_last->previous = m_last->next = m_last;
        m_size = 0;
    }
    
// ---- Доступ к элементам ------------------------------------------------------------------------
 
public:
    value_type & front () { return m_last->next->value; }
    const value_type & front () const { return m_last->next->value; }
    
    value_type & back () { return m_last->previous->value; }
    const value_type & back () const { return m_last->previous->value; }
 
// ---- Последовательный доступ -------------------------------------------------------------------
 
public:
    iterator begin () { return ++iterator(m_last); }
    const_iterator begin () const { return ++const_iterator(m_last); }
    
    iterator end () { return iterator(m_last); }
    const_iterator end () const { return const_iterator(m_last); }
 
// ---- Информация --------------------------------------------------------------------------------
    
public:
    bool is_empty () const { return m_size == 0; }
    int size () const { return m_size; }
 
// ---- Переменные --------------------------------------------------------------------------------
    
private:
    node * m_last;
    
    int m_size;
};

@ForEveR · 14.02.2011, 19:28 **[ТС]**

volovzi, Ммм.. Да. Интересно на тему erase. Своп жутко понравился)

@besh]<a · 14.02.2011, 21:43

Можете подсказать, в односвязном списке обязательно должно быть 2 указателя, на начальный и конечный элементы списка, или можно обойтись одним, только на начальный элемент?

@ForEveR · 15.02.2011, 00:58 **[ТС]**

Добавил некоторую обработку ошибок. Не знаю правда как обрабатывать выход из диапазона итератора...
Пожаления/дополнения/советы приветствуются.
На merge/sort стоят заглушки, которые я не думаю, что буду переделывать. Собственно все по-сути.

Список

C++

/*TODO
*/
 
#include <iostream>
#include <algorithm>
#include <utility>
#include <list>
#include <numeric>
#include <vector>
#include <functional>
 
struct bidirectional_iterator_tag:public std::forward_iterator_tag
{
};
 
template<class T>
class List
{
    //Declaration of supplementarry classes
    class Iterator;
    class Const_Iterator;
    class Reverse_Iterator;
    class Const_Reverse_Iterator;
 
public:
    //Declaration of types
    typedef Iterator iterator;
    typedef Const_Iterator const_iterator;
    typedef Reverse_Iterator reverse_iterator;
    typedef Const_Reverse_Iterator const_reverse_iterator;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    
    //Constructors
    explicit List():head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
    }
 
    explicit List(int n, const T& value=T()):sz(0),head(new Node(T()))
    {
        head->prev=head->next=head;
        for(int i=0; i<n; ++i)
            push_back(value);
    }
 
    template<class iterator_>
    List(iterator_ first, iterator_ last):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        Copy_(first, last);
    }
 
    List(const List& other):head(new Node(T())), sz(0)
    {
        head->prev=head->next=head;
        Copy_(other);
    }
    
    //Destructor
    ~List()
    {
        head->prev->next=0;
        delete head;
    }
 
    //Iteraton functions
    iterator begin() { return ++iterator(head); }
 
    iterator end() { return iterator(head); }
 
    const_iterator begin() const { return ++const_iterator(head); }
 
    const_iterator end() const { return const_iterator(head); }
 
    reverse_iterator rbegin() { return ++reverse_iterator(head); }
 
    reverse_iterator rend() { return reverse_iterator(head); }
 
    const_reverse_iterator rbegin() const { return ++const_reverse_iterator(head); }
 
    const_reverse_iterator rend() const { return const_reverse_iterator(head); }
 
    //Operators
    List& operator =(const List& other)
    {
        if(this == &other)
            return *this;
        clear();
        Copy_(other);
        return *this;
    }
 
    //Functions
    size_type size() const {return sz;}
 
    bool empty() const {return sz == 0;}
 
    void push_back(const_reference el) { insert(end(), el); }
 
    void push_front(const_reference el) { insert(begin(), el); }
 
    reference front() 
    {
        if(empty())
            Empty_Error();
        return *begin(); 
    }
 
    reference back() 
    {
        if(empty())
            Empty_Error();
        return *(--end()); 
    }
 
    const_reference front() const 
    {
        if(empty())
            Empty_Error();
        return *begin(); 
    }
 
    const_reference back() const 
    { 
        if(empty())
            Empty_Error();
        return *(--end()); 
    }
 
    void pop_front() 
    {
        if(empty())
            Empty_Error();
        erase(begin()); 
    }
 
    void pop_back() 
    {
        if(empty())
            Empty_Error();
        erase(--end()); 
    }
 
    void clear() 
    {
        head->prev->next=0;
        delete head->next;
        head->prev=head->next=head;
        sz=0;
    }
 
    iterator erase(iterator where_)
    {
        if(empty())
            Empty_Error();
        Node* del=where_.MyNode();
        Node* res=del->next;
        del->prev->next=del->next;
        del->next->prev=del->prev;
        del->next=0;
        delete del;
        --sz;
        return iterator(res);
    }
 
    iterator insert(iterator position, const T& value)
    {
        Node* tmp=new Node(value);
        Node* current=position.MyNode();
        tmp->prev=current->prev;
        tmp->next=current;
        current->prev->next=tmp;
        current->prev=tmp;
        ++sz;
        return ++iterator(tmp);
    }
    
    iterator erase(iterator first, iterator last)
    {
        for(iterator beg=first; beg != last; ++beg)
            erase(beg);
        return last;
    }
    
    void insert(iterator position, int n, const T& value)
    {
        for(int i=0; i<n; ++i)
            position=insert(position, value);
    }
 
    template<class iterator_>
    iterator insert(iterator position, iterator_ first, iterator_ last)
    {
        for(iterator_ beg=first; beg != last; ++beg)
            position=insert(position, *beg);
        return position;
    }
 
    template<class iterator_>
    void assign(iterator_ first, iterator_ last)
    {
        clear();
        Copy_(first, last);
    }
 
    void assign(int n, const T& value)
    {
        clear();
        for(int i=0; i<n; ++i)
            push_back(value);
    }
 
    void remove(const T& value)
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(*beg == value)
                erase(beg);
    }
 
    template<class Predicate>
    void remove_if(Predicate pred)
    {
        for(iterator beg=begin(); beg != end(); ++beg)
            if(pred(*beg))
                erase(beg);
    }
 
    void resize(size_t n, const T& value=T())
    {
        if(size < 0)
            Size_Error();
        if(n < sz)
        {
            for(size_t i=0; i<sz-n; ++i)
                erase(--end());
        }
        if(n > sz)
        {
            for(size_t i=0; i<sz-n; ++i)
                push_back(value);
        }
    }
 
    void splice(iterator position, List& other)
    {
        for(iterator beg=other.begin(); beg != other.end(); ++beg)
        {
            position=insert(position, *beg);
            other.erase(beg);
        }
    }
 
    void splice(iterator position, List& other, iterator i)
    {
        for(iterator beg=other.begin(); beg != other.end(); ++beg)
            if(beg == i)
            {
                position=insert(position, *beg);
                other.erase(beg);
                break;
            }
    }
 
    void splice(iterator position, List& other, iterator first, iterator last)
    {
        for(iterator beg=first; beg != last; ++beg)
        {
            position=insert(position, *beg);
            other.erase(beg);
        }
    }
 
    void reverse()
    {
        iterator first=begin();
        iterator last=end();
        while(first != last)
        {
            splice(first, *this, --last);
        }
    }
 
    void swap(List& other)
    {
        std::swap(head, other.head);
        std::swap(sz, other.sz);
    }
 
    void unique()
    {
        iterator first=begin();
        iterator after=first;
        for(++after; after != end(); )
        {
            if(*first == *after)
                after=erase(after);
            else
                first=after++;
        }
    }
 
    template<class BinPred>
    void unique(BinPred Pred)
    {
        iterator first=begin();
        iterator after=first;
        for(++after; after != end(); )
        {
            if(Pred(*first, *after))
                after=erase(after);
            else
                first=after++;
        }
    }
 
    size_t max_size()
    {
        size_t max=size_t(-1)/sizeof(T);
        return 0 < max ? max : 1;
    }
    
    void sort()
    {
        std::vector<int> vec(begin(), end());
        std::sort(vec.begin(), vec.end());
        assign(vec.begin(), vec.end());
    }
    
    template<class Compare>
    void sort(Compare comp)
    {
        std::vector<int> vec(begin(), end());
        std::sort(vec.begin(), vec.end(), comp);
        assign(vec.begin(), vec.end());
    }
 
    void merge(const List& other)
    {
        insert(begin(), other.begin(), other.end());
        sort();
    }
 
    template<class Compare>
    void merge(const List& other, Compare comp)
    {
        insert(begin(), other.begin(), other.end());
        sort(comp);
    }
 
private:
    //Node of list
    struct Node
    {
        explicit Node(T elem_)
            :elem(elem_), next(0), prev(0)
        {
        }
 
        ~Node() {delete next;}
        Node* next;
        Node* prev;
        T elem;
    };
    //Head node
    Node* head;
    size_type sz;
 
    void Copy_(const List& other)
    {
        for(List::const_iterator iter=begin(); iter != end(); ++iter)
            push_back(*iter);
    }
 
    template<class iterator_>
    void Copy_(iterator_ first, iterator_ second)
    {
        for(iterator_ iter=first; iter != second; ++iter)
            push_back(*iter);
    }
 
    void Empty_Error()
    {
#ifdef _DEBUG
        std::_DEBUG_ERROR("List is empty");
#else
        terminate();
#endif
    }
 
    void Size_Error()
    {
#ifdef _DEBUG
        std::_DEBUG_ERROR("Size if negative");
#else
        terminate();
#endif
    }
 
};
 
template<class T> class List<T>::Const_Iterator
{
public:
    //Declaration of types
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef Const_Iterator My_Iter;
    
    //Constructor
    My_Iter():curr(0), next(0), prev(0)
    {
    }
 
    explicit My_Iter(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    
    //Operators
    My_Iter& operator ++()
    {
        return *this=My_Iter(next);
    }
 
    My_Iter operator ++(int)
    {
        My_Iter tmp=*this;
        ++(*this);
        return tmp;
    }
 
    My_Iter& operator --()
    {
        return *this=My_Iter(prev);
    }
 
    My_Iter operator --(int)
    {
        My_Iter tmp=*this;
        --(*this);
        return tmp;
    }
    
    //Accessors
    Node* MyNode() const
    {
        return curr;
    }
 
    const_reference operator *() const
    {
        return curr->elem;
    }
 
    const_pointer operator ->() const
    {
        return &curr->elem;
    }
    
    bool operator ==(const My_Iter& other)
    {
        return curr == other.curr;
    }
 
    bool operator !=(const My_Iter& other)
    {
        return curr != other.curr;
    }
    
private:
 
    Node* curr;
    Node* next;
    Node* prev;
};
 
template<class T> class List<T>::Iterator:public Const_Iterator
{
public:
 
    //Declaration of types
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef Iterator My_Iter;
 
    //Constructor
    My_Iter():curr(0), next(0), prev(0)
    {
    }
 
    explicit My_Iter(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    
    //Accessors
    reference operator *()
    {
        return curr->elem;
    }
 
    Node* MyNode()
    {
        return curr;
    }
 
    pointer operator ->()
    {
        return &curr->elem;
    }
 
    //Operators
    My_Iter& operator ++()
    {
        return *this=My_Iter(next);
    }
 
    My_Iter& operator --()
    {
        return *this=My_Iter(prev);
    }
 
    My_Iter operator ++(int)
    {
        My_Iter tmp=*this;
        ++(*this);
        return tmp;
    }
    
    My_Iter operator --(int)
    {
        My_Iter tmp=*this;
        --(*this);
        return tmp;
    }
 
    bool operator == (const My_Iter& other) const 
    {
        return curr == other.curr;
    }
 
    bool operator != (const My_Iter& other) const
    {
        return curr != other.curr;
    }
 
private:
 
    Node* curr;
    Node* prev;
    Node* next;
};
 
template<class T> class List<T>::Const_Reverse_Iterator
{
public:
 
    //Declaration of types
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* const_pointer;
    typedef const T& const_reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef Const_Reverse_Iterator My_Iter;
    
    //Constructor
    My_Iter():curr(0), next(0), prev(0)
    {
    }
 
    explicit My_Iter(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    
    //Accessors
    Node* MyNode() const
    {
        return curr;
    }
 
    const_reference operator *() const
    {
        return curr->elem;
    }
 
    const_pointer operator ->() const
    {
        return &curr->elem;
    }
 
    //Operators
    My_Iter& operator ++()
    {
        return *this=My_Iter(prev);
    }
 
    My_Iter& operator --()
    {
        return *this=My_Iter(next);
    }
 
    My_Iter operator ++(int)
    {
        My_Iter tmp=*this;
        ++(*this);
        return tmp;
    }
 
    My_Iter operator --(int)
    {
        My_Iter tmp=*this;
        --(*this);
        return tmp;
    }
 
    bool operator ==(const Const_Reverse_Iterator& other)
    {
        return curr == other.curr;
    }
    bool operator !=(const Const_Reverse_Iterator& other)
    {
        return curr != other.curr;
    }
private:
 
    Node* curr;
    Node* next;
    Node* prev;
};
 
template<class T> class List<T>::Reverse_Iterator:
public Const_Reverse_Iterator
{
public:
 
    //Declaration of types
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef ptrdiff_t difference_type;
    typedef size_t size_type;
    typedef Reverse_Iterator My_Iter;
    
    //Constructors
    My_Iter():curr(0), next(0), prev(0)
    {
    }
 
    explicit My_Iter(Node* curr_):curr(curr_), next(curr_->next), prev(curr_->prev)
    {
    }
    
    //Accessors
    Node* MyNode()
    {
        return curr;
    }
    reference operator *()
    {
        return curr->elem;
    }
 
    pointer operator ->()
    {
        return &curr->elem;
    }
 
    //Operators
    My_Iter& operator ++()
    {
        return *this=My_Iter(prev);
    }
 
    My_Iter& operator --()
    {
        return *this=My_Iter(next);
    }
 
    My_Iter operator ++(int)
    {
        My_Iter tmp=*this;
        ++(*this);
        return tmp;
    }
 
    My_Iter operator --(int)
    {
        My_Iter tmp=*this;
        --(*this);
        return tmp;
    }
 
    bool operator ==(const Reverse_Iterator& other)
    {
        return curr == other.curr;
    }
 
    bool operator !=(const Reverse_Iterator & other)
    {
        return curr != other.curr;
    }
 
private:
 
    Node* curr;
    Node* next;
    Node* prev;
};

@volovzi · 15.02.2011, 01:05

Универсальной сортировкой при помощи итераторов могу поделиться.

C++

template <typename Iterator>
void quick_sort (Iterator first, Iterator last) {
    Iterator base = first;
    Iterator new_last = last;
        
    if (first != last && first++ != --last) {       
        while (first != last) {
            while (first != last && *first <= *base) ++first;
            while (first != last && *last >= *base) --last;
            
            if (first != last) std::swap(*first, *last);
        }
        
        if (*base > *first) std::swap(*base, *first);
            
        quick_sort(base, first);
        quick_sort(first, new_last);
    }
}

А вот «merge» у тебя неправильно работает. Второй список не просто копируется в первый, а ещё и очищается.

@ForEveR · 15.02.2011, 01:12 **[ТС]**

volovzi, Оу. Про очищение не прочитал что-то.
clear() то вставить без проблем. Но вроде как это нечестно. Я верно понимаю?)

@volovzi · 15.02.2011, 01:21

ForEveR, не знаю, в исходниках эта функция спрятана. Но лично я бы не копировал, а встроил второй список в первый тем же способом, которым предлагал делать insert(iterator, iterator), т.е переприсвоил соответствующие указатели без физического переноса узлов.

Кстати, в этом случае не надо считать количество элементов, т.к. их число явно известно, т.е. перенос можно осуществить за О(1). Ну а от сортировки уже никуда не денешься...

@ForEveR · 15.02.2011, 19:12 **[ТС]**

volovzi, Остальное-то все относительно нормально кроме sort/merge?

@volovzi · 15.02.2011, 20:46

ForEveR, всегда можно найти, что улучшить

.
Например, в присвоении я бы не делал проверку на равенство. Ответственность за неё должна лежать на пользователе.
То же самое — проверка в функциях «back()» и «front()». Это пользователь должен проверять, есть ли что-нибудь в списке.
Аналогично и в функции «resize(size_t, const T &)» я бы не стал делать проверку на положительность размера.
Но если уж ты обрабатываешь ошибки и не кидаешь исключение, то тогда нельзя завершать программу (кстати, что такое «terminate»?), а надо сообщить об ошибке и продолжить работу.

@ForEveR · 15.02.2011, 22:11 **[ТС]**

volovzi, terminate() вызов завершения программы. А искл я кидаю впринципе. _DEBUG_ERROR(msg) он пишет ошибку прямо в окне. Не в консоли пишет, а при выводе окна о том, что ошибка программа завершена из-за ошибки - пишет это сообщение... а terminate() это то, что происходит после runtime_error по сути.

На равенство... Хм... Просто привык, чтобы это было.
back/front по стандарту контролируются итератором насколько я понимаю.
А в resize проверка из-за типа int, но наверное тоже не особо нужна

@bigredcat · 15.04.2011, 18:37

Вот интересовался, смотрел исключительно реализации итераторов.
То как это сделано в сообщении #31, не вижу особого смысла в наследовании:

C++

1 2	template<class T> class List<T>::Reverse_Iterator : public Const_Reverse_Iterator template<class T> class List<T>::Iterator : public Const_Iterator

Вроде бы все поля и функции переопределяются заново, что на мой взгляд не есть хорошо. Стоило бы поля оставить только в базовом классе. И, по-моему, одного поля было бы вполне достаточно. А еще я бы функцию Node* MyNode() const в базовом классе сделал виртуальной и возвращающей конст. указатель (если она вообще там требуется).

C++

1	virtual const Node* MyNode() const

@ForEveR · 15.04.2011, 19:56 **[ТС]**

bigredcat, Загляните в реализацию STL на досуге.

@bigredcat · 16.04.2011, 06:15

ForEveR, так в первую очередь туда и заглядывал. Интересовался, как другие этот огород городят. Но у вас практически тоже самое.

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	13.02.2011, 02:14	23
	ForEveR, не волнуйся, если стд::листу задать отрицательный размер, то он будет точно так же обрабатываться. Так что на данном этапе я бы забил на лишние сложности и оставил инт. 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	13.02.2011, 14:07	25
	Что увидел при первом просмотре: Можно сделать отдельную функцию для копирования, чтобы не повторять два раза один и тот же цикл в конструкторе копирования о операторе присваивания. В функции «erase(iterator &)» не нужна ссылка. Функцию «erase(iterator, iterator)», мне кажется, можно усовершенстовать: не удалять элементы по одному, а переприсвоить соответствующие указатели на крайних узлах и удалить ненужные узлы всем скопом. Правда, всё равно придётся посчитать расстояние между итераторами, но всё равно должно быть побыстрее. Функция «swap()» должна обменивать только указатели на корневые узлы и размеры списков, т.е. работать за константное время. Итератор списка в СБШ не умеет продвигаться более, чем на одну позицию в каждую сторону, т.е. не имеет арифметических операторов, кроме ++ и --. В функции «reverse_iterator rbegin()» опечатка: должно быть --. И, кстати, можно использовать std::reverse_iterator. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	14.02.2011, 19:28 [ТС]	29
	volovzi, Ммм.. Да. Интересно на тему erase. Своп жутко понравился) 0

@besh]<a 13 / 11 / 1 Регистрация: 02.11.2009 Сообщений: 194
	14.02.2011, 21:43	30
	Можете подсказать, в односвязном списке обязательно должно быть 2 указателя, на начальный и конечный элементы списка, или можно обойтись одним, только на начальный элемент? 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	15.02.2011, 01:12 [ТС]	33
	volovzi, Оу. Про очищение не прочитал что-то. clear() то вставить без проблем. Но вроде как это нечестно. Я верно понимаю?) 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.02.2011, 02:07 [ТС]	22
	volovzi, Ну это тоже не особо решение. Так и отрицательный размер задать можно. Конечно, можно контролировать, но тоже не весело... Первый раз такое вижу. При реализации вектора - этого не было. Ого. Вот так круто. Спасибо) Попробую. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.02.2011, 14:27 [ТС]	26
	volovzi, опечатка в const_reverse_iterator rbegin() а не в reverse_iterator rbegin(), проверял вывод через copy на reverse. Остальное - посмотрю завтра. Спасибо 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	14.02.2011, 19:14 [ТС]	27
	volovzi, 1) Согласен 2) Согласен 3) Можно... Но я ведь не собираюсь моделировать полностью работу стандартного списка... Я вообще не знаю, зачем это делаю... Наверное, чтобы понять как это устроено. Если менять, то как по сути должно быть? Алгоритм действий я имею ввиду. 4) Аналогично, немного не понял как делать то, что ты предложил. 5) Подозревал. Перестарался. Но почему-то мне кажется, что так удобнее... Стоит убрать? 7) Можно было... Но в таком случае можно было использовать и iterator/const_iterator. Сделать просто typedef типа typedef std::list<T>::iterator iterator... Ну и плюс к тому, копии настоящего все равно не получится, ибо с аллокатором парится не очень хочется. Для вектора он реализовался легко, можно его и взять, но там в списке какие-то хитрости с rebind используются. А что ты думаешь насчет сортировки? Как лучше делать? (алгоритм) 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	15.02.2011, 01:21	34
	ForEveR, не знаю, в исходниках эта функция спрятана. Но лично я бы не копировал, а встроил второй список в первый тем же способом, которым предлагал делать insert(iterator, iterator), т.е переприсвоил соответствующие указатели без физического переноса узлов. Кстати, в этом случае не надо считать количество элементов, т.к. их число явно известно, т.е. перенос можно осуществить за О(1). Ну а от сортировки уже никуда не денешься... 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	15.02.2011, 19:12 [ТС]	35
	volovzi, Остальное-то все относительно нормально кроме sort/merge? 0

@volovzi 274 / 175 / 12 Регистрация: 14.03.2010 Сообщений: 501
	15.02.2011, 20:46	36
	ForEveR, всегда можно найти, что улучшить . Например, в присвоении я бы не делал проверку на равенство. Ответственность за неё должна лежать на пользователе. То же самое — проверка в функциях «back()» и «front()». Это пользователь должен проверять, есть ли что-нибудь в списке. Аналогично и в функции «resize(size_t, const T &)» я бы не стал делать проверку на положительность размера. Но если уж ты обрабатываешь ошибки и не кидаешь исключение, то тогда нельзя завершать программу (кстати, что такое «terminate»?), а надо сообщить об ошибке и продолжить работу. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	15.02.2011, 22:11 [ТС]	37
	volovzi, terminate() вызов завершения программы. А искл я кидаю впринципе. _DEBUG_ERROR(msg) он пишет ошибку прямо в окне. Не в консоли пишет, а при выводе окна о том, что ошибка программа завершена из-за ошибки - пишет это сообщение... а terminate() это то, что происходит после runtime_error по сути. На равенство... Хм... Просто привык, чтобы это было. back/front по стандарту контролируются итератором насколько я понимаю. А в resize проверка из-за типа int, но наверное тоже не особо нужна 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	15.04.2011, 19:56 [ТС]	39
	bigredcat, Загляните в реализацию STL на досуге. 0

@bigredcat 374 / 321 / 32 Регистрация: 24.02.2011 Сообщений: 1,512 Записей в блоге: 1
	16.04.2011, 06:15	40
	ForEveR, так в первую очередь туда и заглядывал. Интересовался, как другие этот огород городят. Но у вас практически тоже самое. 0