stx::bag<Key,Compare,Allocator>
‘bag’について
‘bag’とはmultisetとmapの’あいのこ’です。multisetは要素の重複を許します。たとえば、
multiset<int> ints; for ( int i = 0; i < 1000; ++i ) ints.insert(1);
このコードでは、intsの中に1が1000個格納されます。
ここに紹介するクラス’bag’は要素とその個数を管理することにより、格納される要素の個数を最小限に抑えるコンテナです。
bagによる金種計算プログラムを書いてみました。
/*
* bag demonstration : 金種計算
*/
#include <iostream> // cout, endl
#include <iomanip> // setw
#include <set> // set<T>
#include "bag" // bag<T>
using namespace std;
using namespace stx;
int main() {
set<int> cash;
cash.insert(10000); // 1万円札
cash.insert( 5000); // 5千円札
//cash.insert( 2000); // 2千円札
cash.insert( 1000); // 千円札
cash.insert( 500); // 5百円玉
cash.insert( 100); // 百円玉
cash.insert( 50); // 50円玉
cash.insert( 10); // 10円玉
cash.insert( 5); // 5円玉
cash.insert( 1); // 1円玉
bag<int> kind;
while ( true ) {
int price;
cout << "金額を入力してください (0 で終了) :" << flush;
cin >> price;
if ( price <= 0 ) break;
for ( set<int>::reverse_iterator it = cash.rbegin();
it != cash.rend(); ++it ) {
int n = price / *it;
price %= *it;
kind.insert_n(n, *it);
if ( n > 0 ) cout << setw(5) << *it << " : "
<< setw(3) << n << endl;
}
}
cout << "総計..." << endl;
for ( set<int>::reverse_iterator it = cash.rbegin();
it != cash.rend(); ++it ) {
cout << setw(5) << *it << " : "
<< setw(3) << kind.count(*it) << endl;
}
return 0;
}
コンストラクタ
explicit bag(const Compare& comp =Compare(), const Allocator& alloc =Allocator());
デフォルトコンストラクタ。
// sample bag<string> b; int n = b.size(); // n = 0
template<class InputIterator> bag(InputIterator first, InputIterator last, const Compare& comp=Compare(), const Allocator& alloc =Allocator());
シーケンス[first,last)からなるbagを作ります。
// sample
string s = "hello";
bag<char> b(s.begin(), s.end()); // b = { e h l l o }
bag(const bag& x);
コピーコンストラクタ。 x の全要素がコピーされます。
// sample
bag<string> b1;
b1.insert_n(2,"apple");
b1.insert("banana"); // b1 = { apple apple banana }
bag<string> b2(b1);// b2 = { apple apple banana }
デストラクタ
~bag();
デストラクタ。 全要素を廃棄します。
コピー
bag& operator=(const bag& x );
全要素を廃棄し、新たに x の全要素がコピーされます。
// sample
bag<string> b1;
bag<string> b2;
b1.insert_n(2,"apple");
b1.insert("banana"); // b1 = { apple apple banana }
b2 = b1;// b2 = { apple apple banana }
イテレータ
iterator begin(); const_iterator begin() const;
最初の要素を指すイテレータを返します。
iterator end(); const_iterator end() const;
最後の要素の直後を指すイテレータを返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
bag<string>::iterator i = b.begin();
while ( i != b.end() ) { // output : apple apple banana
cout << *i << ' ';
++i;
}
reverse_iterator rbegin(); const_reverse_iterator rbegin() const;
最後の要素の直後を指す反転イテレータを返します。
reverse_iterator rend(); const_reverse_iterator rend() const;
最初の要素を指す反転イテレータを返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
bag<string>::reverse_iterator i = b.rbegin();
while ( i != b.rend() ) { // output : banana apple apple
cout << *i << ' ';
++i;
}
empty / size / max_size
bool empty() const;
要素数が 0 なら true を返します。
// sample
bag<string> b;
bool t0 = b.empty(); // t0 = true
b.insert("apple");
bool t1 = b.empty(); // t1 = false
size_type size() const;
要素数を返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("banana");
int s = b.size(); // s = 3
size_type max_size() const;
格納できる最大要素数を返します。
insert
void insert_n(iterator position, size_type n, const key_type& x);
要素 x を n 個追加します。 position に意味はありません。
// sample bag<string> b; b.insert_n(b.begin(), 5, "apple"); // "apple"を5個追加 int s = b.size() // s = 5
void insert(iterator position, const key_type& x);
要素 x を 1 個追加します。 position に意味はありません。
// sample bag<string> b; b.insert(b.begin(), "apple"); // "apple"を1個追加 int s = b.size() // s = 1
void insert_n(size_type n, const key_type& x);
要素 x を n 個追加します。
// sample bag<string> b; b.insert_n(5, "apple"); // "apple"を5個追加 int s = b.size() // s = 5
void insert(const key_type& x);
要素 x を 1 個追加します。
// sample
bag<string> b;
b.insert("apple"); // "apple"を1個追加
int s = b.size() // s = 1
template<class InputIterator> void insert(InputIterator first, InputIterator last);
シーケンス[first,last)を追加します。
// sample
string s = "hello";
bag<char> b;
b.insert(s.begin(), s.end()); // b = { e h l l o }
erase / clear / swap
void erase(iterator position);
position が指す要素を削除します。
// sample bag<string> b; b.insert_n(3,"apple"); b.erase(b.begin()); // 最初の要素を削除 int s = b.size(); // s = 2
size_type erase_all(const key_type& x);
x と等しい要素をすべて削除します。 削除した数を返します。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase_all("apple"); // "apple"をすべて削除
int n = b.count("apple"); // n = 0
size_type erase_n(size_type n, const key_type& x);
x と等しい要素を最大 n 個削除します。 削除した数を返します。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase_n(2,"apple"); // "apple"を2個削除
int n = b.count("apple"); // n = 1
size_type erase(const key_type& x);
x と等しい要素を最大 1 個削除します。 削除した数を返します。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.erase("apple"); // "apple"を1個削除
int n = b.count("apple"); // n = 2
void erase(iterator first, iterator last);
シーケンス[first,last)を削除します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
bag<string>::iterator f = b.find("banana");
bag<string>::iterator l = b.find("cherry"); ++l; // [f,l) = { banana banana cherry }
b.erase(f,l); // b = { apple apple cherry }
void clear();
全要素を削除します。erase(begin(), end()) と等価です。
// sample
bag<string> b;
b.insert("apple");
b.insert("banana"); // b = { apple banana }
b.clear(); // b = { }
int s = b.size(); // s = 0
void swap(bag& x);
*this と x の全要素を交換します。
// sample
bag<string> b1;
b1.insert_n("apple"); // b1 = { apple apple }
bag<string> b2;
b2.insert_n("banana"); // b2 = { banana banana }
b1.swap(b2); // b1 = { banana banana } , b2 = { apple apple }
replace / unique / unique_copy
bool replace(const key_type& x);
x と等しい要素を x に置き換えます。x と等しい要素がないときは false を返します。
// sample
struct abs_less : binary_function<int,int,bool> {
// 絶対値で比較
bool operator()(int x, int y) const
{ return abs(x) < abs(y); }
};
bag<int,abs_less> b;
b.insert(1);
b.insert(2);
b.insert(-2); // b = { 1 2 2 }
b.replace(-2); // b = { 1 -2 -2 }
bool unique(const key_type& x);
x と等しい要素の個数を 1 にします。x と等しい要素がないときは false を返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple apple banana }
b.unique("apple"); // b = { apple banana }
int n = b.count("apple"); // n = 1
void unique();
全要素の個数を 1 にします。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
b.unique(); // b = { apple banana }
int s = b.size(); // s = 2
template<class OutputIterator> OutputIterator unique_copy(OutputIterator result) const;
unique()の結果が [result,RET) にコピーされます(*thisの内容は変化しません)。RETはこの関数の戻り値です。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
vector<string> v;
b.unique_copy(back_inserter(v)); // v = { apple banana }
count / entries / find /lower_bound / upper_bound / equal_range
size_type count(const key_type& x) const;
x と等しい要素の個数を返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple apple banana }
int n = b.count("apple"); // n = 3
size_type entries() const;
互いに異なる要素の個数を返します。
// sample
bag<string> b;
b.insert_n(3,"apple");
b.insert("banana"); // b = { apple apple apple banana }
int n = b.entries(); // n = 2
iterator find(const key_type& x) const;
x と等しい要素を指すイテレータを返します。見つからないときはend()を返します。
// sample
bag<string> b;
b.insert("apple");
b.insert("apple");
b.insert("banana"); // b = { apple apple banana }
bag<string>::iterator i = b.find("apple"); // *i = apple
if ( i != b.end() ) cout << *i << endl;
iterator lower_bound(const key_type& x) const;
x より小さくない最初の要素を指すイテレータを返します。
iterator upper_bound(const key_type& x) const;
x より大きい最初の要素を指すイテレータを返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
bag<string>::iterator l = b.lower_bound("banana"); // *l = banana
bag<string>::iterator u = b.upper_bound("banana"); // *u = cherry
// [l,u) = { banana banana }
std::pair<iterator,iterator> equal_range(const key_type& x) const;
lower_bound(x), upper_boud(x)の組を返します。
// sample
bag<string> b;
b.insert_n(2,"apple");
b.insert_n(2,"banana");
b.insert_n(2,"cherry"); // b = { apple apple banana banana cherry cherry }
std::pair<bag<string>::iterator,bag<string>::iterator> r
= b.equal_range("banana");
// [r.first, r.second) = { banana banana }
ソースコード
#ifndef __STX_BAG_H__
#define __STX_BAG_H__
/*
* 'bag' class template
*
* Microsoft Visual C++ v6.0
* でのコンパイル/実行を確認した。
*
* επιστημη
*/
#include <set>
namespace stx {
template<class Key, class Compare=std::less<Key>, class Allocator=std::allocator<std::pair<Key,size_t> > >
class bag {
public:
typedef Key key_type;
typedef key_type value_type;
private:
/* bag<Key> はその内部に set< pair<Key,size_t> > を内包することで要素とその個数を管理する。
* このとき、set< pair<Key,size_t> > に与える比較オブジェクトは
* pair<Key,size_t>.first すなわち Key を比較対象としなければならない。
*/
struct bag_compare {
Compare comp;
bag_compare(Compare c)
: comp(c) {}
typename Compare::result_type operator()(const std::pair<Key,size_t>& x, const std::pair<Key,size_t>& y) const
{ return comp(x.first, y.first); }
};
public:
typedef std::set<std::pair<Key,size_t>, bag_compare, Allocator> container;
typedef container::difference_type difference_type;
// const_iterator
class const_iterator : public std::iterator<std::bidirectional_iterator_tag, key_type,difference_type> {
friend bag;
container::const_iterator i;
size_t c;
explicit const_iterator(container::const_iterator ci, size_t cc)
: i(ci), c(cc) {}
public:
const_iterator()
{}
const_iterator(const const_iterator& it)
: i(it.i), c(it.c) {}
const value_type& operator*() const
{ return i->first; }
const value_type* operator->() const
{ return &(i->first); }
const_iterator& operator++()
{ if ( i->second <= c ) { ++i; c = 1; } else ++c; return *this; }
const_iterator operator++(int)
{ const_iterator tmp(*this); ++(*this); return tmp; }
const_iterator& operator--()
{ if ( c <= 1 ) { --i; c = i->second; } else --c; return *this; }
const_iterator operator--(int)
{ const_iterator tmp(*this); --(*this); return tmp; }
bool operator==(const const_iterator& x) const
{ return i == x.i && c == x.c; }
bool operator!=(const const_iterator& x) const
{ return i != x.i || c != x.c; }
};
// const_reverse_iteartor
class const_reverse_iterator : std::iterator<std::bidirectional_iterator_tag,key_type,difference_type> {
friend bag;
container::const_iterator i;
size_t c;
explicit const_reverse_iterator(container::const_iterator ci, size_t cc)
: i(ci), c(cc) {}
public:
const_reverse_iterator()
{}
const_reverse_iterator(const const_reverse_iterator& it)
: i(it.i), c(it.c) {}
const value_type& operator*()
{ const_reverse_iterator tmp(*this); ++tmp; return tmp.i->first; }
const value_type* operator->()
{ const_reverse_iterator tmp(*this); ++tmp; return &tmp.i->first; }
const_reverse_iterator& operator++()
{ if ( c <= 1 ) { --i; c = i->second; } else --c; return *this; }
const_reverse_iterator operator++(int)
{ const_reverse_iterator tmp(*this); ++(*this); return tmp; }
const_reverse_iterator& operator--()
{ if ( i->second <= c ) { ++i; c = 1 } else ++c; return *this; }
const_reverse_iterator operator--(int)
{ const_reverse_iterator tmp(*this); --(*this); return tmp; }
bool operator==(const const_reverse_iterator& x) const
{ return i == x.i && c == x.c; }
bool operator!=(const const_reverse_iterator& x) const
{ return i != x.i || c != x.c; }
};
// iterator / reverse_iterator
/* イテレータを介してbag内の要素を書き換えることは(要素の大小関係を狂わせるので)許されない。
* したがって、const_iterator / reverse_const_iterator のみを定義し、
* iterator / reverse_iterator は それぞれ
* const_iterator / reverse_const_iterator の typedef である。
*/
typedef const_iterator iterator;
typedef const_reverse_iterator reverse_iterator;
// types:
typedef container::key_compare key_compare;
typedef container::value_compare value_compare;
typedef container::allocator_type allocator_type;
typedef container::reference reference;
typedef container::const_reference const_reference;
typedef container::size_type size_type;
// constructor/copy/destroy:
explicit bag(const Compare& comp =Compare(), const Allocator& alloc =Allocator())
: c(value_compare(comp),alloc) {}
template<class InputIterator>
bag(InputIterator first, InputIterator last, const Compare& comp=Compare(), const Allocator& alloc =Allocator())
: c(value_compare(comp),alloc) { for ( ;first != last; ++first ) insert(*first); }
bag(const bag& x)
{ c = x.c; }
bag& operator=(const bag& x )
{ c = x.c; return *this; }
~bag()
{}
allocator_type get_allocator() const
{ return c.get_allocator(); }
// iterators:
iterator begin()
{ return iterator(c.begin(),1); }
const_iterator begin() const
{ return const_iterator(c.begin(),1); }
reverse_iterator rbegin()
{ return reverse_iterator(c.end(),1); }
const_reverse_iterator rbegin() const
{ return const_reverse_iterator(c.end(),1); }
iterator end()
{ return iterator(c.end(),1); }
const_iterator end() const
{ return const_iterator(c.end(),1); }
reverse_iterator rend()
{ return reverse_iterator(c.begin(),1); }
const_reverse_iterator rend() const
{ return const_reverse_iterator(c.end(),1); }
// capacity:
bool empty() const
{ return c.empty(); }
/* 以下の実装では、size() の時間計算量が O(N)となり、望ましくない...
*/
size_type size() const
{ size_type n = 0;
for ( container::iterator it = c.begin(); it != c.end(); ++it )
n += it->second;
return n;
}
size_type max_size() const
{ return c.max_size(); }
// insert:
void insert_n(iterator position, size_type n, const key_type& x)
{ if ( n == 0 ) return;
container::key_type tmp(x,n);
container::iterator it = c.find(tmp);
if ( it == c.end() ) c.insert(position.i, tmp);
else const_cast<size_t&>(it->second) += n;
}
void insert(iterator position, const key_type& x)
{ insert_n(position, 1, x); }
void insert_n(size_type n, const key_type& x)
{ insert_n(begin(), n, x); }
void insert(const key_type& x)
{ insert_n(begin(), 1, x); }
template<class InputIterator>
void insert(InputIterator first, InputIterator last)
{ for ( ;first != last; ++first ) insert(*first); }
// erase:
/* stdc++ では set::erase(iterator) の戻り値は void であるため、
* 以下の実装は誤りである...
*
* iterator erase(iterator position)
* { container::iterator it = position.i;
* if ( it->second <= 1 ) { it = c.erase(it); return iterator(it,1); }
* else { --const_cast<size_t&>(it->second); ++position; }
* return position;
* }
*/
void erase(iterator position)
{ container::iterator it = position.i;
if ( it->second <= 1 ) c.erase(it);
else --const_cast<size_t&>(it->second);
}
size_type erase_all(const key_type& x)
{ size_type n = 0;
container::iterator it = c.find(container::value_type(x,1));
if ( it != c.end() ) { n = it->second; c.erase(it); }
return n;
}
size_type erase_n(size_type n, const key_type& x)
{ if ( n == 0 ) return 0;
container::iterator it = c.find(container::value_type(x,1));
if ( it != c.end() ) {
size_type t = it->second;
if ( t <= n ) { c.erase(it); n = t; }
else const_cast<size_t&>(it->second) -= n;
}
return n;
}
size_type erase(const key_type& x)
{ return erase_n(1,x); }
/* stdc++ では set::erase(iterator) の戻り値は void であるため、
* 以下の実装は誤りである...
*
* void erase(iterator first, iterator last)
* { while ( first != last ) first = erase(first); }
*/
void erase(iterator first, iterator last)
{ container tmp(c.key_comp(), c.get_allocator());
container::iterator i;
for( ; first != last; ++first ) {
container::value_type v(*first,1);
i = tmp.find(v);
if ( i == tmp.end() ) tmp.insert(v);
else ++const_cast<size_t&>(i->second);
}
for ( i = tmp.begin(); i != tmp.end(); ++i )
erase(i->second, i->first);
}
// other modifiers:
void swap(bag& x)
{ c.swap(x.c); }
void clear()
{ c.clear(); }
// observers:
key_compare key_comp() const
{ return c.key_comp(); }
value_compare value_comp() const
{ return c.value_comp(); }
// bag operations:
bool replace(const key_type& x)
{ container::iterator it = c.find(container::key_type(x,1));
if ( it != c.end() ) const_cast<key_type&>(it->first) = x;
return it != c.end();
}
void unique()
{ for ( container::iterator it = c.begin(); it != c.end(); ++it )
const_cast<size_t&>(it->second) = 1;
}
template<class OutputIterator>
OutputIterator unique_copy(OutputIterator result) const
{ for ( container::const_iterator it = c.begin(); it != c.end(); ++it ) {
*result = it->first;
++result;
}
return result;
}
size_type count(const key_type& x) const
{ container::const_iterator it = c.find(container::value_type(x,1));
return it == c.end() ? 0 : it->second;
}
size_type entries() const
{ return c.size(); }
iterator find(const key_type& x) const
{ return iterator(c.find(container::value_type(x,1)),1); }
iterator lower_bound(const key_type& x) const
{ return iterator(c.lower_bound(container::value_type(x,1)),1); }
iterator upper_bound(const key_type& x) const
{ return iterator(c.upper_bound(container::value_type(x,1)),1); }
std::pair<iterator,iterator>
equal_range(const key_type& x) const
{ std::pair<container::iterator,container::iterator> r = c.equal_range(container::value_type(x,1));
return std::pair<iterator,iterator>(iterator(r.first,1),iterator(r.second,1));
}
// rel-ops:
friend bool operator==(const bag& x, const bag& y)
{ return x.c == y.c; }
friend bool operator!=(const bag& x, const bag& y)
{ return x.c != y.c; }
friend bool operator<(const bag& x, const bag& y)
{ return x.c < y.c; }
friend bool operator<=(const bag& x, const bag& y)
{ return x.c <= y.c; }
friend bool operator>(const bag& x, const bag& y)
{ return x.c > y.c; }
friend bool operator>=(const bag& x, const bag& y)
{ return x.c >= y.c; }
// swap:
friend void swap(bag& x, bag& y)
{ x.c.swap(y.c); }
protected:
container c;
};
}
#endif