Menulis Kontainer STL Anda sendiri

120

Apakah ada pedoman tentang bagaimana seseorang harus menulis wadah baru yang akan berperilaku seperti STLwadah lainnya?

c++ stl c++-standard-library Avinash
sumber
7
Lihat implementasi container standar yang ada, dan cobalah untuk memahaminya - fungsi, jenis kembalian, kelebihan beban operator, jenis bertingkat, pengelolaan memori, dan semuanya.
Nawaz
Saya biasanya mulai dengan menyalin prototipe fungsi anggota dari wadah mana pun yang paling mendekati konsepnya dengan apa yang saya lakukan, baik dari msdn, atau standar. ( cplusplus.com tidak memiliki fungsi C ++ 11, dan www.sgi.com tidak cocok)
Mooing Duck
@Mooing Duck: menurut Anda msdn lebih dekat dengan standar daripada sgi?
Dani
3
Ini pasti. MSDN terkini - SGI adalah pra-Standar
Anak Anjing
9
Referensi online terbaik (kelengkapan, ketepatan dan terutama kegunaan) sejauh ini adalah cppreference.com. Ini juga menjelaskan banyak fitur bahasa selain dari perpustakaan. Dan ini adalah wiki, jadi seharusnya mengandung lebih sedikit kesalahan daripada cplusplus.com.
rubenvb

Jawaban:

209

Berikut urutan pseudo-kontainer saya potongan bersama dari § 23.2.1 \ 4 Catatan bahwa iterator_categoryharus menjadi salah satu std::input_iterator_tag, std::output_iterator_tag, std::forward_iterator_tag, std::bidirectional_iterator_tag, std::random_access_iterator_tag. Juga perhatikan bahwa di bawah ini secara teknis lebih ketat dari yang disyaratkan, tetapi inilah idenya. Perhatikan bahwa sebagian besar fungsi "standar" secara teknis bersifat opsional, karena kedahsyatannya yaitu iterator.

template <class T, class A = std::allocator<T> >
class X {
public:
    typedef A allocator_type;
    typedef typename A::value_type value_type; 
    typedef typename A::reference reference;
    typedef typename A::const_reference const_reference;
    typedef typename A::difference_type difference_type;
    typedef typename A::size_type size_type;

    class iterator { 
    public:
        typedef typename A::difference_type difference_type;
        typedef typename A::value_type value_type;
        typedef typename A::reference reference;
        typedef typename A::pointer pointer;
        typedef std::random_access_iterator_tag iterator_category; //or another tag

        iterator();
        iterator(const iterator&);
        ~iterator();

        iterator& operator=(const iterator&);
        bool operator==(const iterator&) const;
        bool operator!=(const iterator&) const;
        bool operator<(const iterator&) const; //optional
        bool operator>(const iterator&) const; //optional
        bool operator<=(const iterator&) const; //optional
        bool operator>=(const iterator&) const; //optional

        iterator& operator++();
        iterator operator++(int); //optional
        iterator& operator--(); //optional
        iterator operator--(int); //optional
        iterator& operator+=(size_type); //optional
        iterator operator+(size_type) const; //optional
        friend iterator operator+(size_type, const iterator&); //optional
        iterator& operator-=(size_type); //optional            
        iterator operator-(size_type) const; //optional
        difference_type operator-(iterator) const; //optional

        reference operator*() const;
        pointer operator->() const;
        reference operator[](size_type) const; //optional
    };
    class const_iterator {
    public:
        typedef typename A::difference_type difference_type;
        typedef typename A::value_type value_type;
        typedef typename const A::reference reference;
        typedef typename const A::pointer pointer;
        typedef std::random_access_iterator_tag iterator_category; //or another tag

        const_iterator ();
        const_iterator (const const_iterator&);
        const_iterator (const iterator&);
        ~const_iterator();

        const_iterator& operator=(const const_iterator&);
        bool operator==(const const_iterator&) const;
        bool operator!=(const const_iterator&) const;
        bool operator<(const const_iterator&) const; //optional
        bool operator>(const const_iterator&) const; //optional
        bool operator<=(const const_iterator&) const; //optional
        bool operator>=(const const_iterator&) const; //optional

