Вид по доверенности (или: отсортируйте один контейнер по содержанию другого) в C++

Создайте вектор объектов, которые содержат индексы для двух массивов. Определите operator < для этого объекта, чтобы выполнять сравнение на основе ключей [index] . Отсортируйте этот вектор. Когда вы закончите, пройдите по этому вектору и разместите исходные объекты в порядке, определенном этими прокси-объектами:

// warning: untested code.
struct sort_proxy { 
    size_t i;

    bool operator<(sort_proxy const &other) const { 
        return keys[i] < keys[other.i];
    }
};

// ... key_size = number of keys/data items.
std::vector<sort_proxy> proxies(key_size); 

for (i=0; i<keys_size; i++)
    proxies[i].i = i;

std::sort(proxies.begin(), proxies.end());

// in-place reordering left as an exercise for the reader. :-)
for (int i=0; i<proxies[i].size(); i++) {
    result_keys[i] = keys[proxies[i].i];
    result_data[i] = data[proxies[i].i];
}

Вы можете использовать карту:

int main() {
  vector<int> keys;
  vector<string> data;
  keys.push_back(5); data.push_back("joe");
  keys.push_back(2); data.push_back("yaochun");
  keys.push_back(1); data.push_back("holio");

  // load the keys and data to the map (they will automatically be inserted in sorted order by key)
  map<int, string> sortedVals;
  for(int i = 0; i < (int)keys.size(); ++i) {
    sortedVals[keys[i]] = data[i];
  }

  // copy the map values back to vectors  
  int ndx=0;
  for(map<int, string>::iterator it = sortedVals.begin(); it != sortedVals.end(); ++it) {
    keys[ndx] = it->first;
    data[ndx] = it->second;
    ++ndx;
  }

  // verify
  for(int i = 0; i < (int)keys.size(); ++i) {
    cout<<keys[i]<<" "<<data[i]<<endl;
  }

  return 0;
}

Вот результат:

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c c:\temp\temp.exe
1 holio
2 yaochun
5 joe

> Terminated with exit code 0.

Эта проблема действительно заставила меня задуматься. Я придумал решение, которое использует некоторые функции C ++ 0x для получения алгоритма, очень похожего на STL parallel_sort . Чтобы выполнить сортировку «на месте», мне пришлось написать back_remove_iterator в качестве аналога back_insert_iterator , чтобы позволить алгоритму читать и писать в один и тот же контейнер. Вы можете пропустить эти части и сразу перейти к интересному.

Я не подвергал его жесткому тестированию, но он кажется достаточно эффективным как во времени, так и в пространстве, в основном из-за использования std :: move () для предотвращения ненужного копирования.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>


//
// An input iterator that removes elements from the back of a container.
// Provided only because the standard library neglects one.
//
template<class Container>
class back_remove_iterator :
    public std::iterator<std::input_iterator_tag, void, void, void, void> {
public:


    back_remove_iterator() : container(0) {}
    explicit back_remove_iterator(Container& c) : container(&c) {}

    back_remove_iterator& operator=
        (typename Container::const_reference value) { return *this; }

    typename Container::value_type operator*() {

        typename Container::value_type value(container->back());
        container->pop_back();
        return value;

    } // operator*()

    back_remove_iterator& operator++() { return *this; }
    back_remove_iterator operator++(int) { return *this; }


    Container* container;


}; // class back_remove_iterator


//
// Equivalence operator for back_remove_iterator. An iterator compares equal
// to the end iterator either if it is default-constructed or if its
// container is empty.
//
template<class Container>
bool operator==(const back_remove_iterator<Container>& a,
    const back_remove_iterator<Container>& b) {

    return !a.container ? !b.container || b.container->empty() :
        !b.container ? !a.container || a.container->empty() :
        a.container == b.container;

} // operator==()


//
// Inequivalence operator for back_remove_iterator.
//
template<class Container>
bool operator!=(const back_remove_iterator<Container>& a,
    const back_remove_iterator<Container>& b) {

    return !(a == b);

} // operator!=()


//
// A handy way to default-construct a back_remove_iterator.
//
template<class Container>
back_remove_iterator<Container> back_remover() {

    return back_remove_iterator<Container>();

} // back_remover()


