Pairs and precise tie rules
Keep related values together and make ordering requirements explicit.
Two related fields travel together
std::pair<A, B> holds first and second, possibly with different types. A pair<string, int> can store a name and score. These are fields, so write result.first rather than result.first(). A pair has no size() and is not indexed like an array.
State what the fields mean: (score, ID), (time, ID), or (minimum, maximum). A vector of pairs moves each whole record during sorting, preserving that relationship. A helper returning a pair can return two related answers together.
Default ordering is first field, then second
Ascending integer-pair order compares first fields, then second fields only on a tie. Thus (1, 100) precedes (2, 0); the sums of the fields are irrelevant. For (time, ID), ascending order means earlier time then smaller ID.
A task requiring larger score and smaller ID has mixed directions and needs a custom rule. std::sort does not promise to preserve input order among equivalent keys. Store an arrival index when arrival order is the required tiebreaker.
Optional: a strict named comparator
For std::sort, the comparator answers whether a should precede b. For higher score then smaller ID, compare scores with > and tied IDs with <. The ordering must be strict and consistent; comparing a value with itself must return false.
Using >= to include equality is invalid: it can claim an item belongs before itself and violates the algorithm’s comparator requirements. Test equal scores with different IDs, and duplicate pairs, before trusting an ordering.
// Complete C++23 program. No input; output: 90 2, 90 3, 80 1.
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
bool higherScore(const std::pair<int, int>& a,
const std::pair<int, int>& b) {
if (a.first != b.first) return a.first > b.first;
return a.second < b.second;
}
int main() {
std::vector<std::pair<int, int>> students{{90, 3}, {80, 1}, {90, 2}};
std::sort(students.begin(), students.end(), higherScore);
for (const auto& student : students) {
std::cout << student.first << ' ' << student.second << '\n';
}
}Optional: more convenient pair syntax
emplace_back(id, score) constructs a pair from those arguments in a vector. push_back({id, score}) is also valid; emplacement is not an automatic speed guarantee.
auto [id, score] = result introduces names bound to a copied pair value. auto& [id, score] = result refers to the existing pair. Use const auto& for read-only access without copying, and do not keep bound references across an operation that invalidates vector element references.
Container workbench
Insert values, then remove the next accessible item. Priority queue values are shown sorted for explanation, not as an internal heap.
Next removal: 5. Size: 3.
Guided simulation · Change the inputs to test your understanding.
Which pair comes first in default ascending order: (1, 50) or (2, 3)?
Turn the idea into code
For a nonempty list of scores in [0, 100], return a pair containing the highest score and the one-based position of its first occurrence. Test 70 95 95 60 90.
Give me a hint
Initialize from the first score. Update only when a strictly higher score appears.
Show the explained solution
The pair tracks the earliest best score in each processed prefix. Strict comparison keeps the first occurrence on ties. For the sample, the result is (95, 2); time is O(n), with O(1) helper auxiliary space.
// Complete C++23 program. Input: 1 <= n <= 200000, then n scores.
#include <iostream>
#include <utility>
#include <vector>
std::pair<int, int> firstHighest(const std::vector<int>& scores) {
std::pair<int, int> answer{scores[0], 1};
for (int i = 1; i < static_cast<int>(scores.size()); ++i) {
if (scores[i] > answer.first) answer = {scores[i], i + 1};
}
return answer;
}
int main() {
int n = 0;
std::cin >> n;
std::vector<int> scores(n);
for (int& x : scores) std::cin >> x;
auto answer = firstHighest(scores);
std::cout << answer.first << ' ' << answer.second << '\n';
}Your notes
Mark complete when you can explain it yourself.