Tryer Tryer - 3 years ago 115
C++ Question

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

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.

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?

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download