Tryer - 3 years ago 115

C++ 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.

`O(log n)`

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`

`insert(int)`

That is, if to the above list,

`insert(8)`

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`

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)`

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

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**