c++ - 언어 - 코딩 도장 함수




컨테이너를 청크로 나누기, C++ (3)

@BenjaminB가 anwser를 조금 수정했고이 함수를 사용하는 예제가 추가되었습니다.

#include <iostream>
#include <vector>

using namespace std;

template<typename Iterator, typename Func>
void chunks(Iterator begin,
            Iterator end,
            iterator_traits<string::iterator>::difference_type k,
            Func f)
{
    Iterator chunk_begin;
    Iterator chunk_end;
    chunk_end = chunk_begin = begin;

    do
    {
        if(std::distance(chunk_end, end) < k)
            chunk_end = end;
        else
            std::advance(chunk_end, k);
        f(chunk_begin,chunk_end);
        chunk_begin = chunk_end;
    }
    while(std::distance(chunk_begin,end) > 0);
}

int main() {
    string in_str{"123123123"};

    vector<string> output_chunks;

    auto f = [&](string::iterator &b, string::iterator &e)
    {
        output_chunks.emplace_back(b, e);
    };

    chunks(in_str.begin(), in_str.end(), 3, f);

    for (string a_chunk: output_chunks)
    {
        cout << a_chunk << endl;
    }

    return 0;
}

결과는 다음과 같습니다.

123
123
123

누군가가 유용 할 수 있기를 바랍니다.

주어진 N 요소 벡터 v = ( 1, 2, 3, 4, ... , N ) 은 크기가 K<N 모든 청크에 대해 반복 범위 반복자를 반환합니다. N%K!=0 경우 마지막 범위는 K 보다 작을 수 있습니다.

예 :

v = ("a","b","c","d","e")

문자열 표시

"ab", "cd", "e"

N=v.size();
K=2;

가능한 한 가지 해결책은 다음과 같습니다.

for( unsigned int i=0; i<v.size(); i+=K )
    cout << boost::join( v | boost::adaptors::sliced( i, min(i+K, v.size()) ), "" );

이 솔루션은 꽤 괜찮지 만 몇 가지 문제가 있습니다.

  1. for 루프 - 필요한가?
  2. min(i+K, v.size()) 알고리즘을 사용하는 대신 min(i+K, v.size()) 경계 케이스에주의를 기울여야합니다. 이것은보기 흉하고 산만 해 보인다.

보다 세련된 솔루션을 제안 할 수 있습니까? 우아한 해결책은 일반 알고리즘을 사용하거나, 일반적으로 사용되는 라이브러리 (예 : 부스트)를 사용하여 빌드하거나 제공한다는 것입니다.

-------------------------- [편집하다] --------------------- -----

여러분 중 일부는 실용적인 예를 얻었습니다. 여기 있습니다.

#include <iostream>
#include <vector>
#include <string>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/assign.hpp> //just for fun

using namespace std;
using namespace boost::assign;

int main(int , char **)
{
    const int K = 2;
    vector< string > v;
    v += "a","b","c","d","e";

    for( unsigned int i=0; i<v.size(); i+=K )
        cout << boost::algorithm::join( 
                    v | boost::adaptors::sliced( i, min(i+K, v.size()) ), "" ) 
             << endl;
}

산출:

ab 
cd
e

매우 우아한 지 모르겠지만 표준 함수 advance 및 distance를 사용하는 반복기를 사용할 수 있습니다.

template<typename Iterator, typename Func, typename Distance>
void chunks(Iterator begin, Iterator end, Distance k ,Func f){
    Iterator chunk_begin;
    Iterator chunk_end;
    chunk_end = chunk_begin = begin;

    do{
        if(std::distance(chunk_end, end) < k)
            chunk_end = end;
        else
            std::advance(chunk_end, k);
        f(chunk_begin,chunk_end);
        chunk_begin = chunk_end;
    }while(std::distance(chunk_begin,end) > 0);
}

WRT "For 루프가 필요합니까?"

루프 구조는 std::distance() 를 사용하지 않으려는 경우에 필요합니다. 랜덤 액세스 컨테이너의 경우 std::distance() 는 값이 쌉니다. 그러나 다른 모든 알고리즘에서는이 알고리즘에 비해 비용이 많이 듭니다.)

