2017年11月17日
《その133》 要素数の大きな集合クラス & p.84演習2-8
ビットベクトルによる要素数の大きな集合クラス
自分の使っている処理系では、unsigned char型は 8ビットです。
例えば、この unsigned char型の数値を 6個使用することにすれば、要素数が 6 × 8 ＝ 48個の全体集合を取り扱うことが可能になります。
11000000 00000000 00000000 00000000 00000001 00000011
この場合の全体集合が整数 0 〜 47 であるとすれば、上の例では
0, 1, 8, 46, 47
の要素を保持していることになります。
新版明解C++中級編 p.84 演習2-8
以下の特徴をもつビットベクトルによる集合を実現するクラス VecBitSet型を作成せよ。
・要素数は unsigned long型のビット数に制限されない。
・集合の上限値と加減値を任意の値に設定できる。
たとえば、VecBitSet型の集合 b1 を 10以上 99以下の整数を表せる集合とするのであれば、以下に示す方法で初期化できるように実現すること。
VecBitSet b1(10, 99);
もしも unsigned long型が 32ビットであれば、呼び出されたコンストラクタは、10 から 99 までの 90種類の数値を格納するために、要素数が 3 である unsigned long型の配列 set を動的に確保する。
そうすると、set[0] の各ビットは 10 から 41 までを、set[1] の各ビットは 42 から 73 までを、set[2] の各ビットは 74 から 99 までを格納できる。
基本的な演算を行うための演算子関数を含め、メンバ関数を設計・作成すること。
ここでは、ビット数が 8 の unsigned char型を使って、10 から 69 までの 60種類の数値を格納することにしました。
実現するためには、unsigned char型の 配列 set[0] 〜 set[7] が必要です。
この 演習2-8 に書いてあるような 32ビットの unsigned long型を使って 90種類の数値を格納する仕様に変更するには、プログラム中の型を変更するだけです。そのように仕様を変更したプログラムは、次回《その134》に載せる予定です（今回のプログラムと全く同じものですが・・・）。
演習2-8 では、上図のような状況を仮定しています。
// VecBitSet.h
#ifndef ___Class_VecBitSet
#define ___Class_VecBitSet
class VecBitSet {
static const int BIT = std::numeric_limits<unsigned char>::digits;
int bit_bottom;
int bit_top;
int univ_n; // 全体集合の要素数
int indx_n; // 格納用配列の要素数
unsigned char* set; // 格納用配列 set[]
public:
// x に対応するﾋﾞｯﾄが入っている配列要素の添字を返す。
static int ary_idx(int x) { return x / BIT; }
// x に対応しているのは第何ﾋﾞｯﾄ(0〜15)か。
static int bit_num(int x) { return x - BIT * ary_idx(x); }
/*
◇先ず､ｺﾝｽﾄﾗｸﾀ VecBitSet(int n1, int n2)で bit_bottom, bit_topの値が確定した
ｵﾌﾞｼﾞｪｸﾄを作成し､これを VecBitSetｵﾌﾞｼﾞｪｸﾄの仕様とする。
◇演算に使うVecBitSetｵﾌﾞｼﾞｪｸﾄは､同仕様でなければならないので､全てｺﾋﾟｰｺﾝｽﾄﾗｸﾀ
VecBitSet(const VecBitSet& x)で作成し､作成後に､関数bit_set(int e[], int n)
を用いて具体的な集合要素の値を与える。
*/
VecBitSet(int n1, int n2); // ｺﾝｽﾄﾗｸﾀ
VecBitSet(const VecBitSet& x); // ｺﾋﾟｰｺﾝｽﾄﾗｸﾀ
~VecBitSet() { delete[] set; } // ﾃﾞｽﾄﾗｸﾀ
VecBitSet& operator=(const VecBitSet& x); // 代入演算子=
void bit_set(const int e[], int n); // 集合要素を配列e[]から読み込む。
bool is_valid(int x) const; // 集合要素としての妥当性をﾁｪｯｸ。
void add(int s); // 要素を追加(該当ﾋﾞｯﾄに1をｾｯﾄ)
void remove(int s); // 要素を削除(該当ﾋﾞｯﾄに0をｾｯﾄ)
int* to_array() const; // 集合要素の値を配列に格納。
int size() const; // 集合の要素数
bool contains(int x) const; // 要素であるかどうか。
bool empty() const; // 空集合かどうか。
void reset(); // ﾘｾｯﾄ
int min() const; // 集合要素の最小値
int max() const; // 集合要素の最大値
// 等価演算子==
bool operator==(const VecBitSet& r) const;
// 等価演算子!=
bool operator!=(const VecBitSet& r) const;
// s の部分集合であるか。
bool is_subset_of(const VecBitSet& s) const;
// s の真部分集合であるか。
bool is_proper_subset_of(const VecBitSet& s) const;
// r との和集合に更新
VecBitSet& operator+=(const VecBitSet& r);
// r との積集合に更新
VecBitSet& operator*=(const VecBitSet& r);
// r との差集合に更新
VecBitSet& operator-=(const VecBitSet& r);
// "{ a, b, c }"タイプの文字列を作る。
std::string to_string() const;
// "11000･･･10100"タイプの文字列を作る。
std::string bit_string() const;
};
// 和集合を求める。
VecBitSet operator+(const VecBitSet& s1, const VecBitSet& s2);
// 積集合を求める。
VecBitSet operator*(const VecBitSet& s1, const VecBitSet& s2);
// 差集合を求める。
VecBitSet operator-(const VecBitSet& s1, const VecBitSet& s2);
// 交換
void swap(VecBitSet& s1, VecBitSet& s2);
// 対称差を求める。
VecBitSet symmetric_difference(const VecBitSet& s1, const VecBitSet& s2);
// 挿入子<< の多重定義
std::ostream& operator<<(std::ostream& os, const VecBitSet& x);
#endif
// VecBitSet.cpp
#include <sstream>
#include <iostream>
#include "VecBitSet.h"
using namespace std;
// ｺﾝｽﾄﾗｸﾀ
VecBitSet::VecBitSet(int n1, int n2) : bit_bottom(n1), bit_top(n2) {
univ_n = n2 - n1 + 1;
indx_n = ary_idx(n2 - n1) + 1;
set = new unsigned char[indx_n];
for (int i = 0; i < indx_n; i++)
set[i] = 0; // 全ﾋﾞｯﾄを0にする。
}
// ｺﾋﾟｰｺﾝｽﾄﾗｸﾀ
VecBitSet::VecBitSet(const VecBitSet& x) {
if (&x == this) {
univ_n = 1;
indx_n = 1;
set = new unsigned char[1];
}
else {
bit_bottom = x.bit_bottom;
bit_top = x.bit_top;
univ_n = x.univ_n;
indx_n = x.indx_n;
set = new unsigned char[indx_n];
for (int i = 0; i < indx_n; i++)
set[i] = x.set[i];
}
}
// 代入演算子=
VecBitSet& VecBitSet::operator=(const VecBitSet& x) {
if (&x != this) {
if (indx_n != x.indx_n) {
delete[] set;
indx_n = x.indx_n;
set = new unsigned char[indx_n];
}
bit_bottom = x.bit_bottom;
bit_top = x.bit_top;
univ_n = x.univ_n;
for (int i = 0; i < indx_n; i++)
set[i] = x.set[i];
}
return *this;
}
// 集合要素を配列e[]から読み込む。
void VecBitSet::bit_set(const int e[], int n) {
for (int i = 0; i < n; i++) add(e[i]);
}
// 集合要素としての妥当性をﾁｪｯｸ。
bool VecBitSet::is_valid(int x) const {
return x >= bit_bottom && x <= bit_top;
}
// 要素を追加(該当ﾋﾞｯﾄに1をｾｯﾄ)
void VecBitSet::add(int s) {
if (is_valid(s)) {
s = s - bit_bottom;
set[ary_idx(s)] |= 1 << bit_num(s);
}
}
// 要素を削除(該当ﾋﾞｯﾄに0をｾｯﾄ)
void VecBitSet::remove(int s) {
if (is_valid(s)) {
s = s - bit_bottom;
set[ary_idx(s)] &= ~(1 << bit_num(s));
}
}
// 集合要素の値を配列に格納。
int* VecBitSet::to_array() const {
int* ary = new int[size()];
int v = 0, index = 0;
for (int i = 0; i < indx_n; i++) {
for (int j = 0; j < BIT; j++) {
if (set[i] & 1 << j)
ary[index++] = v + bit_bottom;
v++;
if (v > bit_top - bit_bottom) goto P;
}
}
P:
return ary;
}
// 集合の要素数
int VecBitSet::size() const {
int count = 0, v = 0;
for (int i = 0; i < indx_n; i++) {
for (int j = 0; j < BIT; j++) {
if (set[i] & 1 << j) ++count;
v++;
if (v > bit_top - bit_bottom) goto Q;
}
}
Q:
return count;
}
// 要素であるかどうか。
bool VecBitSet::contains(int x) const {
bool b = false;
if (is_valid(x)) {
x = x - bit_bottom;
b = set[ary_idx(x)] & (1 << bit_num(x)) ? true : false;
}
return b;
}
// 空集合かどうか。
bool VecBitSet::empty() const {
bool f = true;
for (int i = 0; i < indx_n; i++)
if (set[i]) f = false;
return f;
}
// ﾘｾｯﾄ
void VecBitSet::reset() {
for (int i = 0; i < indx_n; i++)
set[i] = 0;
}
// 集合要素の最小値
int VecBitSet::min() const {
int v = bit_top + 1;
int* ary = to_array();
for (int i = 0; i < size(); i++)
if (ary[i] < v) v = ary[i];
delete[] ary;
return (v <= bit_top) ? v : -1;
}
// 集合要素の最大値
int VecBitSet::max() const {
int v = bit_bottom - 1;
int* ary = to_array();
for (int i = 0; i < size(); i++)
if (ary[i] > v) v = ary[i];
delete[] ary;
return (v >= bit_bottom) ? v : -1;
}
// 等価演算子==
bool VecBitSet::operator==(const VecBitSet& r) const {
bool b = true;
for (int i = 0; i < indx_n; i++)
if (set[i] != r.set[i]) b = false;
return b;
}
// 等価演算子 !=
bool VecBitSet::operator!=(const VecBitSet& r) const {
bool b = false;
for (int i = 0; i < indx_n; i++)
if (set[i] != r.set[i]) b = true;
return b;
}
// s の部分集合であるか。
bool VecBitSet::is_subset_of(const VecBitSet& s) const {
VecBitSet temp = *this;
return (temp -= s).empty() ? true : false;
}
// s の真部分集合であるか。
bool VecBitSet::is_proper_subset_of(const VecBitSet& s) const {
VecBitSet temp1 = *this; VecBitSet temp2 = s;
return ((temp1 -= s).empty() && temp2 != *this) ?
true : false;
}
// r との和集合に更新
VecBitSet& VecBitSet::operator+=(const VecBitSet& r) {
for (int i = 0; i < indx_n; i++)
set[i] |= r.set[i];
return *this;
}
// r との積集合に更新
VecBitSet& VecBitSet::operator*=(const VecBitSet& r) {
for (int i = 0; i < indx_n; i++)
set[i] &= r.set[i];
return *this;
}
// r との差集合に更新
VecBitSet& VecBitSet::operator-=(const VecBitSet& r) {
for (int i = 0; i < indx_n; i++)
set[i] &= ~r.set[i];
return *this;
}
// "{ a, b, c }"タイプの文字列を作る。
string VecBitSet::to_string() const {
ostringstream s;
s << "{";
int bit_n = 0, f = 0;
for (int i = 0; i < indx_n; i++) {
for (int j = 0; j < BIT; j++) {
if (set[i] & 1 << j)
if (f == 0) { s << bit_n + bit_bottom; f = 1; }
else s << ", " << bit_n + bit_bottom;
if (++bit_n > bit_top - bit_bottom) goto BREAK;
}
}
BREAK:
s << "}";
return s.str();
}
// "11000･･･10100"タイプの文字列を作る。
string VecBitSet::bit_string() const {
string temp;
int bit_n = 0;
for (int i = 0; i < indx_n; i++) {
for (int j = 0; j < BIT; j++) {
temp = (set[i] & 1U << j ? '1' : '0') + temp;
if (++bit_n > bit_top - bit_bottom) goto BREAK;
}
temp = ' ' + temp;
}
BREAK:
return temp;
}
// 和集合を求める。
VecBitSet operator+(const VecBitSet& s1, const VecBitSet& s2) {
VecBitSet temp(s1);
return temp += s2;
}
// 積集合を求める。
VecBitSet operator*(const VecBitSet& s1, const VecBitSet& s2) {
VecBitSet temp(s1);
return temp *= s2;
}
// 差集合を求める。
VecBitSet operator-(const VecBitSet& s1, const VecBitSet& s2) {
VecBitSet temp(s1);
return temp -= s2;
}
// 交換
void swap(VecBitSet& s1, VecBitSet& s2) {
VecBitSet temp(s1); s1 = s2; s2 = temp;
}
// 対称差を求める。
VecBitSet symmetric_difference(const VecBitSet& s1, const VecBitSet& s2) {
VecBitSet temp1(s1); VecBitSet temp2(s2);
temp1 -= s2; temp2 -= s1;
return temp1 += temp2;
}
// 挿入子<< の多重定義
std::ostream& operator<<(ostream& os, const VecBitSet& x) {
return os << x.to_string();
}
// VecBitSetTest.cpp
#include <iostream>
#include <string>
#include "VecBitSet.h"
using namespace std;
int main() {
VecBitSet b0(10, 69);
int a1[] = { 0, 5, 56, 20, 30, 40, 45, 10, 11, 69, 100 };
int a2[] = { 5, 8, 69, 11, 68, 65, 99 };
int a3[] = { 40, 56 };
VecBitSet b1(b0); b1.bit_set(a1, sizeof(a1) / sizeof(a1[0]));
VecBitSet b2(b0); b2.bit_set(a2, sizeof(a2) / sizeof(a2[0]));
VecBitSet b3(b0); b3.bit_set(a3, sizeof(a3) / sizeof(a3[0]));
VecBitSet b4(b0);
VecBitSet b5(b3);
cout << "b1 = "; cout << b1.bit_string() << '\n';
cout << "b1 = "; cout << b1 << '\n';
cout << "b2 = "; cout << b2 << '\n';
cout << "b3 = "; cout << b3 << '\n';
cout << "b4 = "; cout << b4 << '\n';
cout << "b5 = "; cout << b5 << '\n';
cout << '\n';
cout << "集合b1の最小要素 : " << b1.min() << '\n';
cout << "集合b1の最大要素 : " << b1.max() << '\n';
cout << "集合b4の最小要素 : " << b4.min() << '\n';
cout << "集合b4の最大要素 : " << b4.max() << '\n';
cout << "集合b1の要素数 : " << b1.size() << '\n';
cout << "集合b4の要素数 : " << b4.size() << "\n\n";
VecBitSet temp(b0);
temp = b1;
cout << "temp = "; cout << temp << '\n';
cout << "◇temp.reset();" << '\n';
temp.reset();
cout << "temp = "; cout << temp << '\n';
cout << "◇temp.add(23); temp.add(99);" << '\n';
temp.add(23); temp.add(99);
cout << "temp = "; cout << temp << '\n';
cout << "◇temp.remove(23);" << '\n';
temp.remove(23);
cout << "temp = "; cout << temp << '\n';
cout << '\n';
cout << "◇swap(b1, b2);" << '\n';
swap(b1, b2);
cout << "b1 = "; cout << b1 << '\n';
cout << "b2 = "; cout << b2 << '\n';
cout << "◇swap(b1, b2);" << '\n';
swap(b1, b2);
cout << "b1 = "; cout << b1 << '\n';
cout << "b2 = "; cout << b2 << "\n\n";
cout << "◇symmetric_difference(b1, b2) // 対称差" << '\n';
cout << symmetric_difference(b1, b2) << '\n';
cout << "◇b1 * b2 // 積集合" << '\n';
cout << (b1 * b2) << '\n';
cout << "◇b1 + b2 // 和集合" << '\n';
cout << (b1 + b2) << '\n';
cout << "◇b1 - b2 // 差集合" << '\n';
cout << (b1 - b2) << "\n\n";
cout << "◇b1.is_subset_of(b3) // 部分集合であるかどうか" << '\n';
cout << boolalpha << b1.is_subset_of(b3) << '\n';
cout << "◇b3.is_subset_of(b1)" << '\n';
cout << boolalpha << b3.is_subset_of(b1) << '\n';
cout << "◇b1.is_subset_of(b4)" << '\n';
cout << boolalpha << b1.is_subset_of(b4) << '\n';
cout << "◇b4.is_subset_of(b1)" << '\n';
cout << boolalpha << b3.is_subset_of(b5) << "\n\n";
cout << "◇b3.is_subset_of(b1)" << '\n';
cout << boolalpha << b3.is_subset_of(b5) << "\n\n";
cout << "◇b1.is_proper_subset_of(b3) // 真部分集合であるかどうか" << '\n';
cout << boolalpha << b1.is_proper_subset_of(b3) << '\n';
cout << "◇b3.is_proper_subset_of(b1)" << '\n';
cout << b3.is_proper_subset_of(b1) << '\n';
cout << "◇b1.is_proper_subset_of(b4)" << '\n';
cout << b1.is_proper_subset_of(b4) << '\n';
cout << "◇b4.is_proper_subset_of(b1)" << '\n';
cout << b4.is_proper_subset_of(b1) << '\n';
cout << "◇b3.is_proper_subset_of(b5)" << '\n';
cout << b3.is_proper_subset_of(b5) << "\n\n";
cout << "◇b1 == b2 // 等しいか" << '\n';
cout << (b1 == b2) << '\n';
cout << "◇b1 == b4" << '\n';
cout << (b1 == b4) << '\n';
cout << "◇b3 == b5" << '\n';
cout << (b3 == b5) << "\n\n";
cout << "◇b1 != b2 // 等しくないか" << '\n';
cout << (b1 != b2) << '\n';
cout << "◇b1 != b4" << '\n';
cout << (b1 != b4) << '\n';
cout << "◇b3 != b5" << '\n';
cout << (b3 != b5) << "\n\n";
cout << "◇b1.empty() // 空集合か" << '\n';
cout << b1.empty() << '\n';
cout << "◇b4.empty()" << '\n';
cout << b4.empty() << "\n\n";
cout << "◇b1.contains(60) // 含まれるか" << '\n';
cout << b1.contains(60) << '\n';
cout << "◇b1.contains(56)" << '\n';
cout << b1.contains(56) << "\n\n";
cout << "◇((b1 - b3 + b2) + b3) * b3" << '\n';
cout << ((b1 - b3 + b2) + b3) * b3 << '\n';
cout << "◇b1 - (b1 - b2) * b3 + (b2 - b1)" << '\n';
cout << b1 - (b1 - b2) * b3 + (b2 - b1) << '\n';
}
出力結果と見比べるのに使えるので、最初の図をもう一度ここに載せておきます。
 | 新品価格 |  | 新品価格 |
この記事へのコメント
コメントを書く
この記事へのトラックバックURL
https://fanblogs.jp/tb/6979640
※ブログオーナーが承認したトラックバックのみ表示されます。
この記事へのトラックバック
