hamigaki.png
前のページ 上に戻る ホーム 次のページ

Class template xor_list

hamigaki::xor_list —

XOR連結リストを表現するクラス。

Synopsis

template<typename T, typename Allocator = std::allocator<T> > 
class xor_list {
public:
  // types
  typedef typename Allocator::reference         reference;             
  typedef typename Allocator::const_reference   const_reference;       
  typedef implementation defined                iterator;              
  typedef implementation defined                const_iterator;        
  typedef implementation defined                size_type;             
  typedef implementation defined                difference_type;       
  typedef T                                     value_type;            
  typedef Allocator                             allocator_type;        
  typedef typename Allocator::pointer           pointer;               
  typedef typename Allocator::const_pointer     const_pointer;         
  typedef std::reverse_iterator<iterator>       reverse_iterator;      
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  // construct/copy/destruct
  explicit xor_list(const Allocator& = Allocator());
  explicit xor_list(size_type, const T& = T(), const Allocator& = Allocator());
  template<typename InputIterator> 
    xor_list(InputIterator, InputIterator, const Allocator& = Allocator());
  xor_list(const xor_list<T,Allocator>&);
  xor_list<T,Allocator>& operator=(const xor_list<T,Allocator>&);
  ~xor_list();
  template<typename InputIterator> void assign(InputIterator, InputIterator);
  void assign(size_type, const T&);
  allocator_type get_allocator() const;

  // iterators
  iterator begin();
  const_iterator begin() const;
  iterator end();
  const_iterator end() const;
  reverse_iterator rbegin();
  const_reverse_iterator rbegin() const;
  reverse_iterator rend();
  const_reverse_iterator rend() const;

  // capacity
  bool empty() const;
  size_type size() const;
  size_type max_size() const;
  void resize(size_type, const T& = T());

  // element access
  reference front();
  const_reference front() const;
  reference back();
  const_reference back() const;

  // modifiers
  void push_front(const T&);
  void pop_front();
  void push_back(const T&);
  void pop_back();
  iterator insert(iterator, const T&);
  void insert(iterator, size_type, const T&);
  template<typename InputIterator> 
    void insert(iterator, InputIterator, InputIterator);
  iterator erase(iterator);
  iterator erase(iterator, iterator);
  void swap(xor_list<T,Allocator>&);
  void clear();

  // list operations
  void splice(iterator, xor_list<T,Allocator>&);
  void splice(iterator, xor_list<T,Allocator>&, iterator);
  template<typename InputIterator> 
    void splice(iterator, xor_list<T,Allocator>&, InputIterator, 
                InputIterator);
  void remove(const T&);
  template<typename Predicate> void remove_if(Predicate);
  void unique();
  template<typename BinaryPredicate> void unique(BinaryPredicate);
  void merge(xor_list<T,Allocator>&);
  template<typename Compare> void merge(xor_list<T,Allocator>&, Compare);
  void sort();
  template<typename Compare> void sort(Compare);
  void reverse();
};

// comparisons
template<typename T, typename Allocator> 
  bool operator==(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);
template<typename T, typename Allocator> 
  bool operator<(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);
template<typename T, typename Allocator> 
  bool operator!=(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);
template<typename T, typename Allocator> 
  bool operator>(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);
template<typename T, typename Allocator> 
  bool operator>=(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);
template<typename T, typename Allocator> 
  bool operator<=(const xor_list<T,Allocator>&, const xor_list<T,Allocator>&);

// specialized algorithms
template<typename T, typename Allocator> 
  void swap(xor_list<T,Allocator>&, xor_list<T,Allocator>&);

Description

xor_list construct/copy/destruct

  1. explicit xor_list(const Allocator& a = Allocator());
    Effects: 空のリストを構築する。
    Postconditions: get_allocator() == a
    Complexity: 定数時間 
  2. explicit xor_list(size_type n, const T& value = T(), 
                  const Allocator& a = Allocator());
    Effects: 割付け子 a を用いてコピーした n 個の value からなるリストを構築する。
    Postconditions: n == 0 なら get_allocator() == a
    Complexity: n に比例する。 
  3. template<typename InputIterator> 
  xor_list(InputIterator first, InputIterator last, 
           const Allocator& a = Allocator());
    Effects: 割付け子 a を用いて区間 [first, last) をコピーした要素からなるリストを構築する。
    Postconditions: first == last なら get_allocator() == a
    Complexity: std::distance(first, last) に比例する。 
  4. xor_list(const xor_list<T,Allocator>& x);
    Complexity: 定数時間 
  5. xor_list<T,Allocator>& operator=(const xor_list<T,Allocator>& x);
    Complexity: 線形時間 
  6. ~xor_list();
    Complexity: 線形時間 
template<typename InputIterator> 
  void assign(InputIterator first, InputIterator last);
Effects: 
erase(begin(), end());
insert(begin(), first, last);

void assign(size_type n, const T& value);
Effects: 
erase(begin(), end());
insert(begin(), n, value);

allocator_type get_allocator() const;
Complexity: 定数時間

xor_list iterators

  1. iterator begin();