WRT i + K / min () 문제

i + K 또는 포장 / 초과 / 언더 플로 문제를 일으킬 수있는 사항은 쓰지 마십시오. 대신 남은 양을 추적하고 뺍니다. min() 사용해야합니다.

WRT 우아한 솔루션

이 알고리즘은 다음과 같이보다 "우아합니다".

  1. 위의 처음 두 "WRT"항목은 문제가되지 않습니다.
  2. 외부 라이브러리를 사용하지 않습니다. - std::copy_n()std::advance() 합니다.
  3. 인수 필요 룩업이 필요한 / 필요하다면 인수 의존 룩업을 이용합니다.
  4. 컨테이너의 size_type 사용합니다.
  5. 모든 컨테이너에서 효율적으로 작동합니다.
  6. K <= 0이면 std::domain_error 가 발생합니다.

솔루션은 C ++ 11이지만 copy_n() 도 작성하면 C ++ 98으로 쉽게 변환 할 수 있습니다.

#include <vector>
#include <string>
#include <sstream>
#include <iterator>
#include <iostream>
#include <stdexcept>
#include <algorithm>

template <
  typename Container,
  typename OutIter,
  typename ChunkSepFunctor
>
OutIter chunker(
  Container const& c, 
  typename Container::size_type const& k,
  OutIter o,
  ChunkSepFunctor sep
)
{
  using namespace std;

  if (k <= 0)
    throw domain_error("chunker() requires k > 0");

  auto chunkBeg = begin(c);
  for (auto left=c.size(); left != 0; )
  {
    auto const skip = min(left,k);

    o = copy_n(chunkBeg, skip, o);

    left -= skip;
    advance(chunkBeg, skip);

    if (left != 0)
      sep();
  }
  return o; 
}

int main()
{
  using namespace std;

  using VECTOR = vector<string>;
  VECTOR v{"a","b","c","d","e"};

  for (VECTOR::size_type k = 1; k < 7; ++k)
  {
    cout << "k = " << k << "..." << endl;
    chunker(
      v, k, 
      ostream_iterator<VECTOR::value_type>(cout),
      []() { cout << endl; }
    );
  }
  cout << endl;
}

편집 : sep 펑터가 출력 반복자를 수신하고 출력 반복자를 반환하도록 chunker() 를 작성하는 것이 좋습니다. 이 방법을 사용하면 출력 반복기에 관한 출력 청크 간의 모든 업데이트를 올바르게 처리 할 수 ​​있고 일반 루틴을 훨씬 유연하게 처리 할 수 ​​있습니다. (예를 들어, 이것은 펑크 터가 각 덩어리의 끝 위치를 기억할 수있게 해주고, 덩어리를 복사하고, 컨테이너를 비우고, 출력 반복자를 재설정하는 펑터 등) 만약 이것이 바람직하지 않다면 표준 라이브러리처럼 서로 다른 sep 요구 사항으로 하나 이상의 과부하가 있거나 인수를 모두 제거해야합니다. 이 업데이트 된 chunker() 는 다음과 같습니다.

template <
  typename Container,
  typename OutIter,
  typename ChunkSepFunctor
>
OutIter chunker(
  Container const& c, 
  typename Container::size_type const& k,
  OutIter o,
  ChunkSepFunctor sep
)
{
  using namespace std;

  if (k <= 0)
    throw domain_error("chunker() requires k > 0");

  auto chunkBeg = begin(c);
  for (auto left=c.size(); left != 0; )
  {
    auto const skip = min(left,k);

    o = copy_n(chunkBeg, skip, o);

    advance(chunkBeg, skip);
    left -= skip;

    if (left != 0)
      o = sep(o);
  }
  return o; 
}

청크 호출은 꽤 적지 만 일반적으로 더 유용 할 것입니다 (이 경우는 아니지만).

chunker(
  v, k, 
  ostream_iterator<VECTOR::value_type>(cout),
  [](ostream_iterator<VECTOR::value_type> o) { cout << endl; return o; }
);

이것은 놀라 울 정도로 우아한 작은 일상으로 밝혀졌습니다.





c++11