Maintaining a sorted list of numbers in multiset and the cumulative sums in another

Question

I have an application in which integers are presented in no particular order. The integers presented can be repeat values. I have to maintain them in a sorted fashion. Each time a new entry is presented, it needs to be placed in the appropriate position so that the sorted order is maintained.

std::multiset

seems to be one suggested solution with the best time,

O(log n)

, for insertion.

Now, in addition to this sorted multiset, I have to maintain the cumulative sums in another container.

That is, if the sorted entries are:

1, 5, 7, 9 (in indices 0, 1, 2 and 3)

the cumulative sum container would be:

1, 6, 13, 22 (in indices 0, 1, 2 and 3)

I am having trouble figuring out how to use the

std::multiset

iterator that is returned after each

insert(int)

operation into the multiset in order to update the cumulative sum container. Note that the cumulative sum will only affect in those entries and indices that have to be moved because of the insert operation.

That is, if to the above list,

insert(8)

has to be performed, the updated containers would be:

Sorted entries:

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

Cumulative sum:

1, 6, 13, 21, 30 (in indices 0, 1, 2, 3 and 4. Note that only entries in indices 3 and 4 are affected.)

At present, the only way I have been able to implement this is by using two arrays, one for the array of values and one for the cumulative sum. A working code that implements this is presented below:

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

}

As can be seen from this code, to calculate the cumulative sum, the integer array index,

postoadd

can be used until the end of the array is reached.

Is there any combination of containers that can perform better/more efficiently than the two integer arrays?

The return type of a

std::multiset.insert(int)

operation is an iterator that points to the inserted entry. Can this iterator be used to update another container that stores the cumulative sum?

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

Use an std::multimap, which keeps the keys sorted, and allows for duplicate keys.

Example:

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

Output:

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

PS: Another approach would be to use std::multiset where every element would be std::pair, where the first would be the number, and the second the cumulative sum.

Maintaining a sorted list of numbers in multiset and the cumulative sums in another

Sign up