//
// A handy way to construct a back_remove_iterator.
//
template<class Container>
back_remove_iterator<Container> back_remover(Container& c) {

    return back_remove_iterator<Container>(c);

} // back_remover()


//
// A comparison functor that sorts std::pairs by their first element.
//
template<class A, class B>
struct sort_pair_by_first {

    bool operator()(const std::pair<A, B>& a, const std::pair<A, B>& b) {

        return a.first < b.first;

    } // operator()()

}; // struct sort_pair_by_first


//
// Performs a parallel sort of the ranges [keys_first, keys_last) and
// [values_first, values_last), preserving the ordering relation between
// values and keys. Sends key and value output to keys_out and values_out.
//
// This works by building a vector of std::pairs, sorting them by the key
// element, then returning the sorted pairs as two separate sequences. Note
// the use of std::move() for a vast performance improvement.
//
template<class A, class B, class I, class J, class K, class L>
void parallel_sort(I keys_first, I keys_last, J values_first, J values_last,
                   K keys_out, L values_out) {

    typedef std::vector< std::pair<A, B> > Pairs;
    Pairs sorted;

    while (keys_first != keys_last)
        sorted.push_back({std::move(*keys_first++), std::move(*values_first++)});

    std::sort(sorted.begin(), sorted.end(), sort_pair_by_first<A, B>());

    for (auto i = sorted.begin(); i != sorted.end(); ++i)
        *keys_out++ = std::move(i->first),
        *values_out++ = std::move(i->second);

} // parallel_sort()


int main(int argc, char** argv) {

    //
    // There is an ordering relation between keys and values,
    // but the sets still need to be sorted. Sounds like a job for...
    //
    std::vector<int> keys{0, 3, 1, 2};
    std::vector<std::string> values{"zero", "three", "one", "two"};

    //
    // parallel_sort! Unfortunately, the key and value types do need to
    // be specified explicitly. This could be helped with a utility
    // function that accepts back_remove_iterators.
    //
    parallel_sort<int, std::string>
        (back_remover(keys), back_remover<std::vector<int>>(),
        back_remover(values), back_remover<std::vector<std::string>>(),
        std::back_inserter(keys), std::back_inserter(values));

    //
    // Just to prove that the mapping is preserved.
    //
    for (unsigned int i = 0; i < keys.size(); ++i)
        std::cout << keys[i] << ": " << values[i] << '\n';

    return 0;

} // main()

Надеюсь, это окажется полезным или, по крайней мере, развлекательным.

Для сортировки можно использовать функторы, например:

template <class T>
struct IndexFunctor {
  IndexFunctor(const std::vector<T>& v_) : v(v_) {}
  bool operator ()(int a, int b) const {
    return v[a] < v[b];
  }
  const std::vector<T>& v;
};

template <class K, class D>
void SortByKeys(std::vector<K>& keys, std::vector<D>& data) {
  // Calculate the valid order inside a permutation array p.
  const int n = static_cast<int>(keys.size());
  std::vector<int> p(n);
  for (int i = 0; i < n; ++i) p[i] = i;
  std::sort(p.begin(), p.end(), IndexFunctor(keys));

  // Reorder the keys and data in temporary arrays, it cannot be done in place.
  std::vector<K> aux_keys(n);
  std::vector<D> aux_data(n);
  for (int i = 0; i < n; ++i) {
    aux_keys[i] = keys[p[i]];
    aux_data[i] = data[p[i]];
  }

  // Assign the ordered vectors by swapping, it should be faster.
  keys.swap(aux_keys);
  data.swap(aux_data);
}

Вот пример реализации, который определяет новый тип итератора для обеспечения парного представления над двумя последовательностями. Я попытался сделать его соответствующим стандартам и корректным, но поскольку стандарт C++ ужасно сложен в своих деталях, я почти уверен, что потерпел неудачу. Я скажу, что этот код, похоже, работает при сборке с clang++ или g++.

Этот код не рекомендуется для общего использования, поскольку он длиннее и менее понятен, чем другие ответы, и, возможно, вызывает ужасное "неопределенное поведение".

