멀티 세트에서 숫자의 정렬 된 목록 및 다른 숫자의 누적 합계 유지

Question

정수가 특별한 순서없이 표시되는 응용 프로그램이 있습니다. 제시되는 정수는 반복되는 값일 수 있습니다. 나는 그것을 정렬 된 방식으로 유지해야한다. 새 항목이 제시 될 때마다 정렬 된 순서가 유지되도록 적절한 위치에 배치해야합니다.

std::multiset 가장 적합한 시간 인 제안 된 해결책 인 O(log n) 인 것으로 보입니다.

이제이 정렬 된 다중 세트 외에도 누적 합계를 다른 컨테이너에 유지해야합니다.

는

1, 5, 7, 9

(인덱스 0, 1, 2 및 3에서) 누적 합계 컨테이너 것이다 :

정렬 된 항목이있는 경우이다

1, 6, 13, 22 (인덱스 0, 1, 2 및 3에서)

각 insert(int) 작업 이후에 반환되는 std::multiset 반복기를 사용하여 멀티 세트로 업데이트하는 방법을 알아내는 데 어려움이 있습니다 합계 컨테이너. 누적 합계는 삽입 작업으로 인해 이동해야하는 항목 및 색인에만 영향을줍니다. 상기 목록에 insert(8) 수행 할 경우

즉, 업데이트 된 컨테이너가 될 것이다 :

분류 항목이 인덱스 0

1, 5, 7, 8, 9 (1, 2, 3, 4)

누계 :

1, 6, 13, 21, 인덱스 0, 1, 2, 3 (30) (및도 4를 참고 지표 3 및 4 항목 만 영향을받습니다.)

현재 구현할 수있는 유일한 방법은 값 배열과 누적 합계에 대해 하나씩 두 개의 배열을 사용하는 것입니다. 이를 구현하는 작업 코드가 아래에 제시되어 어레이의 끝에 도달 할 때까지

코드로부터 알 수있는 바와 같이

#include <iostream> 


int *arr = new int[100];//Array to maintain sorted list 
int *cum_arr = new int[100];//Array to maintain cumulative sum 

void insert_into_position(int val, int &last_valid_index_after_insertion) { 
    //Inserts val into arr such that after insertion 
    //arr[] has entries in ascending order. 

    int postoadd = last_valid_index_after_insertion; 
    //index in array at which to insert val 
    //initially set to last_valid_index_after_insertion 

    //Search from end of array until you find the right 
    //position at which to insert val 
    for (int ind = last_valid_index_after_insertion - 1; ind >= 0; ind--) { 
     if (arr[ind] > val) { 
      postoadd--; 
     } 
     else { 
      break; 
     } 
    } 

    //Move everything from and including postoadd one position to the right. 
    //Update the cumulative sum array as you go 
    for (int ind = last_valid_index_after_insertion - 1; ind >= postoadd; ind--) { 
     arr[ind + 1] = arr[ind]; 
     cum_arr[ind + 1] = cum_arr[ind] + val; 
    } 

    //Update entry in index postoadd 
    arr[postoadd] = val; 
    if (postoadd > 0) 
     cum_arr[postoadd] = cum_arr[postoadd - 1] + val; 
    else 
     cum_arr[0] = val; 
    last_valid_index_after_insertion++; 
} 

int main(void) 
{ 
    int length = 0; 
    insert_into_position(1, length); 
    insert_into_position(5, length); 
    insert_into_position(7, length); 
    insert_into_position(9, length); 

    printf("\nPrint sorted array\n"); 
    for (int i = 0; i < length; i++) 
     printf("%d ", arr[i]); 
    printf("\nPrint Cumulative sum array\n"); 
    for (int i = 0; i < length; i++) 
     printf("%d ", cum_arr[i]); 

    insert_into_position(8, length); 

    printf("\nPrint sorted array\n"); 
    for (int i = 0; i < length; i++) 
     printf("%d ", arr[i]); 
    printf("\nPrint Cumulative sum array\n"); 
    for (int i = 0; i < length; i++) 
     printf("%d ", cum_arr[i]); 

    getchar(); 
} 

가 누적 합계를 계산하기 위해, 정수 배열 인덱스 postoadd 사용할 수있다.

두 정수 배열보다 더 효율적으로 수행 할 수있는 컨테이너 조합이 있습니까?

std::multiset.insert(int) 연산의 반환 형식은 삽입 된 항목을 가리키는 반복자입니다. 이 반복자를 사용하여 누적 합계를 저장하는 다른 컨테이너를 업데이트 할 수 있습니까?

Answer 1

키를 정렬 된 상태로 유지하고 중복 키를 허용하는 std::multimap을 사용하십시오.

예 :

#include <iostream> 
#include <map> 

int main() 
{ 
    std::multimap<int,int> mymultimap = { {1, 1}, {5, 6}, {7, 13}, {9, 22} }; 
    std::multimap<int,int>::iterator it; 

    it = mymultimap.insert (std::pair<char,int>(8, 8)); 

    if(mymultimap.size() > 1) { 
    it->second = std::prev(it)->second + it->second; 
    ++it; 
    while(it!=mymultimap.end()) { 
     it->second = std::prev(it)->second + it->first; 
     ++it; 
    } 
    } 

    // showing contents: 
    std::cout << "mymultimap contains:\n"; 
    for (it=mymultimap.begin(); it!=mymultimap.end(); ++it) 
    std::cout << (*it).first << " => " << (*it).second << '\n'; 

    return 0; 
} 

출력 :

mymultimap contains: 
1 => 1 
5 => 6 
7 => 13 
8 => 21 
9 => 30 

---

PS : 또 다른 방법은, 각 요소는 첫 번째 숫자 일 것이다 std::pair을 할 것 인 std::multiset을 사용하는 것 및 두 번째는 누적 합계입니다.