sort_two.cpp

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const char* syms[] = {
    /* 0 */ "quux",
    /* 1 */ "foo",
    /* 2 */ "biff",
    /* 3 */ "baff",
    /* 4 */ "bar",
};

struct Bindings {
    vector<size_t> names; /* indices to syms array */
    vector<const char*> values;

    // A proxy object for which std::swap has been overloaded to swap both names[i] and values[i].
    // However, for small arrays libstdc++ uses insertion sort for which we need to support copy construction and move assignment as well.
    // (See https://stackoverflow.com/a/14213387)
    struct SwapWrapper {
        Bindings* owner;
        ssize_t i;

        // If owner is nullptr, then this proxy represents a 'temporary' holding a (this->name, this->value) pair,
        // otherwise this proxy represents a reference to (this->owner->names[i], this->owner->values[i])
        size_t name;
        const char* value;

        size_t getName() const { return owner ? owner->names[i] : name; }
        const char* getValue() const { return owner ? owner->values[i] : value; }

        SwapWrapper() = delete;
        SwapWrapper& operator=(SwapWrapper& rhs) = delete;

        SwapWrapper(Bindings* owner, size_t i) : owner(owner), i(i) { }

        SwapWrapper(const SwapWrapper& rhs) : owner(nullptr), i(rhs.i), name(rhs.getName()), value(rhs.getValue()) { }

        SwapWrapper(SwapWrapper&& rhs) : owner(nullptr), i(rhs.i), name(rhs.getName()), value(rhs.getValue()) { }

        SwapWrapper& operator=(SwapWrapper&& rhs) {
            if (owner) {
                owner->names[i] = rhs.getName();
                owner->values[i] = rhs.getValue();
            } else {
                name = rhs.getName();
                value = rhs.getValue();
            }
            return *this;
        }
    };

    struct iterator {
        Bindings* owner;
        size_t i;

        typedef ssize_t difference_type;
        typedef SwapWrapper value_type;
        typedef SwapWrapper* pointer;
        typedef SwapWrapper& reference;
        typedef std::random_access_iterator_tag iterator_category;

        // Slight hack - usually operator*() returns a reference but this doesn't.
        SwapWrapper operator*() { return SwapWrapper(owner, i); }

        bool operator<(const Bindings::iterator& rhs) const { return i < rhs.i; }
        bool operator!=(const Bindings::iterator& rhs) const { return i != rhs.i; }
        bool operator==(const Bindings::iterator& rhs) const { return i == rhs.i; }

        difference_type operator-(const Bindings::iterator& rhs) const { return i - rhs.i; }

        Bindings::iterator operator+(difference_type n) const { return Bindings::iterator{owner, i + n}; }
        Bindings::iterator operator-(difference_type n) const { return Bindings::iterator{owner, i - n}; }

        Bindings::iterator operator++() { this->i++; return *this; }
        Bindings::iterator operator--() { this->i--; return *this; }
    };
};

// Slight hack - usually operator*() returns a reference but this doesn't.
void swap(Bindings::SwapWrapper lhs, Bindings::SwapWrapper rhs) {
    swap(lhs.owner->names[lhs.i], rhs.owner->names[rhs.i]);
    swap(lhs.owner->values[lhs.i], rhs.owner->values[rhs.i]);
}

bool cmpBySymbolOrder(const Bindings::SwapWrapper& lhs, const Bindings::SwapWrapper& rhs) {
    return lhs.getName() < rhs.getName();
}

bool cmpLexicographically(const Bindings::SwapWrapper& lhs, const Bindings::SwapWrapper& rhs) {
    return strcmp(syms[lhs.getName()], syms[rhs.getName()]) < 0;
}

void sortSymbolOrder(Bindings& bindings) {
    Bindings::iterator begin{&bindings, 0};
    Bindings::iterator end{&bindings, bindings.names.size()};
    std::sort(begin, end, cmpBySymbolOrder);
}

void sortLexicographically(Bindings& bindings) {
    Bindings::iterator begin{&bindings, 0};
    Bindings::iterator end{&bindings, bindings.names.size()};
    std::sort(begin, end, cmpLexicographically);
}

void print(Bindings& bindings) {
    for (size_t i = 0; i < bindings.names.size(); i++) {
        printf("    %s = %s\n", syms[bindings.names[i]], bindings.values[i]);
    }
}

int main() {
    Bindings b;

    b.names.push_back(1);
    b.values.push_back("foo");

    b.names.push_back(4);
    b.values.push_back("bar");

    b.names.push_back(2);
    b.values.push_back("biff");

    printf("In original order:\n");
    print(b);

    printf("In symbol order:\n");
    sortSymbolOrder(b);
    print(b);

    printf("In lexicographical order:\n");
    sortLexicographically(b);
    print(b);
}