[C/C++] 문자열 분리 (strpbrk, strtok, find_first_of 사용)

1. C 의 strpbrk 함수를 사용한 delimiter 문자 검색 (가장 빠름)

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[] = "This_is,the,,C/C++ world";
    char del[] = "/, _";

    char *start = str, *stop = start;

    for (; stop != NULL; start = stop + 1)
    {
        if (stop = strpbrk(start, del))
            *stop = NULL;

        printf("%s\n", start);
    }
}

출력:

This
is
the

C
C++
world

 

2. C 의 strtok 함수를 사용한 delimiter 문자 검색

strtok 함수는 strpbrk 와 비슷한데, 발견된 구분자 위치에 자동으로 널문자를 넣어주며 연속된 delimiter에 의한 빈 문자열은 건너뛴다는 점이 다르다. 다만 중첩 수행 및 멀티 쓰레드 안정성이 고려되어 있지 않으므로 strtok_s 또는 strpbrk 를 사용하는 것이 좋다.

#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[] = "This_is,the,,C/C++ world";
    char del[] = "/, _";

    char* start = strtok(str, del);

    while (start)
    {
        printf("%s\n", start);
        start = strtok(NULL, del);
    }
}

출력:

This
is
the
C
C++
world

 

3. C++ 의 find_first_of 함수를 사용한 delimiter 문자 검색

strpbrk 와 같이 빈 문자열을 건너뛰지 않는다.

#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    string str = "This_is,the,,C/C++ world";
    string del = "/, _";

    for (auto start = str.begin(), stop = start; stop != str.end(); )
    {
        stop = find_first_of(start, str.end(), del.begin(), del.end());

        cout << string(start, stop) << endl;

        if (stop != str.end())
            start = stop + 1;
    }
}

출력:

This
is
the

C
C++
world

 

속도는 윈도우 기준으로 find_first_of 가 O(N*M), strpbrk 가 O(N+M) 의 실행 속도를 낸다.
(입력 문자열 수 N, 구분 문자 세트 수 M)

strpbrk 는 입력 요소가 char 타입이기 때문에 구분 문자 세트 M이 최대 256 이므로 M 에 대한 해시 테이블을 사용해 for 루프를 N 번만 수행하도록 최적화할 수 있지만, find_first_of 는 요소의 타입에 무관한 generic 함수이기 때문에 이러한 최적화가 구현되기 어려워 N과 M 의 이중 for 루프를 수행하기 때문으로 보인다.

실제로 확인해 보니 윈도우 C런타임의 구현은 strpbrk 의 경우 해시 테이블(32 X 8개의 비트 마스크로 256가지 문자를 O(1)로 검색)을 사용해 한 단계의 루프만 돌지만 wcspbrk 의 경우 해시 테이블을 사용하지 않는 이중 루프로 구현되어 있다. 

 

 

번외로 C++ range-based iterator 를 구현한 split_string 클래스

iterator 의 구현 방식이 다소 복잡하지만 사용법은 매우 간단하다.

#pragma once
#include <string>
#include <iostream>

using namespace std;

struct split_string
{
    string _str, _del;

    split_string(string str, string delimiters = " \r\n\t\v\f")
    {
        _str = str, _del = delimiters;
    }

    struct iterator
    {
        char *start, *stop, *del; // start = nullptr 이면 더 이상 검색할 수 없는 상태 (end iterator)
        
        iterator operator++()
        {
            if (stop)
                stop = strpbrk(start = stop + 1, del);
            else
                start = nullptr;
            return *this;
        }

        bool operator!=(const iterator& other)
        {
            return start != other.start || stop != other.stop;
        }

        const char* operator*()
        {
            if (stop) *stop = '\0';
            return start;
        }        
    };

    iterator begin()
    {
        return iterator{ &_str[0], strpbrk(&_str[0], &_del[0]), &_del[0] };
    }

    iterator end()
    {
        return iterator{ nullptr };
    }
};

int main()
{
    char str[] = "This_is,the,,C/C++ world";
    char del[] = "/, _";
    
    for (auto a : split_string(str, del))
        cout << a << endl;
}

출력:

This
is
the

C
C++
world