Однако, у него есть преимущество в виде постоянных временных и пространственных затрат, поскольку он предоставляет представление существующих данных, а не создает временное альтернативное представление или вектор перестановок. Наиболее очевидная (для меня) проблема производительности этого кода заключается в том, что отдельные элементы двух контейнеров должны быть скопированы во время операции замены. Несмотря на несколько попыток, я не нашел способа успешно специализировать std::swap так, чтобы std::sort или std::random_shuffle избегали использования реализации свопа, основанной на временной копии по умолчанию. Возможно, что использование системы ссылок на rvalue в C++0x (см. std::move и ответ Джона Перди) может решить эту проблему.

#ifndef HDR_PAIRED_ITERATOR
#define HDR_PAIRED_ITERATOR

#include <iterator>

/// pair_view mostly looks like a std::pair,
/// and can decay to a std::pair, but is really a pair of references
template <typename ItA, typename ItB>
struct pair_view {
    typedef typename ItA::value_type first_type;
    typedef typename ItB::value_type second_type;

    typedef std::pair<first_type, second_type> pair_type;

    pair_view() {}
    pair_view(const ItA &a, const ItB &b):
        first(*a), second(*b) {}

    pair_view &operator=(const pair_view &x)
        { first = x.first; second = x.second; return *this; }
    pair_view &operator=(const pair_type &x)
        { first = x.first; second = x.second; return *this; }

    typename ItA::reference first;
    typename ItB::reference second;
    operator pair_type() const
        { return std::make_pair(first, second); }

    friend bool operator==(const pair_view &a, const pair_view &b)
        { return (a.first == b.first) && (a.second == b.second); }
    friend bool operator<(const pair_view &a, const pair_view &b)
        { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); }
    friend bool operator!=(const pair_view &a, const pair_view &b)
        { return !(a == b); }
    friend bool operator>(const pair_view &a, const pair_view &b)
        { return (b < a); }
    friend bool operator<=(const pair_view &a, const pair_view &b)
        { return !(b < a); }
    friend bool operator>=(const pair_view &a, const pair_view &b)
        { return !(a < b); }

    friend bool operator==(const pair_view &a, const pair_type &b)
        { return (a.first == b.first) && (a.second == b.second); }
    friend bool operator<(const pair_view &a, const pair_type &b)
        { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); }
    friend bool operator!=(const pair_view &a, const pair_type &b)
        { return !(a == b); }
    friend bool operator>(const pair_view &a, const pair_type &b)
        { return (b < a); }
    friend bool operator<=(const pair_view &a, const pair_type &b)
        { return !(b < a); }
    friend bool operator>=(const pair_view &a, const pair_type &b)
        { return !(a < b); }

    friend bool operator==(const pair_type &a, const pair_type &b)
        { return (a.first == b.first) && (a.second == b.second); }
    friend bool operator<(const pair_type &a, const pair_type &b)
        { return (a.first < b.first) || ((a.first == b.first) && (a.second < b.second)); }
    friend bool operator!=(const pair_type &a, const pair_type &b)
        { return !(a == b); }
    friend bool operator>(const pair_type &a, const pair_type &b)
        { return (b < a); }
    friend bool operator<=(const pair_type &a, const pair_type &b)
        { return !(b < a); }
    friend bool operator>=(const pair_type &a, const pair_type &b)
        { return !(a < b); }
};

template <typename ItA, typename ItB>
struct paired_iterator {
    // --- standard iterator traits
    typedef typename pair_view<ItA, ItB>::pair_type value_type;
    typedef pair_view<ItA, ItB> reference;
    typedef paired_iterator<ItA,ItB> pointer;

    typedef typename std::iterator_traits<ItA>::difference_type difference_type;
    typedef std::random_access_iterator_tag iterator_category;

    // --- methods not required by the Random Access Iterator concept
    paired_iterator(const ItA &a, const ItB &b):
        a(a), b(b) {}

    // --- iterator requirements

    // default construction
    paired_iterator() {}

    // copy construction and assignment
    paired_iterator(const paired_iterator &x):
        a(x.a), b(x.b) {}
    paired_iterator &operator=(const paired_iterator &x)
        { a = x.a; b = x.b; return *this; }

