c++11 c언어 - 컨테이너를 청크로 나누기, C++



비트필드 비트필드란 (5)

주어진 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

Answers

매우 우아한 지 모르겠지만 표준 함수 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);
}

@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

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


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; }
);

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


이는 우수한 성능을 갖춘 일종의 일반적인 솔루션입니다.

template <class T, class Func>
void do_chunks(T container, size_t K, Func func) {
    size_t size = container.size();
    size_t i = 0;

    // do we have more than one chunk?
    if (size > K) {
        // handle all but the last chunk
        for (; i < size - K; i += K) {
            func(container, i, i + K);
        }
    }

    // if we still have a part of a chunk left, handle it
    if (i % K) {
        func(container, i, i + i % K);
    }
}

구문 당과는 별도로 참조는 const 포인터입니다 ( const 포인터가 아닙니다 ). 참조 변수를 선언 할 때 참조하는 내용을 설정해야하며 나중에 변경할 수 없습니다.

업데이트 : 이제 생각해 보면 더 중요한 차이가 있습니다.

const 포인터의 대상은 주소를 가져 와서 const 캐스트를 사용하여 바꿀 수 있습니다.

참조의 대상은 UB가 부족한 어떤 방법 으로든 대체 할 수 없습니다.

이렇게하면 컴파일러가 참조에서 더 많은 최적화 작업을 수행 할 수 있습니다.





c++ c++11