Sort a lightweight index: keep original data order, and write the invalidation rules clearly

View order need not equal storage order

Item 34 analyzes index tables rather than rewriting a sorting algorithm. The same idea is applied here to job records that have names and durations: the original array order represents submission order, and another index sequence represents display order from shortest to longest. Sorting only moves size_t values; it does not move names and complete records, nor copy a second job list.

This example chooses position indexes rather than storing iterators, so the interface is explicitly limited to a randomly accessible fixed array. No adapter layer is invented for possibly arbitrary containers; the actual need is only this one stable data set, so a simple representation suffices. Extensibility should come from real usage scenarios, not from having more template parameters.

The comparison rule includes the decision on ties

The comparator reads job durations via subscripts. When durations differ the smaller value is preferred; when they are equal the original position is preferred, forming a deterministic display order. Therefore assertions can verify the exact index sequence without relying on std::sort's unspecified arrangement of equivalent elements. If the business only requires preserving the order of equal keys from the input, stable_sort can also be chosen.

The comparator captures a reference to the source array; this reference is used only during the synchronous sort call, and the source array always lives and is unmodified. Returning indexes does not copy records and does not obtain ownership of the data; it merely lets the caller interpret the same batch of objects in a second order.

Saving moves does not exempt from maintenance

An index must be interpreted together with the source data. For a vector, mere reallocation does not change position numbers, but insertion, erasure, or wholesale rearrangement in the middle will change which object a number corresponds to; stored iterators are additionally affected by reallocation. Even if record positions stay the same, updating only a duration field may make the old display order stale.

Therefore rules should be established before using an index view: freeze the source data for the duration of the view, or rebuild the index after modification. The current complete program chooses the former, writing the rule directly into the type with a const fixed array. The book's advice on readability and reusing the standard library is embodied here as reducing handwritten management logic, not as line-by-line transplantation of helper classes from twenty years ago.

Pitfalls

• An index being in range only proves that access does not go out of bounds; it does not prove that it still points to the originally intended business record.
• The keys read by the comparator must remain consistent during sorting; duration must not be modified inside the comparison function, nor may it depend on how many times comparison is called.

Minimum C++11 · complete program · Download .cpp

#include <algorithm>
#include <array>
#include <cassert>
#include <cstddef>
#include <numeric>
#include <string>

struct Job {
    std::string name;
    int duration;
};

int main() {
    const std::array<Job, 4> jobs{{
        {"parse", 7}, {"cache", 3}, {"index", 7}, {"send", 1}
    }};
    std::array<std::size_t, 4> order{};
    std::iota(order.begin(), order.end(), std::size_t{0});
    std::sort(order.begin(), order.end(), [&jobs](std::size_t a, std::size_t b) {
        if (jobs[a].duration != jobs[b].duration) {
            return jobs[a].duration < jobs[b].duration;
        }
        return a < b;
    });
    assert((order == std::array<std::size_t, 4>{{3, 1, 0, 2}}));
    assert(jobs[0].name == "parse");
    assert(jobs[order[0]].name == "send");
    assert(jobs[order[2]].name == "parse");
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread books-exceptional-cpp-style.cpp -o example && ./example

Expected result

Expected: exit 0, no output; every assert holds.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

To change to duration from large to small, while still preferring original position on equal duration, which place should be changed?

Check the sources

• Exceptional C++ Style Item 34, pp.246–257
• C++ draft [alg.sorting] — strict weak ordering

Drafts and official chapters change. The version mark is only the example’s minimum.