C ++ 17 및 C ++ 14 기능을 사용하면 다음 코드가 더 낫다고 생각합니다.

// These codes are un-tested when I write this post, but I'll test it
// When I'm free, and I sincerely welcome others to test and modify this
// code.

// C++17
#include <istream>     // For std::istream.
#include <string_view> // new feature in C++17, sizeof(std::string_view) == 16 in libc++ on my x86-64 debian 9.4 computer.
#include <string>
#include <utility>     // C++14 feature std::move.

template <template <class...> class Container, class Allocator>
void split1(Container<std::string_view, Allocator> &tokens,
            std::string_view str,
            std::string_view delimiter = " ")
{
    /*
     * The model of the input string:
     *
     * (optional) delimiter | content | delimiter | content | delimiter|
     * ... | delimiter | content
     *
     * Using std::string::find_first_not_of or
     * std::string_view::find_first_not_of is a bad idea, because it
     * actually does the following thing:
     *
     *     Finds the first character not equal to any of the characters
     *     in the given character sequence.
     *
     * Which means it does not treeat your delimiters as a whole, but as
     * a group of characters.
     *
     * This has 2 effects:
     *
     *  1. When your delimiters is not a single character, this function
     *  won't behave as you predicted.
     *
     *  2. When your delimiters is just a single character, the function
     *  may have an additional overhead due to the fact that it has to
     *  check every character with a range of characters, although
     * there's only one, but in order to assure the correctness, it still
     * has an inner loop, which adds to the overhead.
     *
     * So, as a solution, I wrote the following code.
     *
     * The code below will skip the first delimiter prefix.
     * However, if there's nothing between 2 delimiter, this code'll
     * still treat as if there's sth. there.
     *
     * Note:
     * Here I use C++ std version of substring search algorithm, but u
     * can change it to Boyer-Moore, KMP(takes additional memory),
     * Rabin-Karp and other algorithm to speed your code.
     *
     */

    // Establish the loop invariant 1.
    typename std::string_view::size_type
        next,
        delimiter_size = delimiter.size(),
        pos = str.find(delimiter) ? 0 : delimiter_size;

    // The loop invariant:
    //  1. At pos, it is the content that should be saved.
    //  2. The next pos of delimiter is stored in next, which could be 0
    //  or std::string_view::npos.

    do {
        // Find the next delimiter, maintain loop invariant 2.
        next = str.find(delimiter, pos);

        // Found a token, add it to the vector
        tokens.push_back(str.substr(pos, next));

        // Skip delimiters, maintain the loop invariant 1.
        //
        // @ next is the size of the just pushed token.
        // Because when next == std::string_view::npos, the loop will
        // terminate, so it doesn't matter even if the following 
        // expression have undefined behavior due to the overflow of 
        // argument.
        pos = next + delimiter_size;
    } while(next != std::string_view::npos);
}

template <template <class...> class Container, class traits, class Allocator2, class Allocator>
void split2(Container<std::basic_string<char, traits, Allocator2>, Allocator> &tokens,
            std::istream &stream,
            char delimiter = ' ')
{
    std::string<char, traits, Allocator2> item;

    // Unfortunately, std::getline can only accept a single-character 
    // delimiter.
    while(std::getline(stream, item, delimiter))
        // Move item into token. I haven't checked whether item can be 
        // reused after being moved.
        tokens.push_back(std::move(item));
}

컨테이너 선택 :

1. std::vector.

   할당 된 내부 배열의 초기 크기가 1이고 최종 크기가 N이라고 가정하면 log2 (N) 번에 대해 할당 및 할당 해제하고 (2 ^ (log2 (N) + 1)-1) = (2N-1) 번. 에서 지적했듯이 realloc을 로그 횟수로 호출하지 않아 std :: vector의 성능이 좋지 않습니까? , 벡터의 크기를 예측할 수없고 매우 클 경우 성능이 저하 될 수 있습니다. 그러나 크기를 추정 할 수 있다면 문제가되지 않을 것입니다.

