根据字符串在句子中的位置对这些字符串输入进行排序的更快方法是什么？

Question

在全国信息学奥林匹克竞赛的练习中遇到了一个问题，问题如下:用户输入句子中的单词数量(n)，输入单词的收益以及由空格分隔的位置。要求你按正确的词序输入句子。

例如：

输入：

4
this 1
sentence 4
is 2
a 3

输出：

this is a sentence

限制：

1 <= N <= 3 * 10^5
1 <= Size of a word <= 50

我试着用unordered_map解决这个问题，结果这个问题解决得相当快，只用了0.588秒，检查了所有的测试用例，这使得我的解决方案在45个测试用例中排名第五。然而，最快的解决方案只需要0.14秒的计算时间，我不知道他/她是如何做到的。解决此问题比使用unordered_map更快的方法是什么？

unordered_map < int, string > words;    
int n;    
cin >> n;  
for (int i = 0; i < n; i++) {    
    string word;    
    int position;     
    cin >> word >> position;    
    words[position] = word;    
}    
for (int i = 1; i <= n; i++) {     
    cout << words[i] << "\n";      
} 

Answer 1

对于这个问题，std::unordered_map有点过头了。由于提供了元素的顺序，因此可以使用std::vector<std::string>，只需将元素放在输入告诉您的向量中即可。这简化了程序代码，以

int main()
{
    int records;
    std::cin >> records;
    std::vector<std::string> sentence(records);
    std::string word;
    int place;
    while (std::cin >> word >> place)
        sentence[place - 1] = std::move(word); // subtract one as input is 1 based index, use move to save an allocation and copy
    for (auto const& e : sentence)
        std::cout << e << " ";
}