Implementasi std::vector yang mandiri dan kompatibel dengan STL

Implementasi std::vector yang disertakan dengan Visual Studio 2010 dan versi sebelumnya memiliki kekhasan yang terkenal: metode resize memiliki tanda tangan berikut (sesuai dengan C++03):

void resize(size_type new_size, value_type value);

alih-alih tanda tangan yang sesuai dengan C++11 yang telah digunakan oleh sebagian besar implementasi STL lainnya (seperti STL atau STLport gcc) jauh sebelum C++11:

void resize(size_type new_size, const value_type& value);

Masalah dengan varian pertama adalah, dalam beberapa situasi, ia akan gagal dikompilasi jika value_type memiliki spesifikasi penyelarasan:

struct __declspec(align(64)) S { ... };
std::vector<S> v;  // error C2719: '_Val': formal parameter with __declspec(align('64')) won't be aligned

Ini adalah baik dikenal masalah tanpa solusi yang memuaskan selain menggunakan implementasi std::vector yang berbeda .

Saya mencari implementasi std::vector yang ditulis dengan baik, teruji dengan baik, mandiri dan kompatibel dengan STL dengan lisensi gaya MIT yang dapat saya masukkan ke dalam proyek saya sebagai wadah pilihan tipe selaras.

Saya mempertimbangkan untuk mengekstraknya dari STLport atau STL gcc tetapi, karena sepenuhnya memenuhi standar, keduanya besar dengan banyak ketergantungan yang tidak sepele.

(Saya akan sangat senang dengan penerapan subset wajar std::vector yang hanya mendukung push_back, clear, capacity, size, reserve, resize, swap dan pengindeksan array.)

Ada ide?


c++ alignment vector stl
person François Beaune    schedule 23.02.2012    source sumber
comment
Saya tidak melihat bagaimana metode .resize() menyebabkan deklarasi std::vector<S> v; gagal. Membuat instance templat kelas tidak membuat instance metodenya, hanya metode yang digunakan. (Yaitu ctor dan dtor default dalam kasus ini).   -  person MSalters    schedule 23.02.2012
comment
Saya kira kesalahan terjadi selama penguraian... Ingatlah bahwa kita sedang membicarakan masalah yang benar-benar khusus untuk kompiler di sini.   -  person François Beaune    schedule 23.02.2012

Jawaban (2)


arrow_upward
8
arrow_downward

Orang-orang di belakang perpustakaan Eigen tampaknya telah menemukan solusi yang bagus untuk masalah penyimpanan "tipe yang terlalu selaras" (sebagaimana Stephan T. Lavavej menyebutnya) menjadi std::vector seperti yang diterapkan dalam STL Visual Studio.

Penerapannya tampaknya tidak terlalu rumit (lihat sumber di sini dan di sini) tetapi ide utamanya adalah merangkum tipe yang masuk ke std::vector dengan pembungkus tipis:

#include <vector>

template <typename T>
struct wrapper : public T
{
    wrapper() {}
    wrapper(const T& rhs) : T(rhs) {}
};

struct __declspec(align(64)) S
{
    float x, y, z, w;
};

int main()
{
    std::vector< wrapper<S> > v;  // OK, no C2719 error
    return 0;
}

Soal implementasi di Eigen, harus saya akui saya kurang paham

  • mengapa mereka membutuhkan Eigen::aligned_allocator_indirection,
  • mengapa mereka perlu membuat pengecualian untuk tipe aritmatika di EIGEN_WORKAROUND_MSVC_STL_SUPPORT,
  • mengapa mereka perlu mendefinisikan semua konstruktor dan operator ini di Eigen::workaround_msvc_stl_support,
  • atau mengapa mereka perlu mendefinisikan ulang resize dalam sebagian spesialisasi std::vector untuk pengalokasi Eigen::aligned_allocator_indirection...

Petunjuk diterima. Intinya, trik ini bekerja dengan sempurna (sejauh yang saya tahu) dan menurut saya tidak ada yang salah dengan trik ini, kecuali mungkin sedikit ketidakeleganannya.

person François Beaune    schedule 23.02.2012

arrow_upward
1
arrow_downward

Opsi termudah (dan terbaik, menurut saya) adalah menyediakan fungsi gratis sebagai ekstensi ke antarmuka vector, yang melakukan hal yang benar. Fungsi yang Anda perlukan untuk mengimplementasikan resize semuanya tersedia dari antarmuka publik std::vector:

#include <vector>

template<class T, class Alloc>
void resize(std::vector<T, Alloc>& v,
    typename std::vector<T, Alloc>::size_type new_size, T const& val)
{
  if (v.size() < new_size)
      v.insert(v.end(), new_size - v.size(), val);
  else if (new_size < v.size())
      v.erase(v.begin() + new_size, v.end());
}

Dan untuk konsistensi juga versi argumen tunggal:

template<class T, class Alloc>
void resize(std::vector<T, Alloc>& v,
    typename std::vector<T, Alloc>::size_type new_size)
{
    v.resize(new_size); // simply forward
}

Namun, jika Anda hanya ingin memasukkan vektor baru dan tidak perlu mengkhawatirkan fungsi bebas atau fungsi anggota, pilihan lainnya adalah dengan membuat subkelas std::vector:

#include <vector>
#include <memory>

template<class T, class Alloc = std::allocator<T>>
class myvector
  : public std::vector<T, Alloc>
{
  typedef std::vector<T, Alloc> base;
public:
  typedef typename base::size_type size_type;

  void resize(size_type new_size){
    base::resize(new_size);
  }

  void resize(size_type new_size, T const& val){
    if (this->size() < new_size)
        this->insert(this->end(), new_size - this->size(), val);
    else if (new_size < this->size())
        this->erase(this->begin() + new_size, this->end());
  }
};

Perhatikan bahwa saya juga menyediakan versi argumen tunggal resize, karena versi dua argumen akan menyembunyikan semua versi kelas dasar. Perhatikan juga bahwa saya perlu mengawali semua panggilan fungsi anggota dengan this->, karena mereka bergantung pada kelas dasar std::vector, dan dengan demikian pada argumen templat.

person Xeo    schedule 23.02.2012
comment
Subkelas std::vector adalah salah satu pendekatan pertama saya, sayangnya masih gagal dikompilasi karena pada akhirnya std::vector masih dipakai. - person François Beaune; 23.02.2012
comment
@FrançoisBeaune: Ah, itu sangat disayangkan. :/ Coba komentari versi std::vector, atau cukup perbaiki tanda tangannya. :P FWIW, VS11 masih belum memperbaiki masalah ini. - person Xeo; 23.02.2012
comment
Aneh, menurut STL di sini, vector::resize di VS11 seharusnya memiliki tanda tangan T const&, tetapi pratinjau pengembang saat ini tidak... Saya rasa saya akan mengiriminya email. - person Xeo; 23.02.2012