const_iterator begin() const;
    Returns: 先頭要素を指す反復子。そのような要素が存在しない場合はend()
    Complexity: 定数時間 

  2. iterator end();
const_iterator end() const;
    Returns: 末尾要素の次を指す反復子
    Complexity: 定数時間 

  3. reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
    Returns: reverse_iterator(end())
    Complexity: 定数時間 

  4. reverse_iterator rend();
const_reverse_iterator rend() const;
    Returns: reverse_iterator(begin())
    Complexity: 定数時間

xor_list capacity

  1. bool empty() const;
    Returns: リストに要素が存在しなければtrue。存在すればfalse。
    Complexity: 定数時間 
  2. size_type size() const;
    Returns: リスト中の要素数
    Complexity: 線形時間
    Notes: Hamigaki.XOL_Listでは要素数をメンバとして保持しないため、線形時間を要する。 
  3. size_type max_size() const;
    Returns: リストに格納できる要素の最大数
    Complexity: 定数時間 
  4. void resize(size_type sz, const T& c = T());
    Effects: 
    if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size()) {
  iterator i = begin();
  advance(i, sz);
  erase(i, end());
}
else
    ; // 何もしない

xor_list element access

  1. reference front();
    Returns: *begin()
    Throws: なし
    Complexity: 定数時間 
  2. const_reference front() const;
    Returns: *begin()
    Throws: なし
    Complexity: 定数時間 
  3. reference back();
    Returns: *--end()
    Throws: なし
    Complexity: 定数時間 
  4. const_reference back() const;
    Returns: *--end()
    Throws: なし
    Complexity: 定数時間

xor_list modifiers

  1. void push_front(const T& x);
    Effects: 
    insert(begin(), x);
    Complexity: 定数時間 
  2. void pop_front();
    Effects: 
    erase(begin());
    Throws: なし
    Complexity: 定数時間 
  3. void push_back(const T& x);
    Effects: 
    insert(end(), x);
    Complexity: 定数時間 
  4. void pop_back();
    Effects: 
    erase(--end());
    Throws: なし
    Complexity: 定数時間 
  5. iterator insert(iterator position, const T& x);
    Effects: position の前に x のコピーを挿入する。position とその一つ前の反復子が無効になる。
    Returns: 挿入された要素を指す反復子
    Complexity: 定数時間 
  6. void insert(iterator position, size_type n, const T& x);
    Effects: position の前に x のコピーを n 個挿入する。position とその一つ前の反復子が無効になる。
    Complexity: n に比例する。 
  7. template<typename InputIterator> 
  void insert(iterator position, InputIterator first, InputIterator last);
    Requires: first と last は *this の反復子ではない。
    Effects: position の前に区間 [first, last) の要素のコピーを挿入する。position とその一つ前の反復子が無効になる。
    Complexity: std::distance(first, last) に比例する。 
  8. iterator erase(iterator position);
    Effects: position の指す要素を削除する。position とその一つ前の反復子が無効になる。
    Returns: 削除された要素の次の要素を指す反復子。そのような要素が存在しない場合は end()。また、削除された要素への参照が無効になる。
    Throws: なし
    Complexity: 定数時間 
  9. iterator erase(iterator position, iterator last);
    Effects: 区間 [position, last) の要素を削除する。position != begin() ならば区間 [--position, last] の反復子が無効になる。それ以外の場合は区間 [position, last] の反復子が無効になる。また、削除された要素への参照が無効になる。
    Returns: 削除前に last の指していた要素を指す反復子。そのような要素が存在しない場合は end()。
    Throws: なし
    Complexity: std::distance(position, last) に比例する。 
  10. void swap(xor_list<T,Allocator>& x);
    Effects: *this と x の要素を交換する。get_allocator() == x.get_allocator() ならば、*this と x の要素を指す参照、ポインタ、反復子は無効にならない。それ以外の場合は参照、ポインタ、反復子すべてが無効になる。
    Throws: get_allocator() == x.get_allocator() ならば例外は送出されない。
    Complexity: get_allocator() == x.get_allocator() ならば定数時間。それ以外の場合は size() + x.size() に比例する。 
  11. void clear();
    Effects: リスト中のすべての要素を削除する。リスト中の要素を指す参照、ポインタ、反復子はすべて無効になる。
    Throws: なし
    Complexity: 線形時間

