char*의 배열을 정렬하는 쉬운 방법이 있습니까? C ++

StackOverflow https://stackoverflow.com/questions/314492

문제

배열이 있습니다 char* 파일에서. 내가 플랫 파일로 매장 데이터를 위해 일하는 회사. 때로는 데이터가 정렬되지만 때로는 그렇지 않습니다. 파일에 데이터를 정렬하고 싶습니다.

이제 코드를 작성하여 처음 부터이 작업을 수행 할 수있었습니다. 더 쉬운 방법이 있습니까?

물론 내면의 정렬이 최선의 선택입니다. 나는 큰 파일을 작업하고 있으며 램이 거의 없습니다. 그러나 나는 모든 옵션을 고려할 것입니다.

모든 문자열은 길이가 동일합니다.

이것은 일부 샘플 데이터입니다.

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

이것은 길이 28의 세 가지 레코드를 나타냅니다. 앱은 길이를 알고 있습니다. 각 레코드는 CRLF로 끝납니다 (\r\n), 이런 종류의 경우에는 중요하지 않습니다.

도움이 되었습니까?

해결책 

template<size_t length> int less(const char* left, const char* right) {
    return memcmp(left, right, length) < 0;
}

std::sort(array, array + array_length, less<buffer_length>);

다른 팁

데이터를 RAM에 맞출 수없는 경우 GNU 정렬 프로그램 (외부) 사용 : 임의 크기의 파일을 정렬하고 파일이 클수록 프로세스 생성의 추가 비용이 작습니다.

STL 컨테이너뿐만 아니라 배열 기본 데이터 유형의 STL에서 알고리즘을 사용할 수 있습니다. strcmp가 왼쪽이 오른쪽보다 작을 때뿐만 아니라 문자열이 동일하지 않을 때 모든 비교에 대해 평가하는 값을 반환하기 때문에 std :: sort를 사용하는 다른 제안은 게시 된대로 작동하지 않습니다. 핸드 사이드 - 이것은 std :: 정렬이 원하는 것입니다. 왼쪽의 사실이 반환되는 이진 술어는 오른쪽보다 작습니다.

이것은 작동합니다 :

struct string_lt : public std::binary_function<bool, char, char>
{
    bool operator()(const char* lhs, const char* rhs)
    {
        int ret = strcmp(lhs, rhs);
        return ret < 0;
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
    size_t numStrings = sizeof(strings)/sizeof(strings[0]);

    std::sort(&strings[0], &strings[numStrings], string_lt());

    return 0;
}

boost::bind 할 수있어:

// ascending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) < 0); 

// descending
std::sort(c, c + size,  boost::bind(std::strcmp, _1, _2) > 0);

편집하다: 문자열은 무효가되지 않습니다.

// ascending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) < 0); 

// descending
std::sort(c, c + array_size,  boost::bind(std::memcmp, _1, _2, size) > 0);

아마도 가장 쉬운 방법은 오래된 stdlib.h 함수 Qsort를 사용하는 것입니다. 이것은 작동해야합니다 :

qsort( array, num_elements, sizeof( char* ), strcmp )

이것은 표준 C이며 영어 텍스트 만으로만 작동합니다.

문자열 객체 목록이있는 경우 C ++에서 다른 것들이 가능합니다.

Linux에 있고 GTK 또는 QT 응용 프로그램을 작성하는 경우 이러한 라이브러리를 미리 살펴볼 것을 제안합니다.

파일이 크고 RAM에 맞지 않으면 사용할 수 있습니다. 빈/버킷 데이터를 작은 파일로 분할하도록 정렬하고 결국 결과 파일에서 조각을 집계하십시오. 다른 응답은 각 개별 버킷 파일을 정렬하는 방법을 보여줍니다.

C로 문자열 배열을 정렬하는 표준 방법이므로 C ++에서 이용할 수있는 권장 방법은 없지만 간접 수준을 사용합니다. strcmp():

static int qsort_strcmp(const void *v1, const void *v2)
{
    const char *s1 = *(char * const *)v1;
    const char *s2 = *(char * const *)v2;
    return(strcmp(s1, s2));
}

static void somefunc(void)   // Or omit the parameter altogether in C++
{
    char **array = ...assignment...
    size_t num_in_array = ...number of char pointers in array...
    ...
    qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
    ...more code...
}

몇 가지가 떠 오릅니다.

  1. 데이터가 메모리에 너무 커지면 파일 오프셋의 메모리 인덱스를 구축 한 다음 파일을 메모리 매핑하여 문자열에 액세스 할 수 있습니다 (OS에 따라 다름).
  2. 현장에서 필요합니다 많은 메모리 사본. 가능하면 쉘 정렬을 사용하십시오. 그런 다음 최종 순서를 알게되면 선형 시간에 문자열을 내내 재정렬하는 것이 훨씬 쉽습니다.
  3. 줄이 모두 같은 길이라면 진짜 Radix 정렬을 원합니다. Radix 정렬에 익숙하지 않은 경우 기본 아이디어는 다음과 같습니다. 비교 기반 분류 (이것은 무엇입니까? std::sort, qsort, 그리고 다른 일반 목적 분류)는 항상 O (n log n) 시간이 필요합니다. Radix Sorting은 한 번에 단일 자리를 비교합니다 (시작 str[0] 그리고 끝납니다 str[K-1] k- 차선의 경우), 전체적으로 실행하는 데 O (n) 시간 만 필요할 수 있습니다.

내가 제공 할 수있는 것보다 Radix 정렬 알고리즘에 대한 자세한 설명을 위해 인터넷에 문의하십시오. 내가 말한 것 외에도 표준 학문 분류 시설을 사용하는 다른 모든 솔루션을 피할 것입니다. 불행히도 특정 문제를 설계하지 않았습니다.

아마 메모리 매핑 파일을보고 싶을 것입니다 ( http://en.wikipedia.org/wiki/memory-mapped_file), mmap () 함수 (http://en.wikipedia.org/wiki/mmap) POSIX-Commaint OS에서. 기본적으로 파일의 내용을 나타내는 연속 메모리에 대한 포인터가 나타납니다.

좋은면은 OS가 파일의 일부를 메모리에로드하고 필요에 따라 다시 언로드하는 것을 관리한다는 것입니다.

한 가지 단점은 하나 이상의 프로세스가 파일에 액세스 할 가능성이있는 경우 부패를 피하기 위해 일부 형태의 파일 잠금으로 해결해야한다는 것입니다.

또 다른 단점은 이것이 좋은 성능을 보장하지는 않는다는 것입니다. 그렇게하려면 페이지를 끊임없이로드하고 내리는 것을 피하려는 정렬 알고리즘이 필요합니다 (물론 전체 파일을 메모리에로드하기에 충분한 메모리가 없다면).

이것이 당신에게 몇 가지 아이디어를 주셨기를 바랍니다!

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top