1

Создаю класс множество(Set) на C++. Использую класс BitScale(шкалу битов) для удобного поведения класса Set. Столкнулся с проблемой при реализации метода map. Задумка метода: В моём случае не список, а множество

(В моём случае не список, а множество).

Суть проблемы: есть оператор объединения в множестве Set& operator |=(T2&& item) - для элемента множества, а есть Set& operator |=<T>(const Set&& set) - для объединения другого множества. Компилятор не может понять, какой шаблон когда использовать:

Например, в main.cpp set1 |= set2; вызывает ошибку "Ошибка C2912 явная специализация; "Set &Set::operator |=(const Set &&)" не является специализацией функции-шаблона". Тобишь компилятору не нравится как я написал явную специализацию... Нужна помощь... Ниже реализация класса Set(с методом map), класса BitScale и главная ф-я main.

#pragma once
#include "BitScale.h"

template <class T>
class Set
{
    int reserve_;
    int capacity_;
    BitScale bitScale_;
    T **array_;
public:
    Set(int reserve = 256) :
        reserve_(reserve)
        , capacity_(0)
        , bitScale_(reserve)
        , array_(new T*[reserve_])
    {}
    Set(const Set& arg) : reserve_(arg.reserve_)
        , capacity_(arg.capacity_)
        , bitScale_(arg.bitScale_)
    {
        memcpy(array_, arg.array_, reserve_ * sizeof(T*));
    }

    int capacity() {
        return capacity_;
    }

    void print() {
        bitScale_.print();
    }

    void resize() {
        reserve_ *= 2;
        T **buf = new T*[reserve_];
        memcpy(buf, array_, (reserve_ / 2) * sizeof(T*));
        delete[] array_;
        array_ = buf;
        bitScale_.resize();
    }

    bool hasItem(const T& item)
    {
        return bitScale_.hasBit(item.id);
    }

    template <class T2>
    Set& operator |=(T2&& item)
    {
        while (item.id >= reserve_)
            resize();
        if (!hasItem(item)) capacity_++;
        bitScale_.setBit(item.id);
        array_[item.id] = &item;
        return *this;
    }

    template<>
    Set& operator |=<T>(const Set&& set)
    {
        while (set.reserve_ > reserve_)
            resize();
        bitScale_ |= set.bitScale_;
        capacity_ = countCapacity(bitScale_);
        addItems(set);
        return *this;
    }

    /*
    Set& operator |(int item)
    {
        Set buf = *this;
        buf |= item;
        return buf;
    }
    Set& operator |(const Set& arg)
    {
        Set buf = *this;
        buf |= arg;
        return buf;
    }
    */
    Set& operator -=(T& item)
    {
        if (hasItem(item)) capacity_--;
        bitScale_.clearBit(item.id);
        return *this;
    }

    Set& operator -=(const Set& set)
    {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        capacity_ -= countCapacity(bufBitScale);
        bitScale_ -= set.bitScale_;
        return *this;
    }
    /*
    Set& operator -(const Set& arg)
    {
        Set buf = *this;
        buf -= arg;
        return buf;
    }
    */

    Set& operator &=(const Set & set) {
        bitScale_ &= set.bitScale_;
        capacity_ = countCapacity(bitScale_);
        return *this;
    }
    /*
    Set& operator &=(T& item) {
        Set bufSet();
        bufSet |= item;
        bitScale_ &= bufSet.
        capacity_ = countCapacity(bitScale_);
        return *this;
    }
    */

    bool operator<=(const Set& set) {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        return capacity_ == countCapacity(bufBitScale);
    }

    bool operator>=(const Set& set) {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        return set.capacity_ == countCapacity(bufBitScale);
    }

    bool operator==(const Set& set) {
        return ((*this >= set) && (*this <= set));
    }

    bool operator!=(const Set& set) {
        return !(*this == set);
    }

