Множество. Реализация на битовых векторах

Общие сведения

Множество (англ. set) — тип данных, позволяющий хранить ограниченный набор значений и отвечать на вопрос о принадлежности некоторого значения данному набору. Как правило, каждое допустимое значение может входить в множество не более одного раза, хотя возможны исключения, когда множество хранит несколько одинаковых значений (в этом случае для обозначеня АТД применяют термин «мультимножество», англ. multiset).

Интерфейс

Минимальный набор функций, обеспечиваемый множеством, содержит следующие операции:

void insert(T value)	— добавление значения value в множество;
void remove(T value)	— исключение значения value из множества;
bool contains(T value)	— проверка на вхождение значения value в множество.

Различные реализации могут также содержать математические операции для множеств (объединение, пересечение и т. д.), поддерживать элементы множества в упорядоченном виде, возвращать количество элементов в множестве (и поддерживать операцию isEmpty()) и т. п.

Демонстрация работы

Демонстрация работы можества, реализованного на битовом векторе

Реализация

Использование логического массива

В тех случаях, когда диапазон значений для множества сравнительно мал, становится возможным определить для каждого допустимого значения отдельную переменную, которая будет указывать на то, содержится ли соответствующее ей значение в множестве. Пусть, например, необходимо реализовать множество строчных латинских символов и десятичных цифр. Так как общее число различных элементов равно 36, для каждого из них можно выделить отдельную логическую переменную. Значение «истина» такой переменной будет свидетельствовать о присутствии соответствующего символа в множестве, значение «ложь» — об его отсутствии.

Работу с большим количеством логических переменных проще организовать, если они представлены в виде массива, но в этом случае необходимо установить взаимно однозначное соответствие между индексами переменных в массиве и значениями в множестве (иными словами, ввести отношение порядка между значениями множества). В нашем примере определим это соответствие следующим образом: пусть нулевой элемент в массиве соответствует символу 'a', первый — символу 'b', ..., 25-й — символу 'z', 26-й — символу '0', 27-й — символу '1', ..., 35-й — символу '9'. В предположении, что в выбранной кодировке символы латинского алфавита и цифры расположены последовательно, мы получаем правило определения переменной, соответствующей символу ch: эта переменная имеет индекс (ch - 'a'), если ch является буквой, либо (26 + ch - '0'), если ch является цифрой.

Вышеприведённые соображения позволяют реализовать множество строчных латинских символов следующим образом:

class Set {

    bool a[36];

public:

    Set() {
        for (int i = 0; i < 36; i++)
            a[i++] = false;
    }

    void insert(char value) {
        int index = (value >= 'a' && value <= 'z' ? value - 'a' : 26 + value - '0');
        a[index] = true;
    }

    void remove(char value) {
        int index = (value >= 'a' && value <= 'z' ? value - 'a' : 26 + value - '0');
        a[index] = false;
    }            

    bool contains(char value) {
        int index = (value >= 'a' && value <= 'z' ? value - 'a' : 26 + value - '0');
        return a[index];
    }

};

Однако данная реализация имеет существенный недостаток: так как sizeof(bool) ≥ sizeof(char), массив логических переменных занимает не менее 36 байт = 288 бит, тогда как каждая переменная несёт 1 бит информации, так что весь массив требует 36 бит.