        const_iterator& operator++();
        const_iterator operator++(int); //optional
        const_iterator& operator--(); //optional
        const_iterator operator--(int); //optional
        const_iterator& operator+=(size_type); //optional
        const_iterator operator+(size_type) const; //optional
        friend const_iterator operator+(size_type, const const_iterator&); //optional
        const_iterator& operator-=(size_type); //optional            
        const_iterator operator-(size_type) const; //optional
        difference_type operator-(const_iterator) const; //optional

        reference operator*() const;
        pointer operator->() const;
        reference operator[](size_type) const; //optional
    };

    typedef std::reverse_iterator<iterator> reverse_iterator; //optional
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator; //optional

    X();
    X(const X&);
    ~X();

    X& operator=(const X&);
    bool operator==(const X&) const;
    bool operator!=(const X&) const;
    bool operator<(const X&) const; //optional
    bool operator>(const X&) const; //optional
    bool operator<=(const X&) const; //optional
    bool operator>=(const X&) const; //optional

    iterator begin();
    const_iterator begin() const;
    const_iterator cbegin() const;
    iterator end();
    const_iterator end() const;
    const_iterator cend() const;
    reverse_iterator rbegin(); //optional
    const_reverse_iterator rbegin() const; //optional
    const_reverse_iterator crbegin() const; //optional
    reverse_iterator rend(); //optional
    const_reverse_iterator rend() const; //optional
    const_reverse_iterator crend() const; //optional

    reference front(); //optional
    const_reference front() const; //optional
    reference back(); //optional
    const_reference back() const; //optional
    template<class ...Args>
    void emplace_front(Args&&...); //optional
    template<class ...Args>
    void emplace_back(Args&&...); //optional
    void push_front(const T&); //optional
    void push_front(T&&); //optional
    void push_back(const T&); //optional
    void push_back(T&&); //optional
    void pop_front(); //optional
    void pop_back(); //optional
    reference operator[](size_type); //optional
    const_reference operator[](size_type) const; //optional
    reference at(size_type); //optional
    const_reference at(size_type) const; //optional

    template<class ...Args>
    iterator emplace(const_iterator, Args&&...); //optional
    iterator insert(const_iterator, const T&); //optional
    iterator insert(const_iterator, T&&); //optional
    iterator insert(const_iterator, size_type, T&); //optional
    template<class iter>
    iterator insert(const_iterator, iter, iter); //optional
    iterator insert(const_iterator, std::initializer_list<T>); //optional
    iterator erase(const_iterator); //optional
    iterator erase(const_iterator, const_iterator); //optional
    void clear(); //optional
    template<class iter>
    void assign(iter, iter); //optional
    void assign(std::initializer_list<T>); //optional
    void assign(size_type, const T&); //optional

    void swap(X&);
    size_type size() const;
    size_type max_size() const;
    bool empty() const;

    A get_allocator() const; //optional
};
template <class T, class A = std::allocator<T> >
void swap(X<T,A>&, X<T,A>&); //optional

Juga, setiap kali saya membuat wadah, saya menguji dengan kelas yang kurang lebih seperti ini:

#include <cassert>
struct verify;
class tester {
    friend verify;
    static int livecount;
    const tester* self;
public:
    tester() :self(this) {++livecount;}
    tester(const tester&) :self(this) {++livecount;}
    ~tester() {assert(self==this);--livecount;}
    tester& operator=(const tester& b) {
        assert(self==this && b.self == &b);
        return *this;
    }
    void cfunction() const {assert(self==this);}
    void mfunction() {assert(self==this);}
};
int tester::livecount=0;
struct verify {
    ~verify() {assert(tester::livecount==0);}
}verifier;

Buat wadah berisi testerobjek, dan panggil masing-masing function()saat Anda menguji wadah Anda. Jangan membuat testerobjek global apa pun . Jika wadah Anda curang di mana saja, testerkelas ini akan assertdan Anda akan tahu bahwa Anda tidak sengaja menipu di suatu tempat.

