在 multiset 中维护一个排序的数字列表，在另一个中维护累积和

Question

我有一个应用程序，其中整数的显示顺序不分先后。呈现的整数可以是重复值。我必须以一种有序的方式维护它们。每次出现新条目时，都需要将其放置在适当的位置，以保持排序顺序。

std::multiset 似乎是一个建议的解决方案，插入的最佳时间 O(log n)。

现在，除了这个已排序的多重集之外，我还必须在另一个容器中维护累积和。

也就是说，如果排序的条目是：

1、5、7、9（在索引 0、1、2 和 3 中）

累积总和容器为：

1、6、13、22（在索引 0、1、2 和 3 中）

我无法弄清楚如何使用 std::multiset 迭代器，该迭代器在每次 insert(int) 操作后被 return 编辑到多重集以更新累积和容器。请注意，累积和只会影响那些因插入操作而必须移动的条目和索引。

也就是说，如果对于上面的列表，必须执行insert(8)，更新的容器将是：

已排序条目：

1、5、7、8、9（在索引 0、1、2、3 和 4 中）

累计：

1、6、13、21、30（在索引 0、1、2、3 和 4 中。请注意，只有索引 3 和 4 中的条目会受到影响。）

目前，我能够实现这一点的唯一方法是使用两个数组，一个用于值数组，一个用于累积和。实现此功能的工作代码如下所示：

#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直到到达数组末尾。

有没有比这两个整数数组更高效better/more的容器组合？

return 类型的 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::multiset，其中每个元素都是 std::pair，其中第一个是数字，第二个是累积总和。

在 multiset 中维护一个排序的数字列表，在另一个中维护累积和

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

c++

arrays

sorting

containers

multiset