Visual C++ 2010に追加されたSTLコンテナ「forward_list」

listを簡略化したコンテナ「forward_list」

insert_iteratorを作ってみた

　ここからはお遊びを兼ねた習作。STLコンテナsrc、dstがあり、srcの要素から特定の条件を満たすものをdstにコピーすることを考えます。たとえばsrcをarray、dstをvectorとするなら、

list-8 : 偶数をvector<int>にコピーする

array<int,5> src = { 0, 1, 2, 3, 4 };
vector<int> dst;
copy_if(src.begin(), src.end(),
        back_inserver(dst), // inserter(dst,dst.end()) も可
        [](int x) { return x % 2 == 0; });

　このとき、コンテナがpush_back()を持ってないとback_inserter()は使えないし、insert()を持ってないとinserter()が使えません。なのでforward_list<int>をコピー先dstにはできないんですよ。かといってpush_front()で挿入を行うfront_inserter()では結果が逆順に格納されてしまいます。

　そこでforward_list専用のinsert_after_iteratorをデッチ上げます。と言ってもそんなに面倒なことじゃなく、insert_iteratorの実装をそのままいただき、ほんのちょっと手を加えるだけなのですが。

list-9 : insert_after_iterator, after_inserter

// TEMPLATE CLASS insert_after_iterator
template<class Container>
class insert_after_iterator
  : public std::iterator<std::output_iterator_tag,void,void,void,void> {
public:
  typedef Container container_type;
  typedef typename Container::const_reference const_reference;
  typedef typename Container::value_type value_type;

  insert_after_iterator(Container& cont, typename Container::iterator where)
    : container(&cont), iter(where) {}

  insert_after_iterator<Container>& operator=(const value_type& _Val) {
    iter = container->insert_after(iter, _Val); // ここで ++iter しないのがミソ
    return (*this);
  }

  insert_after_iterator<Container>& operator=(value_type&& _Val) {
    iter = container->insert_after(iter, std::forward<_Valty>(_Val)); // 同上
    return (*this);
  }

  insert_after_iterator<Container>& operator*() { return *this; }
  insert_after_iterator<Container>& operator++() { return *this; }
  insert_after_iterator<Container>& operator++(int) { return *this; }

protected:
  Container* container;
  typename Container::iterator iter;
};

// TEMPLATE FUNCTION after_inserter
template<class Container> inline
insert_after_iterator<Container>
after_inserter(Container& cont, typename Container::iterator where) {
  return insert_after_iterator<Container>(cont, where);
}

　さらにforward_listの末尾に挿入できるよう、end()の直前すなわち末尾要素を指すイテレータを返すヘルパ関数before_end()を用意します。

list-10 : advance_before, before_end

// endの手前までiterを進める
template<typename Iterator>
bool advance_before(Iterator& iter, Iterator end) {
  if ( iter == end ) return false;　// endの手前をポイントできない
  for ( Iterator next = iter; ++next != end; ++iter)
    ; // do nothing
  return true;
}

// fl.end() の直前位置を返す
template<typename T, class Allocator>
typename std::forward_list<T,Allocator>::iterator
before_end(std::forward_list<T,Allocator>& fl) {
  auto iter = fl.before_begin();
  advance_before(iter,fl.end());
  return iter;
}

template<class Container> inline
insert_after_iterator<Container>
after_back_inserter(Container& cont) {
  return after_inserter(cont, before_end(cont));
}

　試運転してみましょう。動物集合animalsからネコとネズミだけをコピーします。

list-11 : forward_list専用insert_iteratorおためし

int main() {
  array<string,9> animals = {
    "ハチ(犬)", "ミッキー(鼠)", "シュウたん(猫)",
    "タロ(犬)", "楽俊(鼠)",     "みずき(猫)",
    "ジロ(犬)", "ジェリー(鼠)", "マグさん(猫)" };

  forward_list<string> friends;

  // ネコをfriendsの先頭に（ただし逆順）
  copy_if(animals.begin(), animals.end(),
    front_inserter(friends),
    [](const string& x) { return x.find("(猫)") != string::npos;});

  // ネズミをfriendsの末尾に
  copy_if(animals.begin(), animals.end(),
    after_back_inserter(friends), // こうやって使う
    [](const string& x) { return x.find("(鼠)") != string::npos;});

  for_each(friends.begin(), friends.end(), 
    [](const string& x) { cout << x << ' ';});
}

実行結果

マグさん(猫) みずき(猫) シュウたん(猫) ミッキー(鼠) 楽俊(鼠) ジェリー(鼠)