2. std::list.

   모든 push_back에 대해 소비 된 시간은 일정하지만 개별 push_back에서 std :: vector보다 더 많은 시간이 걸릴 수 있습니다. 스레드 별 메모리 풀과 사용자 지정 할당자를 사용하면이 문제를 완화 할 수 있습니다.

3. std::forward_list.

   std :: list와 같지만 요소 당 더 적은 메모리를 차지합니다. API push_back의 부족으로 인해 작동하려면 래퍼 클래스가 필요합니다.

4. std::array.

   성장 한계를 알 수 있다면 std :: array를 사용할 수 있습니다. 원인은 API push_back이 없기 때문에 직접 사용할 수 없습니다. 하지만 래퍼를 정의 할 수 있으며 여기에서 가장 빠른 방법이라고 생각하며 추정이 매우 정확하면 메모리를 절약 할 수 있습니다.

5. std::deque.

   이 옵션을 사용하면 성능을 위해 메모리를 교환 할 수 있습니다. 요소의 복사는 (2 ^ (N + 1)-1), 할당은 N 배, 할당 해제는 없습니다. 또한 일정한 임의 액세스 시간과 양쪽 끝에 새 요소를 추가 할 수있는 기능이 있습니다.

std :: deque-cppreference 에 따르면

반면에 데크는 일반적으로 최소한의 메모리 비용이 큽니다. 요소가 하나만있는 데크는 전체 내부 배열을 할당해야합니다 (예 : 64 비트 libstdc ++에서 객체 크기의 8 배, 객체 크기의 16 배 또는 64 비트 libc ++에서 4096 바이트 중 더 큰 쪽).

또는 다음 조합을 사용할 수 있습니다.

1. std::vector< std::array<T, 2 ^ M> >

   이것은 std :: deque와 유사합니다. 차이점은 단지이 컨테이너가 맨 앞에 요소를 추가하는 것을 지원하지 않는다는 것입니다. 그러나 (2 ^ (N + 1)-1) 번에 대한 기본 std :: array를 복사하지 않기 때문에 성능이 더 빠릅니다. (2 ^에 대한 포인터 배열 만 복사합니다. (N-M + 1)-1) 번, 전류가 가득 차서 아무것도 할당 해제 할 필요가 없을 때만 새 배열을 할당합니다. 그건 그렇고, 당신은 일정한 랜덤 액세스 시간을 얻을 수 있습니다.

2. std::list< std::array<T, ...> >

   메모리 프레임 화의 부담을 크게 완화합니다. 전류가 꽉 찼을 때만 새 어레이를 할당하고 아무것도 복사 할 필요가 없습니다. 콤보 1에 비해 추가 포인터에 대한 가격을 지불해야합니다.

3. std::forward_list< std::array<T, ...> >

   2와 동일하지만 콤보 1과 동일한 메모리 비용이 듭니다.

답변

void split1(vector<string> &tokens, const string &str, const string &delimiters = " ")

void split1(vector<string> &tokens, const string &str, const char delimiters = ' ')

split1  C++   : Saw 10000000 lines in 41 seconds.  Crunch speed: 243902
split2  C++   : Saw 10000000 lines in 144 seconds.  Crunch speed: 69444
split1' C++   : Saw 10000000 lines in 33 seconds.  Crunch speed: 303030

void split5(vector<string> &tokens, const string &str, char delim=' ') {

    enum { do_token, do_delim } state = do_delim;
    int idx = 0, tok_start = 0;
    for (string::const_iterator it = str.begin() ; ; ++it, ++idx) {
        switch (state) {
            case do_token:
                if (it == str.end()) {
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                    return;
                }
                else if (*it == delim) {
                    state = do_delim;
                    tokens.push_back (str.substr(tok_start, idx-tok_start));
                }
                break;

            case do_delim:
                if (it == str.end()) {
                    return;
                }
                if (*it != delim) {
                    state = do_token;
                    tok_start = idx;
                }
                break;
        }
    }
}