C++ レガシー文字列変換で気をつける事

　今更、何を書いてはんの？だとは思いますが、ついつい、うっかりしがちなんで

#include <iostream>
#include <string>

std::string get_string( const char* str ) {
  std::string result = str;
  return result;
}

int main() {
  std::cout << get_string( nullptr ).size() << std::endl;
  std::cout << " OK? " << std::endl;
  return 0;
}

実行結果

terminate called after throwing an instance of 'std::logic_error'
  what():  basic_string::_S_construct null not valid
Abort trap: 6

4月 26, 2013 | Categories: cpp | コメントする

ポリゴンの髭を取り除く

　標準に無い変形アルゴリズムを晒してみようと思います。

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist = std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next = first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next = last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ（要素検索位置）
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] ２項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last, pred );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last, pred );
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ（要素検索位置）
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last );
  }

何に使うかというと、—ABA— みたいな構成のポリゴンは、髭のように変な辺が飛び出しているので、それを消去するのに使います。–ABCBA–みたいなパターンもあるので、–ABA– を消去しても油断できません。地道に再帰で消し去ります。

  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_duplicate( const vector<T>& sec ) {
    return (std::adjacent_find( sec.begin(), sec.end() ) != sec.end());
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾は連続としない
  */
  template <typename T>
  void deduce_duplicate( vector<T>& sec ) {
    vector<T>::iterator f  =  std::adjacent_find( sec.begin(), sec.end() );
    while( f != sec.end() ) {
      sec.erase( f );
      f  =  std::adjacent_find( sec.begin(), sec.end() );
    }
  }

  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_closed_duplicate( const vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    return check_duplicate( sec ) || (*(sec.begin()) == *(sec.rbegin()));
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾を連続とする
  */
  template <typename T>
  void deduce_closed_duplicate( vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    deduce_duplicate( sec );
    if( *(sec.begin()) == *(sec.rbegin()) )  sec.pop_back();
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリラインに使用する
  */
  template <typename T>
  void deduce_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;  sec.erase( g );  sec.erase( f );
      f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    }
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリゴンに使用する
  */
  template <typename T>
  void deduce_closed_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;
      if( g == sec.end() ) {
        sec.erase( f );  sec.erase( sec.begin() );
      } else {
        sec.erase( g );  sec.erase( f );
      }
      f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    }
  }

あんま、おもしろくないですかね。

3月 12, 2013 | Categories: cpp | コメントする

std::move ではまった事

　いまの所、std::move ではまった事なぞを、思い出せる範囲で書いてみようと思います。

　直近では、ndk での話ですが、std::unique に move constructor と move operator しか持たないクラスの deque をかけると、見事にデータが壊れました。move に一部対応している状況なので、文句は言えません。自前で move 用の unique をこさえました。特に、このバグは場所を特定できるまでに凄い時間がかかりました。どこで壊れているのか探すのも大変でした。

　vector を std::move にかけて移動させると、要素が倍で増えました。これは、move 後の変数の状態は不定なので、move した後にも残骸が残っており、残骸要素が加算されていくというバグでした。move した後に clear() をコールする事で回避しました。

move constructor だけでなく、copy constructor も追加したら、copy が優先されて、予期せぬ挙動を引き起こしました。copy constructor は封印して、copy ファンクタを利用するようなアルゴリズムをこさえる事で回避しました。

一応、こんなところでしょうか？

3月 11, 2013 | Categories: cpp | コメントする