    template <class T2>
    Set<T2>* map(T2*(*f)(T *item)) {
        Set<T2> bufSet;
        BitScale buf = bitScale_;
        int id;
        using Word = unsigned short;
        Word bufWord;
        for (int i = 0; i < buf.numWords_; i++) {
            bufWord = buf.words_[i];
            for (int j = 0; j < buf.WordBitSize_ - 1; j++) {
                if (bufWord & 1 == 1) {
                    id = i * buf.WordBitSize_ + j;
                    bufSet |= *(f(array_[id]));
                }
                bufWord >>= 1;
            }
        }
        return &bufSet;
    }

private:
    int countCapacity(const BitScale& arg) {
        using Word = unsigned short;
        int count = 0;
        Word buf;
        for (int i = 0; i < arg.numWords_; i++) {
            buf = arg.words_[i];
            for (int j = 0; j < arg.WordBitSize_ - 1; j++) {
                if (buf & 1 == 1)
                    count++;
                buf >>= 1;
            }
        }
        return count;
    }

    void addItems(const Set& set) {
        BitScale buf = set.bitScale_;
        buf -= bitScale_;
        int id;
        using Word = unsigned short;
        Word bufWord;
        for (int i = 0; i < buf.numWords_; i++) {
            bufWord = buf.words_[i];
            for (int j = 0; j < buf.WordBitSize_ - 1; j++) {
                if (bufWord & 1 == 1) {
                    id = i * buf.WordBitSize_ + j;
                    array_[id] = set.array_[id];
                }
                bufWord >>= 1;
            }
        }
    }
};

main.cpp с тестами.

#include <iostream>
#include <bitset>
#include "Set.h"
using namespace std;
typedef unsigned short Word;

struct B;

struct A {
    int id;
    B *b;
};

struct B{
    int id;
};

B* who(A *item) {
    return item->b;
}

int main()

{
    setlocale(LC_ALL, "");
    B b{ 1 };
    B bb{ 2 };
    A a{ 1, &b };
    A aa{ 2, &bb };
    Set<A> set1;
    set1 |= a;

    Set<A> set2;
    set2 |= aa;
    set1 |= set2;   
    Set<B> *set3 = set1.map(who);
    cout << set3->capacity();
    set3->print();
    system("pause>nul");
    return 0;
}

BitScale.cpp

#include <iostream>
#include <stdexcept>
#include <bitset>
#include "BitScale.h"
using namespace std;

const int BitScale::WordBitSize_ = 16;

BitScale::BitScale(int numBits)
{
    numBits_ = numBits;
    numWords_ = (numBits_ + WordBitSize_ - 1) / WordBitSize_;
    words_ = new Word[numWords_];
    memset(words_, 0, numWords_ * sizeof(Word));
}

BitScale::BitScale(const BitScale& arg)
{
    numBits_ = arg.numBits_;
    numWords_ = arg.numWords_;
    words_ = new Word[numWords_];
    memcpy(words_, arg.words_, numWords_ * sizeof(Word));
}

BitScale::~BitScale()
{
    delete[] words_;
}

void BitScale::print()
{
    for (int i = 0; i < numWords_; i++) {
        printf("%-3d) ", i);
        cout << std::bitset<WordBitSize_>(words_[i]) << endl;
    }
}

bool BitScale::hasBit(int bit)
{
    if (bit < 0 || bit >= numBits_) 
        return false;
    return (words_[bit / WordBitSize_] &
        (1 << bit % WordBitSize_)) != 0;
}

BitScale& BitScale::setBit(int bit)
{
    if (bit < 0)
        throw runtime_error("Signed bit.");
    while (bit >= numBits_)
        resize();
    words_[bit / WordBitSize_] |= (1 << bit % WordBitSize_);
    return *this;
}

BitScale& BitScale::clearBit(int bit)
{
    if (bit < 0 || bit >= numBits_)
        return *this;
    words_[bit / WordBitSize_] &= ~(1 << bit % WordBitSize_);
    return *this;
}

BitScale& BitScale::operator=(const BitScale& arg)
{
    numBits_ = arg.numBits_;
    numWords_ = arg.numWords_;
    words_ = new Word[numWords_];
    memcpy(words_, arg.words_, numWords_ * sizeof(Word));
    return *this;
}

