Pertanyaan Apakah ada wadah C ++ dengan akses acak masuk akal yang tidak pernah memanggil copy konstruktor tipe elemen?


Saya memerlukan wadah yang mengimplementasikan API berikut (dan tidak perlu menerapkan yang lain):

class C<T> {
  C();

  T& operator[](int); // must have reasonably sane time constant

    // expand the container by default constructing elements in place.
  void resize(int); // only way anything is added.
  void clear();

  C<T>::iterator begin();
  C<T>::iterator end();
}

dan dapat digunakan pada:

class I {
 public:
  I();
 private:  // copy and assignment explicate disallowed
  I(I&);
  I& operator=(I&);
}

Dosis seperti binatang buas ada?

vector<T> tidak melakukannya (mengubah ukuran) dan saya tidak yakin seberapa cepat deque<T> aku s.


Saya tidak peduli tentang alokasi

Beberapa orang berasumsi bahwa alasan saya tidak dapat melakukan salinan adalah masalah alokasi memori. Alasan untuk kendala adalah bahwa tipe elemen secara eksplisit melarang penyalinan dan saya tidak bisa mengubahnya.


Sepertinya saya mendapatkan jawaban saya: STL tidak memilikinya. Tapi sekarang aku bertanya-tanya Kenapa tidak?


4
2017-08-19 00:22


asal


Jawaban:


Saya cukup yakin bahwa jawabannya di sini agak tegas "Tidak". Menurut definisi Anda, resize() harus mengalokasikan penyimpanan baru dan menginisialisasi dengan konstruktor default jika saya membaca ini dengan benar. Kemudian Anda akan memanipulasi objek dengan mengindeks ke dalam koleksi dan memanipulasi referensi alih-alih "memasukkan" ke dalam koleksi. Jika tidak, Anda memerlukan konstruktor penyalinan dan operator penugasan. Semua kontainer di Perpustakaan Standar memiliki persyaratan ini.

Anda mungkin ingin melihat menggunakan sesuatu seperti boost::ptr_vector<T>. Karena Anda memasukkan pointer, Anda tidak perlu khawatir tentang menyalin. Ini akan mengharuskan Anda secara dinamis mengalokasikan semua objek Anda sekalipun.


5
2017-08-19 00:40



Anda bisa menggunakan wadah pointer, seperti std::vector<T*>, jika elemen tidak dapat disalin dan memori mereka dikelola secara manual di tempat lain.

Jika vektor harus memiliki elemen, sesuatu seperti std::vector< std::shared_ptr<T> > bisa lebih tepat.

Dan ada juga yang Boost Pointer Container library, yang menyediakan kontainer untuk penanganan pointer aman kecuali.


5
2017-08-19 00:38



Menggunakan deque: kinerja baik-baik saja.

Standar mengatakan, "deque adalah struktur data pilihan ketika sebagian besar insersi dan penghapusan terjadi di awal atau di akhir urutan "(23.1.1). Dalam kasus Anda, semua insersi dan penghapusan berlangsung di bagian akhir, memenuhi kriteria untuk menggunakan deque.

http://www.gotw.ca/gotw/054.htm memiliki beberapa petunjuk tentang bagaimana Anda dapat mengukur kinerja, meskipun mungkin Anda memiliki kasus penggunaan tertentu, jadi itulah yang harus Anda ukur.

Sunting: Oke, jika Anda keberatan deque sebenarnya bukan, "Saya tidak yakin seberapa cepat deque adalah ", tetapi" tipe elemen tidak dapat menjadi elemen dalam kontainer standar ", maka kita dapat mengesampingkan kontainer standar. Tidak, binatang seperti itu tidak ada. deque "jangan pernah menyalin elemen", tetapi menyalin-membangunnya dari objek lain.

Hal terbaik berikutnya mungkin adalah membuat array elemen, default-constructed, dan memelihara wadah pointer ke elemen-elemen tersebut. Sesuatu di sepanjang garis-garis ini, meskipun hal ini mungkin dapat diubah jauh.

template <typename T>
struct C {
    vector<shared_array<T> > blocks;
    vector<T*> elements; // lazy, to avoid needing deque-style iterators through the blocks.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        if (n <= elements.size()) { /* exercise for the reader */ }
        else {
            boost::shared_array<T> newblock(new T[elements.size() - n]);
            blocks.push_back(newblock);
            size_t old = elements.size();
            // currently we "leak" newblock on an exception: see below
            elements.resize(n);
            for (int i = old; j < n; ++i) {
                elements[i] = &newblock[i - old];
            }
    }
    void clear() {
        blocks.clear();
        elements.clear();
    }
};

Ketika Anda menambahkan lebih banyak fungsi dan operator, itu akan mendekati deque, tetapi hindari apa pun yang membutuhkan penyalinan tipe T.

Edit: kalau dipikir-pikir itu, "latihan untuk pembaca" saya tidak bisa dilakukan dengan benar dalam kasus di mana seseorang melakukannya resize(10); resize(20); resize(15);. Anda tidak dapat menghapus setengah array. Jadi jika Anda ingin benar mereproduksi kontainer resize() semantik, merusak elemen berlebih segera, maka Anda harus mengalokasikan elemen-elemen secara individual (atau berkenalan dengan penempatan baru):