xor_list list operations

  1. void splice(iterator position, xor_list<T,Allocator>& x);
    Requires: &x != this
    Effects: x の全要素を position の前に挿入し、x を空にする。get_allocator() == x.get_allocator() ならば x.begin() と x.end() が無効になる。それ以外の場合は x の要素を指す参照、ポインタ、反復子すべてが無効になる。また、position とその一つ前の反復子が無効になる。
    Throws: get_allocator() == x.get_allocator() ならば例外は送出されない。
    Complexity: get_allocator() == x.get_allocator() ならば定数時間。それ以外の場合は x.size() に比例する。 
  2. void splice(iterator position, xor_list<T,Allocator>& x, iterator i);
    Effects: i の指す要素を position の前に挿入し、x からその要素を削除する。get_allocator() != x.get_allocator() ならば i の要素を指す参照、ポインタが無効になる。また、position とその一つ前の反復子、i とその前後の反復子が無効になる。
    Throws: get_allocator() == x.get_allocator() ならば例外は送出されない。
    Complexity: 定数時間 
  3. template<typename InputIterator> 
  void splice(iterator position, xor_list<T,Allocator>& x, 
              InputIterator first, InputIterator last);
    Requires: 区間 [first, last) は x に対する正当な区間である。position は 区間 [first, last) の反復子ではない。
    Effects: 区間 [first, last) の指す要素を position の前に挿入し、x からそれらの要素を削除する。get_allocator() != x.get_allocator() ならば区間 [first, last) の要素を指す参照、ポインタ、反復子が無効になる。また、position とその一つ前の反復子、first とその前後の反復子、last とその前方二つの反復子が無効になる。
    Throws: get_allocator() == x.get_allocator() ならば例外は送出されない。
    Complexity: get_allocator() == x.get_allocator() ならば定数時間。それ以外の場合は std::distance(first, last) に比例する。 
  4. void remove(const T& value);
    Effects: *i == value となるような反復子 i の指す要素をすべて削除する。
    Throws: *i == value の評価以外では例外を送出しない。
    Complexity: size() 回の比較。 
  5. template<typename Predicate> void remove_if(Predicate pred);
    Effects: pred(*i) != false となるような反復子 i の指す要素をすべて削除する。
    Throws: pred(*i) != false の評価以外では例外を送出しない。
    Complexity: size() 回の比較。 

  6. void unique();
template<typename BinaryPredicate> void unique(BinaryPredicate binary_pred);
    Effects: リスト中の連続する等価な要素を最初の要素を除いてすべて削除する。ここで「連続する等価な要素」とは、*i == *j (関数版)または binary_pred(*i, *j) != false (テンプレート版)となるような反復子 i と j の指す要素である。ただし、j == --i とする。
    Complexity: コンテナが空でない場合、size() - 1 回の比較。それ以外の場合は比較を行わない。 

  7. void merge(xor_list<T,Allocator>& x);
template<typename Compare> void merge(xor_list<T,Allocator>& x, Compare comp);
    Requires: operator< (関数版)または comp (テンプレート版) は弱全順序を定義していなければならない。*this 及び x はこの弱全順序に従って整列されていなければならない。
    Effects: 弱全順序を保ったまま、x のすべての要素を *this に併合する。get_allocator() != x.get_allocator() ならば x の要素を指す参照、ポインタが無効になる。また、*this と x のすべての反復子が無効になる。
    Complexity: 高々size() + x.size() - 1 回の比較。比較以外で例外が送出された場合は何もしない。
    Notes: 二つのリストに同値な要素が含まれる場合、併合先のリストの要素が優先される。 

  8. void sort();
template<typename Compare> void sort(Compare comp);
    Requires: operator< (関数版)または comp (テンプレート版) は弱全順序を定義していなければならない。
    Effects: 弱全順序に従い、リスト中の要素を整列する。リスト中のすべての反復子が無効になる。
    Complexity: およそ NlogN 回の比較。ただし、N = size() とする。
    Notes: この操作は安定ソートである。同値な要素の相対順序は保持される。要素の比較で例外が送出された場合、要素の順序は不定とする。 
  9. void reverse();
    Effects: リスト中の要素の順序を逆転する。リスト中のすべての反復子が無効になる。
    Throws: なし
    Complexity: 定数時間

xor_list comparisons

  1. template<typename T, typename Allocator> 
  bool operator==(const xor_list<T,Allocator>& x, 
                  const xor_list<T,Allocator>& y);
    Returns: x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin(), y.end())
    Complexity: 線形時間 
  2. template<typename T, typename Allocator> 
  bool operator<(const xor_list<T,Allocator>& x, 
                 const xor_list<T,Allocator>& y);
    Returns: std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end())
    Complexity: 線形時間 
  3. template<typename T, typename Allocator> 
  bool operator!=(const xor_list<T,Allocator>& x, 
                  const xor_list<T,Allocator>& y);
    Returns: !(x == y)
    Complexity: 線形時間 
  4. template<typename T, typename Allocator> 
  bool operator>(const xor_list<T,Allocator>& x, 
                 const xor_list<T,Allocator>& y);
    Returns: y < x
    Complexity: 線形時間 
  5. template<typename T, typename Allocator> 
  bool operator>=(const xor_list<T,Allocator>& x, 
                  const xor_list<T,Allocator>& y);
    Returns: !(x < y)
    Complexity: 線形時間 
  6. template<typename T, typename Allocator> 
  bool operator<=(const xor_list<T,Allocator>& x, 
                  const xor_list<T,Allocator>& y);
    Returns: !(x > y)
    Complexity: 線形時間

xor_list specialized algorithms

  1. template<typename T, typename Allocator> 
  void swap(xor_list<T,Allocator>& x, xor_list<T,Allocator>& y);
    Effects: 
    x.swap(y);
製作著作 © 2010 Takeshi Mouri
前のページ 上に戻る ホーム 次のページ