Kapasitas awal vektor dalam C ++

Apa dari capacity()dari std::vectoryang dibuat menggunakan konstuktor default? Saya tahu bahwa size()nilainya nol. Bisakah kita menyatakan bahwa vektor yang dibuat default tidak memanggil alokasi memori heap?

Dengan cara ini dimungkinkan untuk membuat array dengan cadangan arbitrer menggunakan alokasi tunggal, seperti std::vector<int> iv; iv.reserve(2345);. Katakanlah karena alasan tertentu, saya tidak ingin memulai size()pada 2345.

Misalnya, di Linux (g ++ 4.4.5, kernel 2.6.32 amd64)

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

dicetak 0,10. Apakah ini aturan, atau tergantung vendor STL?

Standar tidak menentukan inisial apa yang capacityseharusnya menjadi wadah, jadi Anda mengandalkan implementasinya. Penerapan umum akan memulai kapasitas dari nol, tetapi tidak ada jaminan. Di sisi lain, tidak ada cara untuk memperbaiki strategi Anda, std::vector<int> iv; iv.reserve(2345);jadi tetaplah menggunakannya.

Implementasi penyimpanan std :: vector bervariasi secara signifikan, tetapi semua yang saya temukan mulai dari 0.

Kode berikut:

#include <iostream>
#include <vector>

int main()
{
  using namespace std;

  vector<int> normal;
  cout << normal.capacity() << endl;

  for (unsigned int loop = 0; loop != 10; ++loop)
  {
      normal.push_back(1);
      cout << normal.capacity() << endl;
  }

  cin.get();
  return 0;
}

Memberikan keluaran sebagai berikut:

0
1
2
4
4
8
8
8
8
16
16

di bawah GCC 5.1 dan:

0
1
2
3
4
6
6
9
9
9
13

di bawah MSVC 2013.

Sejauh yang saya mengerti tentang standarnya (meskipun saya sebenarnya tidak bisa menyebutkan referensi), instansiasi kontainer dan alokasi memori sengaja dipisahkan untuk alasan yang baik. Oleh karena itu, Anda memiliki panggilan yang berbeda dan terpisah untuk

• constructor untuk membuat wadah itu sendiri
• reserve() untuk mengalokasikan terlebih dahulu blok memori yang sesuai untuk menampung setidaknya (!) sejumlah objek

Dan ini sangat masuk akal. Satu-satunya hak untuk tetap ada reserve()adalah memberi Anda kesempatan untuk membuat kode seputar kemungkinan realokasi mahal saat menumbuhkan vektor. Agar berguna, Anda harus mengetahui jumlah objek yang akan disimpan atau setidaknya harus dapat membuat tebakan yang cerdas. Jika ini tidak diberikan, lebih baik Anda menjauh reserve()karena Anda hanya akan mengubah alokasi ulang untuk memori yang terbuang.

Jadi menggabungkan semuanya:

• Standar sengaja tidak menetapkan konstruktor yang memungkinkan Anda mengalokasikan blok memori untuk sejumlah objek tertentu (yang setidaknya akan lebih diinginkan daripada mengalokasikan implementasi spesifik, "sesuatu" tetap di bawah tenda).
• Alokasi tidak boleh implisit. Jadi, untuk mengalokasikan blok sebelumnya, Anda perlu melakukan panggilan terpisah reserve()dan ini tidak perlu berada di tempat konstruksi yang sama (tentu saja bisa / harus dilakukan nanti, setelah Anda mengetahui ukuran yang diperlukan untuk mengakomodasi)
• Jadi, jika vektor akan selalu mengalokasikan blok memori dari implementasi ukuran yang ditentukan, ini akan menggagalkan pekerjaan yang dimaksudkan reserve(), bukan?
• Apa keuntungan dari mengalokasikan blok jika STL secara alami tidak dapat mengetahui tujuan yang dimaksudkan dan ukuran vektor yang diharapkan? Ini akan menjadi agak tidak masuk akal, jika tidak kontra-produktif.
• Solusi yang tepat adalah dengan mengalokasikan dan mengimplementasikan blok tertentu dengan blok pertama push_back()- jika belum dialokasikan sebelumnya oleh reserve().
• Dalam kasus realokasi yang diperlukan, peningkatan ukuran blok juga spesifik untuk implementasi. Implementasi vektor yang saya ketahui mulai dengan peningkatan ukuran secara eksponensial tetapi akan membatasi laju peningkatan pada maksimum tertentu untuk menghindari pemborosan memori dalam jumlah besar atau bahkan meledakkannya.

