Maintien d'une liste triée de nombres dans un multiset et des sommes cumulées dans une autre

Question

J'ai une application dans laquelle les entiers sont présentés sans ordre particulier. Les entiers présentés peuvent être des valeurs de répétition. Je dois les maintenir d'une manière triée. Chaque fois qu'une nouvelle entrée est présentée, elle doit être placée dans la position appropriée afin que l'ordre trié soit maintenu.

std::multiset semble être une solution suggérée avec le meilleur temps, O(log n), pour l'insertion.

Maintenant, en plus de ce multiset trié, je dois maintenir les sommes cumulées dans un autre conteneur.

Autrement dit, si les entrées triées sont:

1, 5, 7, 9 (dans les indices 0, 1, 2 et 3)

le récipient de somme cumulée serait:

1, 6, 13, 22 (dans les index 0, 1, 2 et 3)

Je n'arrive pas à trouver comment utiliser l'itérateur std::multiset retourné après chaque opération insert(int) dans le multiset afin de mettre à jour le cumulatif somme conteneur. Notez que la somme cumulative affectera uniquement les entrées et les index qui doivent être déplacés en raison de l'opération d'insertion.

C'est, si la liste ci-dessus, insert(8) doit être effectuée, les conteneurs mis à jour seront:

entrées triées:

1, 5, 7, 8, 9 (indices 0, 1, 2, 3 et 4)

somme cumulative:

1, 6, 13, 21, 30 (dans les indices 0, 1, 2, 3 et 4. On notera que seules les entrées dans les indices 3 et 4 sont affectés.)

Actuellement, la seule façon que j'ai pu mettre en œuvre est d'utiliser deux tableaux, un pour le tableau de valeurs et un pour la somme cumulative. Un code de travail qui met en oeuvre ceci est présenté ci-dessous:

#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(); 
} 

Comme on peut le voir à partir de ce code, pour calculer la somme cumulative, l'indice de tableau d'entiers, postoadd peut être utilisé jusqu'à ce que soit atteinte la fin du tableau.

Y a-t-il une combinaison de conteneurs qui peut fonctionner mieux/plus efficacement que les deux ensembles de nombres entiers?

Le type de retour d'une opération std::multiset.insert(int) est un itérateur qui pointe vers l'entrée insérée. Est-ce que cet itérateur peut être utilisé pour mettre à jour un autre conteneur qui stocke la somme cumulée?

Answer 1

Utilisez un std::multimap, qui conserve les clés triées et autorise les clés en double.

Exemple:

#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; 
} 

Sortie:

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

---

PS: Une autre approche serait d'utiliser std::multiset où chaque élément serait std::pair, où le premier serait le nombre et la seconde la somme cumulée.