"Is there an easy STL way to sort a structure of arrays? Imagine array of keys and array of values, sort by key such that a single index will access both key and associated value."

array_pair_dict.cpp

// Copyright 2016 Nicolás Alvarez

// As long as you retain this notice you can do whatever you want
// with this stuff. If we meet some day, and you think this stuff
// is worth it, you can buy me some chocolate in return.

#include <cstdio>    // printf
#include <iterator>  // iterator category tags
#include <algorithm> // sort
#include <utility>   // pair

struct DictIterator;

struct Dict {
    size_t length;
    int* keys;
    const char** values;

    typedef std::pair<int, const char*> Entry;

    Dict() {
        length = 5;
        keys = new int[length];
        values = new const char*[length];
        keys[0] = 41; values[0] = "forty one";
        keys[1] = 36; values[1] = "thirty six";
        keys[2] = 73; values[2] = "seventy three";
        keys[3] = 61; values[3] = "sixty one";
        keys[4] = 25; values[4] = "twenty five";
    }
    ~Dict() {
        delete[] keys;
        delete[] values;
    }
    inline DictIterator begin();
    inline DictIterator end();
};
struct DictItem {
    Dict& dict;
    const size_t idx;
    DictItem(Dict& dict, size_t idx): dict(dict), idx(idx) {}
    
    operator Dict::Entry() const { return {key(), value()}; }

    int key() const {
        return dict.keys[idx];
    }
    const char* value() const {
        return dict.values[idx];
    }
    
    DictItem& operator=(const Dict::Entry& other) {
        dict.keys[idx] = other.first;
        dict.values[idx] = other.second;
        return *this;
    }
    DictItem& operator=(const DictItem& other) {
        dict.keys[idx] = other.key();
        dict.values[idx] = other.value();
        return *this;
    }
};

inline void swap(DictItem a, DictItem b) {
    std::swap(a.dict.keys[a.idx], b.dict.keys[b.idx]);
    std::swap(a.dict.values[a.idx], b.dict.values[b.idx]);
}
struct DictIterator {
    typedef Dict::Entry value_type;
    typedef ssize_t difference_type;
    typedef Dict::Entry* pointer;
    typedef Dict::Entry& reference;
    typedef std::bidirectional_iterator_tag iterator_category;

    Dict& dict;
    size_t idx;
    DictIterator(Dict& dict, size_t idx): dict(dict), idx(idx) {}

    DictItem operator*() {
        return DictItem(dict, idx);
    }
    DictIterator& operator++() {
        ++idx;
        return *this;
    }
    DictIterator& operator--() {
        --idx;
        return *this;
    }
    DictIterator operator+(int offset) const {
        return DictIterator(dict, idx+offset);
    }
    DictIterator operator-(int offset) const {
        return DictIterator(dict, idx-offset);
    }
    ssize_t operator-(const DictIterator& rhs) const {
        return (idx - rhs.idx);
    }
    bool operator<(const DictIterator& rhs) const {
        return (idx < rhs.idx);
    }
    bool operator==(const DictIterator& rhs) const {
        return (idx == rhs.idx);
    }
    bool operator!=(const DictIterator& rhs) const {
        return (idx != rhs.idx);
    }
    DictIterator& operator=(const DictIterator& rhs) {
        idx = rhs.idx;
        return *this;
    }
};
DictIterator Dict::begin() {
    return DictIterator(*this, 0);
}
DictIterator Dict::end() {
    return DictIterator(*this, length);
}

void dump(Dict& dict) {
    printf("{ ");
    for (DictIterator it = dict.begin(); it < dict.end(); ++it) {
        printf("%d: %s, ", (*it).key(), (*it).value());
    }
    printf("\b\b }\n");
}

int main() {
    Dict dict;
    dump(dict);
    printf("Sorting...\n");
    std::sort(dict.begin(), dict.end(), [](const Dict::Entry& a, const Dict::Entry& b) {
        return a.first < b.first;
    });
    dump(dict);
}