    // pre- and post-increment
    paired_iterator &operator++()
        { ++a; ++b; return *this; }
    paired_iterator operator++(int)
        { paired_iterator tmp(*this); ++(*this); return tmp; }

    // pre- and post-decrement
    paired_iterator &operator--()
        { --a; --b; return *this; }
    paired_iterator operator--(int)
        { paired_iterator tmp(*this); --(*this); return tmp; }

    // arithmetic
    paired_iterator &operator+=(const difference_type &n)
        { a += n; b += n; return *this; }
    friend paired_iterator operator+(const paired_iterator &x, const difference_type &n)
        { return paired_iterator(x.a+n, x.b+n); }
    friend paired_iterator operator+(const difference_type &n, const paired_iterator &x)
        { return paired_iterator(x.a+n, x.b+n); }
    paired_iterator &operator-=(const difference_type &n)
        { a -= n; b -= n; return *this; }
    friend paired_iterator operator-(const paired_iterator &x, const difference_type &n)
        { return paired_iterator(x.a-n, x.b-n); }
    friend difference_type operator-(const paired_iterator &x, const paired_iterator &y)
        { return (x.a - y.a); }

    // (in-)equality and ordering
    friend bool operator==(const paired_iterator &x, const paired_iterator &y)
        { return (x.a == y.a) && (x.b == y.b); }
    friend bool operator<(const paired_iterator &x, const paired_iterator &y)
        { return (x.a < y.a); }

    // derived (in-)equality and ordering operators
    friend bool operator!=(const paired_iterator &x, const paired_iterator &y)
        { return !(x == y); }
    friend bool operator>(const paired_iterator &x, const paired_iterator &y)
        { return (y < x); }
    friend bool operator<=(const paired_iterator &x, const paired_iterator &y)
        { return !(y < x); }
    friend bool operator>=(const paired_iterator &x, const paired_iterator &y)
        { return !(x < y); }

    // dereferencing and random access
    reference operator*() const
        { return reference(a,b); }
    reference operator[](const difference_type &n) const
        { return reference(a+n, b+n); }
private:
    ItA a;
    ItB b;
};

template <typename ItA, typename ItB>
paired_iterator<ItA, ItB> make_paired_iterator(const ItA &a, const ItB &b)
{ return paired_iterator<ItA, ItB>(a, b); }

#endif


#include <vector>
#include <algorithm>
#include <iostream>

template <typename ItA, typename ItB>
void print_kvs(const ItA &k0, const ItB &v0, const ItA &kn, const ItB &vn) {
    ItA k(k0);
    ItB v(v0);
    while (k != kn || v != vn) {
        if (k != kn && v != vn)
            std::cout << "[" << *k << "] = " << *v << "\n";
        else if (k != kn)
            std::cout << "[" << *k << "]\n";
        else if (v != vn)
            std::cout << "[?] = " << *v << "\n";

        if (k != kn) ++k;
        if (v != vn) ++v;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> keys;
    std::vector<std::string> data;

    keys.push_back(0); data.push_back("zero");
    keys.push_back(1); data.push_back("one");
    keys.push_back(2); data.push_back("two");
    keys.push_back(3); data.push_back("three");
    keys.push_back(4); data.push_back("four");
    keys.push_back(5); data.push_back("five");
    keys.push_back(6); data.push_back("six");
    keys.push_back(7); data.push_back("seven");
    keys.push_back(8); data.push_back("eight");
    keys.push_back(9); data.push_back("nine");

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end());

    std::cout << "Shuffling\n";
    std::random_shuffle(
        make_paired_iterator(keys.begin(), data.begin()),
        make_paired_iterator(keys.end(), data.end())
    );

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end());

    std::cout << "Sorting\n";
    std::sort(
        make_paired_iterator(keys.begin(), data.begin()),
        make_paired_iterator(keys.end(), data.end())
    );

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end());

    std::cout << "Sort descending\n";
    std::sort(
        make_paired_iterator(keys.begin(), data.begin()),
        make_paired_iterator(keys.end(), data.end()),
        std::greater< std::pair<int,std::string> >()
    );

    print_kvs(keys.begin(), data.begin(), keys.end(), data.end());

    return 0;
}