Mooing Duck
sumber
1
Ini menarik. Bagaimana penguji Anda bekerja? Ada beberapa kesalahan parse, yang sepele (hilang ';') tetapi tidak yakin bagaimana verifikasi destruktor itu bekerja. Oh, maksudmu assert(tester::livecount == 0);. Mmmmm, masih belum yakin bagaimana framework tester ini bekerja. Bisakah Anda memberi contoh?
Adrian
2
Penguji memiliki satu anggota nonstatis yang merupakan penunjuk ke dirinya sendiri, dan destruktor serta anggota adalah cara untuk memeriksa bahwa tidak ada yang tidak valid memcpy. (pengujian tidak selalu mudah, tetapi berhasil menangkap beberapa). Ini livecountadalah detektor kebocoran sederhana, untuk memastikan penampung Anda memanggil jumlah konstruktor dan destruktor yang sama.
Mooing Duck
Oke, saya mengerti, tapi bagaimana cara itu menguji iterator Anda? BTW, saya pikir Anda verifiertidak bermaksud varifier.
Adrian
4
@Adrian Tidak, tidak, Anda menulis penampung Anda, dan kemudian memasukkan banyak wadah ini ke dalam penampung, dan melakukan sesuatu dengan penampung tersebut, untuk memverifikasi bahwa Anda tidak memcpy secara tidak sengaja, dan ingat untuk memanggil semua penghancur.
Mooing Duck
1
bolehkah saya menyarankan untuk mewarisi iterator dari std::iteratorheader<iterator>
sp2danny
28

Anda perlu membaca bagian Standar C ++ tentang Penampung dan persyaratan yang diberlakukan Standar C ++ untuk implementasi penampung.

Bab yang relevan dalam standar C ++ 03 adalah:

Bagian 23.1 Persyaratan Kontainer

Bab yang relevan dalam standar C ++ 11 adalah:

Bagian 23.2 Persyaratan Kontainer

Draf hampir final dari standar C ++ 11 tersedia secara gratis di sini .

Anda mungkin juga, membaca beberapa buku bagus yang akan membantu Anda memahami persyaratan dari sudut pandang pengguna wadah. Dua buku bagus yang dengan mudah terlintas di benak saya adalah:

STL efektif olehScott Meyers &
Perpustakaan Standar C ++: Tutorial dan Referensi olehNicolai Josutils

Alok Save
sumber
6

Berikut adalah implementasi yang sangat sederhana dari vektor palsu, yang pada dasarnya merupakan pembungkus std::vectordan memiliki iteratornya sendiri (tetapi nyata), yang meniru iterator STL. Sekali lagi, iterator sangat sederhana, melewati banyak konsep seperti const_iterator, pemeriksaan validitas, dll.

Kode dijalankan di luar kotak.

#include <iostream>
#include <string>
#include <vector>

template<typename T>
struct It
{
    std::vector<T>& vec_;
    int pointer_;

    It(std::vector<T>& vec) : vec_{vec}, pointer_{0} {}

    It(std::vector<T>& vec, int size) : vec_{vec}, pointer_{size} {}

    bool operator!=(const It<T>& other) const
    {
        return !(*this == other);
    }

    bool operator==(const It<T>& other) const
    {
        return pointer_ == other.pointer_;
    }

    It& operator++()
    {
        ++pointer_;            
        return *this;
    }

    T& operator*() const
    {
        return vec_.at(pointer_);   
    }
};

template<typename T>
struct Vector
{
    std::vector<T> vec_;

    void push_back(T item)
    {
        vec_.push_back(item);
    };

    It<T> begin()
    {
        return It<T>(vec_);
    }

    It<T> end()
    {
        return It<T>(vec_, vec_.size());
    }
};

int main()
{
  Vector<int> vec;
  vec.push_back(1);
  vec.push_back(2);
  vec.push_back(3);

  bool first = true;
  for (It<int> it = vec.begin(); it != vec.end(); ++it)
  {
      if (first) //modify container once while iterating
      {
          vec.push_back(4);
          first = false;
      }

      std::cout << *it << '\n'; //print it 
      (*it)++;                  //change it
  }

  for (It<int> it = vec.begin(); it != vec.end(); ++it)
  {
      std::cout << *it << '\n'; //should see changed value
  }
}
PoweredByRice
sumber