Semua ini datang ke operasi penuh dan keuntungan hanya jika tidak terganggu oleh konstruktor pengalokasi. Anda memiliki default yang wajar untuk skenario umum yang dapat diganti sesuai permintaan oleh reserve()(dan shrink_to_fit()). Jadi, meskipun standar tidak secara eksplisit menyatakan demikian, saya cukup yakin dengan asumsi bahwa vektor yang baru dibangun tidak mengalokasikan sebelumnya adalah taruhan yang cukup aman untuk semua implementasi saat ini.

Sebagai sedikit tambahan untuk jawaban lain, saya menemukan bahwa ketika berjalan di bawah kondisi debug dengan Visual Studio vektor yang dibangun default akan tetap mengalokasikan di heap meskipun kapasitas dimulai dari nol.

Khususnya jika _ITERATOR_DEBUG_LEVEL! = 0 maka vektor akan mengalokasikan beberapa ruang untuk membantu pemeriksaan iterator.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

Saya baru saja menemukan ini sedikit mengganggu karena saya menggunakan pengalokasi khusus pada saat itu dan tidak mengharapkan alokasi tambahan.

Ini adalah pertanyaan lama, dan semua jawaban di sini telah menjelaskan dengan tepat sudut pandang standar dan cara Anda bisa mendapatkan kapasitas awal secara portabel dengan menggunakan std::vector::reserve;

Namun, saya akan menjelaskan mengapa tidak masuk akal bagi implementasi STL untuk mengalokasikan memori pada konstruksi sebuah std::vector<T>objek ;

1. std::vector<T> dari jenis yang tidak lengkap;

   Sebelum C ++ 17, itu adalah perilaku tidak terdefinisi untuk membangun std::vector<T>jika definisi Tmasih belum diketahui pada titik pembuatannya . Namun, batasan itu dikurangi di C ++ 17 .

   Untuk mengalokasikan memori untuk suatu objek secara efisien, Anda perlu mengetahui ukurannya. Dari C ++ 17 dan seterusnya, klien Anda mungkin memiliki kasus di mana std::vector<T>kelas Anda tidak mengetahui ukurannya T. Apakah masuk akal untuk memiliki karakteristik alokasi memori yang bergantung pada kelengkapan tipe?

2. Unwanted Memory allocations

   Ada banyak, banyak, banyak kali Anda membutuhkan model grafik dalam perangkat lunak. (Pohon adalah grafik); Anda kemungkinan besar akan memodelkannya seperti:

   class Node {
       ....
       std::vector<Node> children; //or std::vector< *some pointer type* > children;
       ....
    };
   

   Sekarang pikirkan sejenak dan bayangkan jika Anda memiliki banyak node terminal. Anda akan sangat kesal jika implementasi STL Anda mengalokasikan memori ekstra hanya untuk mengantisipasi adanya objek di dalamnya children.

   Ini hanyalah satu contoh, silakan memikirkan lebih banyak ...

Standar tidak menentukan nilai awal untuk kapasitas tetapi kontainer STL secara otomatis tumbuh untuk menampung data sebanyak yang Anda masukkan, asalkan Anda tidak melebihi ukuran maksimum (gunakan fungsi anggota max_size untuk mengetahui). Untuk vektor dan string, pertumbuhan ditangani oleh realoc bila diperlukan lebih banyak ruang. Misalkan Anda ingin membuat nilai penahan vektor 1-1000. Tanpa menggunakan reserve, kode biasanya akan menghasilkan antara 2 dan 18 realokasi selama loop berikut:

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

Memodifikasi kode untuk menggunakan reserve mungkin menghasilkan 0 alokasi selama loop:

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

Secara kasar dapat dikatakan, kapasitas vektor dan string tumbuh dengan faktor antara 1,5 dan 2 setiap kali.