BitScale& BitScale::operator |=(const BitScale& arg)
{
    while (numBits_ < arg.numBits_) {
        resize();
    }
    for (int i = 0; i < arg.numWords_; i++)
        words_[i] |= arg.words_[i];
    return *this;
}

BitScale& BitScale::operator &=(const BitScale& arg)
{
    for (int i = 0; i < numWords_; i++)
        words_[i] &= arg.words_[i];
    return *this;
}

BitScale& BitScale::operator -=(const BitScale& arg)
{
    for (int i = 0; i < numWords_; i++)
        words_[i] &= ~arg.words_[i];
    return *this;
}

void BitScale::resize() {
    numBits_ *= 2;
    int lastNum = numWords_;
    numWords_ = (numBits_ + WordBitSize_ - 1) / WordBitSize_;
    Word *bufWords = new Word[numWords_];
    memset(bufWords, 0, numWords_ * sizeof(Word));
    memcpy(bufWords, words_, lastNum * sizeof(Word));
    delete[] words_;
    words_ = bufWords;
}

2 ответа 2

1

Так а что это за "специализация" такая? Что вы хотели сказать этим

template <>
Set& operator |=<T>(const Set&& set)

?

Явная специализация должна соответствовать своему основному шаблону

template <class T2>
Set& operator |=(T2&& item)

У вас в треугольных скобах в специализации явно указано, что специализация делается для типа T2 == T, а в списке параметров функции указано const Set &&, то есть согласно списку параметров специализация делается для T2 == const Set<T>.

Это какая-то сама себе противоречащая белиберда. Для какого значения шаблонного параметраT2 вы хотите сделать специализацию? Для T2 == T или для T2 == const Set<T>? Именно это и не может понять компилятор.

К тому же параметр основного шаблона у вас является "универсальной ссылкой". Параметр вашей специализации выглядит довольно необычно - const Set &&, т.е. rvalue-ссылка на константу. Интересно, какие варианты вызова вашей шаблонной функции вы собираетесь покрыть такой специализацией?

