Memastikan bahwa template variadik tidak mengandung duplikat

Saya kira seluruh masalah saya dijelaskan dengan baik dalam judul. Saya mencoba membuat templat kelas variadik (dalam C++11, C++14 atau C++1z).

template<typename ...Types> struct MyVariadicTemplate {};

dan pastikan bahwa daftar tipe dalam setiap contoh MyVariadicTemplate bersifat injektif, jadi jika saya, misalnya, memanggil potongan kode berikut:

MyVariadicTemplate<int, double, int> x;

itu tidak dapat dikompilasi (saya akan dengan senang hati melakukannya menggunakan static_assert).

Saya sangat menghargai petunjuknya.


c++ templates c++11 variadic-templates
person Jytug    schedule 06.12.2015    source sumber

Jawaban (3)


arrow_upward
5
arrow_downward

Ini dapat ditulis dengan bantuan dua metafungsi.

Pertama, IsContained memeriksa apakah suatu tipe muncul dalam daftar tipe.

template <typename T, typename... List>
struct IsContained;

template <typename T, typename Head, typename... Tail>
struct IsContained<T, Head, Tail...>
{
    enum { value = std::is_same<T, Head>::value || IsContained<T, Tail...>::value };
};

template <typename T>
struct IsContained<T>
{
    enum { value = false };
};

Kedua, IsUnique memeriksa apakah daftar tipe tidak berisi duplikat. Ia menggunakan IsContained untuk memeriksa semua kombinasi elemen.

template <typename... List>
struct IsUnique;

template <typename Head, typename... Tail>
struct IsUnique<Head, Tail...>
{
    enum { value = !IsContained<Head, Tail...>::value && IsUnique<Tail...>::value };
};

template <>
struct IsUnique<>
{
    enum { value = true };
};

Dengan alat ini, pernyataan statis menjadi sangat sederhana:

template <typename... Ts>
struct NoDuplicates
{
    static_assert(IsUnique<Ts...>::value, "No duplicate types allowed");
};
person TheOperator    schedule 06.12.2015
comment
Wah, pintar sekali. Saya baru saja melihat contoh faktorial, namun tidak terlintas dalam pikiran saya untuk menerapkannya. Ini juga berguna dalam pekerjaan saya selanjutnya, karena saya tetap membutuhkan IsContained. Terima kasih - person Jytug; 07.12.2015
comment
Saya suka enum { value = ... } sebagai pengganti static constexpr auto value = ... - person Joel Cornett; 07.12.2015

arrow_upward
2
arrow_downward

Jika Anda memiliki akses ke ekspresi lipat C++1z, Anda dapat menyederhanakan jawaban @TheOperator dengan melakukan hal berikut untuk IsContained:

template <typename T, typename... List>
struct IsContained;

template <typename T, typename Head, typename... Tail>
struct IsContained<T, Head, Tail...>
{
    enum { value = std::is_same<T, Head>::value || (IsContained<T, Tail>::value && ... && true) };
};

template <typename T>
struct IsContained<T>
{
    enum { value = false };
};

Perbedaannya adalah dengan ekspresi lipatan ada peluang lebih besar untuk menggunakan kembali instance kelas. Jika Anda menggunakan banyak parameter atau memiliki banyak perbandingan berulang, mungkin ini memiliki waktu kompilasi yang lebih cepat. Seperti biasa, ujilah sendiri.

person JKor    schedule 06.12.2015
comment
Terima kasih. Karena penasaran - apakah perlu menambahkan ( && true) di akhir ekspresi lipatan? Di sini en.cppreference.com/w/cpp/lingual/fold disebutkan bahwa lipatan && dievaluasi menjadi benar jika paket kosong. - person Jytug; 07.12.2015
comment
@Jytug dalam pertemuan standardisasi baru-baru ini mereka menghapus semua default untuk lipatan unary dan membuat lipatan unary dengan paket kosong yang tidak terbentuk (lihat P0160R0). Itu sebabnya saya melakukan lipatan biner (dengan && true) - person JKor; 07.12.2015
comment
(IsContained‹T, Tail›::value && ... && true) ini salah! Alih-alih gunakan (IsContained‹T, Tail›::value || ... || false) karena hasil ekspresi lipatan harus benar jika ada IsContained‹T, Tail›::value yang benar. - person sigmaN; 03.05.2020

arrow_upward
0
arrow_downward

Dengan c++17 ini cukup mudah.

#include <type_traits>

template <typename T, typename... Ts>
struct are_distinct: std::conjunction<
    std::negation<std::is_same<T, Ts>>...,
    are_distinct<Ts...>
>{};

template <typename T>
struct are_distinct<T>: std::true_type{};

Algoritmenya sama dengan yang diilustrasikan oleh Jkor dan Operator, namun diungkapkan dengan lebih ringkas.

Kemudian, untuk pertanyaan spesifik Anda, Anda akan menggunakannya dengan cara ini:

template<typename ...Types> 
struct MyVariadicTemplate {
    static_assert(are_distinct<Types...>::value, "Types must be distinct");

    /* rest of the code */
};

Namun, mengingat ini adalah O(n²), saya ingin tahu apakah ada cara untuk membuatnya tidak terlalu rumit secara algoritmik? Boost::mpl yang unik‹› adalah O( n), tapi saya tidak bisa memahami algo yang digunakannya.

person Fabio A.    schedule 21.03.2021