マルチセット内のソートされたリストと別のソートされたリストの維持

Question

整数が特に指定されていないアプリケーションがあります。提示される整数は、反復値であってもよい。私はソートされた方法でそれらを維持する必要があります。新しいエントリが提示されるたびに、ソートされた順序が維持されるように適切な位置に配置する必要があります。

std::multisetは、最適な時刻を示す1つの解決策、挿入のためのO(log n)のようです。

ここでは、このソート済みマルチセットに加えて、累積合計を別のコンテナに保持する必要があります。ソートされたエントリがある場合に、ある

：

1、5、7、9（インデックス0、1、2及び3）

累積和容器は次のようになります

1、6、13、22（インデックス0、1、2及び3）

I累積を更新するために多重集合に各insert(int)操作後に復帰するstd::multiset反復子を使用する方法を考え出す問題が午前合計コンテナ。累積合計は、挿入操作のために移動する必要があるエントリおよびインデックスにのみ影響します。

insert(8)を行わなければならず、上記のリストにあれば、更新された容器のようになり、ある：

ソートエントリ：インデックス0で

1、5、7、8、9（、 1、2、3及び4）

累積和：

1、6、13、21、30（インデックス0、1、2、3および4メモインデックス3及び4におけるエントリのみその影響を受ける。）

現在、これを実装する唯一の方法は、値の配列と累積合計の2つの配列を使用することです。これを実装する作業コードを以下に示す：累積合計、整数配列インデックスを計算するために、このコードから分かるよう

#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を使用することができます。

2つの整数配列よりも優れた/より効率的に実行できるコンテナの組み合わせはありますか？

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を使用することであろう、そして2番目は累積合計です。