2
  • Я бы хотел, чтобы мой шаблонный оператор мог принимать в качестве параметра: T item - объект типа T, указатель на который можно засунуть в массив указателей T **array_;, и чтобы оператор принимал значения типа Set<T> - множество, хранящее элементы типа T. Поведение этих операторов должно быть различным, т.к. у каждого хранимого элемента есть int id поле, а у самого множества такого поля нет. + нужно реализовать этот шаблонный оператор так, чтобы его можно было удобно применить для добавления в множество в строке bufSet |= *(f(array_[id])). Подскажите пожалуйста, как это правильно реализовать?
    – Chudvan
    15 мая 2019 в 13:42
  • Просто в ф-ю Set<T2>* map(T2*(*f)(T *item)) { может быть передана ф-я, которая выдаёт значения типа T2, отличные от T. Моя задача уметь создавать новое множество Set<T2> из элементов T2 тоже. Позволит ли мне шаблон template <class T> Set& operator |=(T&& item) { ... } объединять множества с новым типом элементов T2? Просто по моей логике, если мы внутри шаблонного класса с типом T, то T - уже фиксированно. Значит, пытаясь выполнить команду bufSet |= *(f(array_[id])) мы получим ошибку, пытаясь добавить эл-ты T2 в массив T...
    – Chudvan
    15 мая 2019 в 14:00
0

Решил вопрос, почитав немного статей про шаблоны в C++. Я действительно, криво пытался реализовать специализацию шаблона, из-за этого программа и не компилировалась.

Кому интересно, что вышло:

Set.h

#pragma once
#include "BitScale.h"

template <class T>
class Set
{
    int reserve_;
    int capacity_;
    BitScale bitScale_;
    T **array_;
public:
    Set(int reserve = 256) :
        reserve_(reserve)
        , capacity_(0)
        , bitScale_(reserve)
        , array_(new T*[reserve_])
    {}

    Set(const Set& arg) : reserve_(arg.reserve_)
        , capacity_(arg.capacity_)
        , bitScale_(arg.bitScale_)
    {
        array_ = new T*[reserve_];
        memcpy(array_, arg.array_, reserve_ * sizeof(T*));
    }

    Set& operator =(const Set& arg)
    {
        reserve_ = arg.reserve_;
        capacity_ = arg.capacity_;
        bitScale_ = arg.bitScale_;
        array_ = new T*[reserve_];
        memcpy(array_, arg.array_, reserve_ * sizeof(T*));
        return *this;
    }

    ~Set() {
        delete[] array_;
    }

    int capacity() {
        return capacity_;
    }

    void print() {
        bitScale_.print();
    }

    void resize() {
        reserve_ *= 2;
        T **buf = new T*[reserve_];
        memcpy(buf, array_, (reserve_ / 2) * sizeof(T*));
        delete[] array_;
        array_ = buf;
        bitScale_.resize();
    }

    bool hasItem(const T& item)
    {
        return bitScale_.hasBit(item.id);
    }

    Set& operator |=(T& item)
    {
        while (item.id >= reserve_)
            resize();
        if (!hasItem(item)) capacity_++;
        bitScale_.setBit(item.id);
        array_[item.id] = &item;
        return *this;
    }

    Set& operator |=(Set& set)
    {
        while (set.reserve_ > reserve_)
            resize();
        addItems(set);
        bitScale_ |= set.bitScale_;
        capacity_ = countCapacity(bitScale_);
        return *this;
    }

    Set& operator -=(T& item)
    {
        if (hasItem(item)) capacity_--;
        bitScale_.clearBit(item.id);
        return *this;
    }

    Set& operator -=(const Set& set)
    {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        capacity_ -= countCapacity(bufBitScale);
        bitScale_ -= set.bitScale_;
        return *this;
    }

    Set& operator &=(const Set & set) {
        bitScale_ &= set.bitScale_;
        capacity_ = countCapacity(bitScale_);
        return *this;
    }

    bool operator<=(const Set& set) {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        return capacity_ == countCapacity(bufBitScale);
    }

    bool operator>=(const Set& set) {
        BitScale bufBitScale;
        bufBitScale = set.bitScale_;
        bufBitScale &= bitScale_;
        return set.capacity_ == countCapacity(bufBitScale);
    }

    bool operator==(const Set& set) {
        return ((*this >= set) && (*this <= set));
    }

    bool operator!=(const Set& set) {
        return !(*this == set);
    }

    template <class T2>
    Set<T2>* map(T2*(*f)(T *item)) {
        Set<T2> *bufSet = new Set<T2>;
        BitScale buf = bitScale_;
        int id;
        using Word = unsigned short;
        Word bufWord;
        for (int i = 0; i < buf.numWords_; i++) {
            bufWord = buf.words_[i];
            for (int j = 0; j < buf.WordBitSize_ - 1; j++) {
                if (bufWord & 1 == 1) {
                    id = i * buf.WordBitSize_ + j;
                    *(bufSet) |= *(f(array_[id]));
                }
                bufWord >>= 1;
            }
        }
        return bufSet;
    }

private:
    int countCapacity(const BitScale& arg) {
        using Word = unsigned short;
        int count = 0;
        Word buf;
        for (int i = 0; i < arg.numWords_; i++) {
            buf = arg.words_[i];
            for (int j = 0; j < arg.WordBitSize_ - 1; j++) {
                if (buf & 1 == 1)
                    count++;
                buf >>= 1;
            }
        }
        return count;
    }

    void addItems(const Set& set) {
        BitScale buf = set.bitScale_;
        buf -= bitScale_;
        int id;
        using Word = unsigned short;
        Word bufWord;
        for (int i = 0; i < buf.numWords_; i++) {
            bufWord = buf.words_[i];
            for (int j = 0; j < buf.WordBitSize_ - 1; j++) {
                if (bufWord & 1 == 1) {
                    id = i * buf.WordBitSize_ + j;
                    array_[id] = set.array_[id];
                }
                bufWord >>= 1;
            }
        }
    }
};

main.cpp с тестами.

#include <iostream>
#include <bitset>
#include "Set.h"
using namespace std;
typedef unsigned short Word;

struct B;

struct A {
    int id;
    B *b;
};

struct B {
    int id;
};

B* who(A *item) {
    return item->b;
}

int main()

{
    setlocale(LC_ALL, "");

    B b{ 1 };
    B bb{ 2 };
    A a{ 1, &b };
    A aa{ 2, &bb };
    Set<A> set1;
    cout << set1.capacity() << endl;
    set1 |= a;
    cout << set1.capacity() << endl;

    Set<A> set2;
    set2 |= aa;
    set1 |= set2;
    cout << set1.capacity() << endl;

    cout << "Has Item?" << endl;
    cout << set1.hasItem(a) << endl;
    cout << set1.hasItem(aa) << endl;

    cout << endl << "Current capacity:" << endl;
    cout << "set1: " << set1.capacity() << endl;
    cout << "set2: " << set2.capacity() << endl;

    cout << endl << "Which subset" << endl;
    cout << "set1 <= set2: " << (set1 <= set2) << endl;
    cout << "set2 <= set1: " << (set2 <= set1) << endl;
    cout << "set2 >= set1: " << (set2 >= set1) << endl;
    cout << "set1 >= set2: " << (set1 >= set2) << endl;
    cout << "set1 == set2: " << (set1 == set2) << endl;
    cout << "set1 != set2: " << (set1 != set2) << endl;

    cout << endl << "Copy constructor" << endl;
    Set<A> set3 = set1;
    cout << "Set<A> set3 = set1" << endl;
    cout << "set1 == set3: " << (set1 == set3) << endl;
    cout << "set1 != set3: " << (set1 != set3) << endl;

    cout << endl << "set3.capacity(): " << set3.capacity() << endl;
    set3 -= set2;
    cout << "set3 -= set2: " << endl;
    cout << "set3.hasItem(a): " << set3.hasItem(a) << endl;
    cout << "set3.hasItem(aa): " << set3.hasItem(aa) << endl;
    cout << "set3.capacity(): " << set3.capacity() << endl;
    cout << "set1.hasItem(a): " << set1.hasItem(a) << endl;
    cout << "set1.hasItem(aa): " << set1.hasItem(aa) << endl;
    cout << "set1.capacity(): " << set1.capacity() << endl;

    cout << endl << "Test map" << endl;
    Set<B> *set4 = set1.map(who);
    cout << "set4->capacity(): " << set4->capacity() << endl;
    cout << "set4->hasItem(b): " << set4->hasItem(b) << endl;
    cout << "set4->hasItem(bb): " << set4->hasItem(bb) << endl;

    cout << endl << "Copy operator=" << endl;
    set3 = set2;
    cout << "set3 = set2" << endl;
    cout << "set3 == set1: " << (set3 == set1) << endl;
    cout << "set3 == set2: " << (set3 == set2) << endl;

    cout << endl << "Difference sets" << endl;
    cout << "set1.capacity(): " << set1.capacity() << endl;
    set1 -= a;
    cout << "set1 -= a: " << endl;
    cout << "set1.hasItem(a): " << set1.hasItem(a) << endl;
    cout << "set1.hasItem(aa): " << set1.hasItem(aa) << endl;
    cout << "set1.capacity(): " << set1.capacity() << endl;
    set1 -= set2;
    cout << "set1 -= set2: " << endl;
    cout << "set1.hasItem(a): " << set1.hasItem(a) << endl;
    cout << "set1.hasItem(aa): " << set1.hasItem(aa) << endl;
    cout << "set1.capacity(): " << set1.capacity() << endl;

    //set4->print();
    //set1 -= set2;

    system("pause>nul");
    return 0;
}

BitScale.cpp - без изменений.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.