template <typename T>
struct C {
    deque<shared_ptr<T> > elements; // or boost::ptr_deque, or a vector.
    T &operator[](size_t idx) { return *elements[idx]; }
    void resize(size_t n) {
        size_t oldsize = elements.size();
        elements.resize(n);
        if (n > oldsize) {
            try {
                for (size_t i = oldsize; i < n; ++i) {
                    elements[i] = shared_ptr<T>(new T());
                }
            } catch(...) {
                // closest we can get to strong exception guarantee, since
                // by definition we can't do anything copy-and-swap-like
                elements.resize(oldsize);
                throw;
            }
        }
    }
    void clear() {
        elements.clear();
    }
};

Kode yang lebih bagus, tidak begitu tertarik pada pola akses memori (tapi kemudian, saya tidak jelas apakah kinerja menjadi perhatian atau tidak karena Anda khawatir tentang kecepatan deque.)


4
2017-08-19 00:33



Seperti yang Anda temukan, semua kontainer standar tidak sesuai dengan kebutuhan Anda. Jika kita bisa membuat beberapa asumsi tambahan, itu tidak akan terlalu sulit untuk menulis wadah Anda sendiri.

  • Wadah akan selalu tumbuh - resize akan selalu dipanggil dengan jumlah yang lebih besar dari sebelumnya, tidak pernah lebih rendah.
  • Itu oke untuk resize untuk membuat wadah lebih besar dari yang diminta; membangun sejumlah objek yang tidak digunakan di ujung kontainer dapat diterima.

Inilah awal. Saya memberikan banyak detail kepada Anda.

class C<T> { 
  C();
  ~C() { clear(); }

  T& operator[](int i) // must have reasonably sane time constant 
  {
      return blocks[i / block_size][i % block_size];
  }

    // expand the container by default constructing elements in place. 
  void resize(int n) // only way anything is added. 
  {
      for (int i = (current_size/block_size)+1; i <= n/block_size;  ++i)
      {
          blocks.push_back(new T[block_size]);
      }
      current_size = n;
  }

  void clear()
  {
      for (vector<T*>::iterator i = blocks.begin();  i != blocks.end();  ++i)
          delete[] *i;
      current_size = 0;
  }

  C<T>::iterator begin(); 
  C<T>::iterator end(); 
private:
  vector<T*> blocks;
  int current_size;
  const int block_size = 1024; // choose a size appropriate to T
} 

P.S. Jika ada yang bertanya mengapa Anda ingin melakukan ini, beri tahu mereka bahwa Anda memerlukan array std::auto_ptr. Itu seharusnya bagus untuk ditertawakan.


3
2017-08-19 17:31



Semua kontainer standar membutuhkan elemen yang dapat dipublikasi. Paling tidak karena push_back dan masukkan salin elemen yang diteruskan kepada mereka. Saya tidak berpikir Anda bisa lolos dengan std :: deque karena bahkan metode resize-nya membutuhkan parameter yang akan disalin untuk mengisi elemen.

Untuk menggunakan kelas yang benar-benar tidak dapat dipertukarkan dalam kontainer standar, Anda harus menyimpan pointer ke objek-objek tersebut. Itu terkadang bisa menjadi beban tetapi penggunaan shared_ptr atau berbagai meningkatkan penunjuk kontainer bisa membuatnya lebih mudah.

Jika Anda tidak menyukai salah satu dari solusi tersebut, maka ambillah penelusuran melalui sisa peningkatan. Mungkin ada hal lain yang cocok di sana. Mungkin kontainer intrusif?

Jika tidak, jika Anda tidak berpikir apa pun yang sesuai dengan kebutuhan Anda maka Anda selalu dapat mencoba untuk menggulung wadah Anda sendiri yang melakukan apa yang Anda inginkan. (Atau lakukan lebih banyak pencarian untuk mengetahui apakah ada orang lain yang pernah melakukan hal semacam itu.)


2
2017-08-19 00:39



Anda tidak harus memilih wadah berdasarkan cara menangani memori. deque misalnya adalah antrian ganda berakhir, jadi Anda hanya harus menggunakannya ketika Anda membutuhkan antrian ganda.

Hampir semua kontainer akan mengalokasikan memori jika Anda mengubah ukurannya! Tentu saja, Anda dapat mengubah kapasitas di depan dengan menelepon vector::reserve. Kapasitas adalah jumlah elemen fisik dalam memori, ukurannya adalah berapa banyak Anda aktif menggunakan.

Tentunya, masih akan ada alokasi jika Anda melampaui kapasitas Anda.


1
2017-08-19 00:34



Melihat ::boost::array. Ini tidak memungkinkan penampung diubah ukurannya setelah membuatnya, tetapi tidak menyalin apa pun.

Dapatkan keduanya resize dan tidak ada penyalinan akan menjadi tipuan. Saya tidak akan mempercayai ::std::dequekarena saya pikir mungkin itu bisa menyalin dalam beberapa kasus. Jika Anda benar-benar perlu mengubah ukuran, saya akan kode wadah deque-seperti Anda sendiri. Karena satu-satunya cara Anda akan mengubah ukuran dan tidak menyalin adalah memiliki sistem halaman seperti ::std::deque menggunakan.

Juga, memiliki sistem halaman berarti itu at tidak akan secepat itu akan terjadi ::std::vector dan ::boost::array dengan tata letak memori berdekatan mereka, meskipun itu masih bisa cukup cepat.


0
2017-08-19 20:03