C ++如何在排序向量中插入新元素？

Question

我正在创建一个分数表，其中的分数存储在Vector中。当一个新的分数被添加并且它比Vector中的当前分数更大时，我希望添加该分数（我已经完成了）但是我希望该分数背后的所有分数基本上都会回到为该分数腾出空间新的分数。

基本上我所说的是当一个新元素被添加到Vector时，我希望新元素背后的所有元素基本上被推回，但我无法想出办法。

我想知道是否有人有想法？

编辑：使我想要的更清楚一点。想象一下，你有10个不同的分数，如下所示：

500 400 385 350 300 265 200 100 50 20

而且我想在这个阵列中添加一个新的分数，就像425那样。所以我想要的是将得分425放在得分1和2之间，得分为2,3,4,5,6， 7,8,9和10被推回所以得分2现在是得分3，得分3现在得分4，依此类推，直到我们得到10得分，其中20的原始得分10不再存在并且已经取而代之的是得分9，即50

Answer 1

您应该使用标准库的算法。

假设分数是您的分数向量，并且ns是您想要插入的新分数：

首先，找到小于新分数的第一个元素：

auto pos = std::find_if(scores.begin(), scores.end(), [ns](auto s) {
    return s < ns;
});

然后在此位置插入新元素（vector.insert(it, elem)在它之前插入elem）。

scores.insert(pos, ns);

如果从头开始以这种方式插入每个元素，则始终会对矢量进行排序。你可以使用std::upper_bound来利用这个不变量，这样可以更快地查找。

要在插入后删除最低分，只需使用pop_back()。

Answer 2

处理这种情况的最佳方法是考虑所需的数据结构。这基本上是一个Score和某种Score表，在这里我的名字Scoreboard得分板将处理分数的添加，分数只是知道自己和抽象比较自己彼此。在这种情况下，我发现我们只需要知道得分A是否小于得分B才能订购。所以我只添加了一个operator<，但这是你遇到类似情况时应该使用的相同模式。

  class Score {
  private:
    std::string initials;
    int score;
  public:
    Score(const std::string & initials, int score) : initials(initials), score(score)
    {}

    int getValue() { return score; }

    bool operator< (const Score & rhs) {
      return this.score < rhs.score;
    }
  };


class Scoreboard {
private:
  std::vector<Score> score;

public:
  Scoreboard() { /* if score chart found on disk, deserialize() */ }
  ~Scoreboard() { /* if scores changed, serialize() to disk */ }


  /* All the magic is in this addScore method, and the scores.at(n) < score
 line where we're using the operator< from Score as above stated, in order
 to determine if the n'th score in the list is less than the score to add.
 If the n'th score is less than the score to add, then insert the score to
 add in place of the n'th score */

  void addScore(const Score & score) {
    if( scores.size() < 10 ) {
      scores.push_back(score);
    } else if( scores.back() < score ) {
      for( int n=0; n<scores.size(); ++n ) {
        if( scores.at(n) < score ) {
          scores.insert( n, score );
          break;
        }
      }
      while( scores.size() > 10 ) {
        scores.pop_back();
      }
    }
  }
};

Answer 3

std::priority_queue是一个STL容器，专为此目的而开发。优先级队列负责排序，并允许使用push成员函数动态插入新元素。

以下是您的问题可以解决的方法：

#include <queue>
#include <vector>
#include <iostream>

std::vector<int> queue2vector(std::priority_queue<int>& q){  
  std::vector<int> v;
  while(!q.empty()) {
    v.push_back(q.top());
    q.pop();
  }
  return v;
}

int main() {
  std::priority_queue<int> q;
  // initialization (the scores are sorted upon insertion into the queue)
  std::vector<int> scores = {100, 50, 385, 350, 20, 200, 265, 500, 400, 300};  
  for(int n : scores)    
    q.push(n);
  // insert new element:
  q.push(425);
  // copy to std::vector:
  scores = queue2vector(q);
  // truncate vector to include only the first 10 entries:
  if(scores.size() > 10) scores.resize(10);     
  // output:
  for(int n : scores)
    std::cout << n << ' ';
  std::cout << std::endl;
}

输出：

500 425 400 385 350 300 265 200 100 50