c++ - 在 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) 操作后返回到 multiset 中以更新累计和容器。请注意，累积和只会影响那些因插入操作而必须移动的条目和索引。

也就是说，如果对于上面的列表，必须执行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直到到达数组末尾。

是否有任何容器组合可以比这两个整数数组执行得更好/更有效？

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，其中第一个是数字，第二个累积总和。