c++ - una - vectores en c

¿Cómo puedo ordenar un std:: vector por los valores de un std:: vector diferente?

Question

Tengo varios std::vector , todos de la misma longitud. Quiero ordenar uno de estos vectores y aplicar la misma transformación a todos los demás vectores. ¿Hay una buena manera de hacer esto? (preferiblemente usando el STL o Boost)? Algunos de los vectores contienen int s y algunos de ellos std::string s.

Pseudo código:

std::vector<int> Index = { 3, 1, 2 };
std::vector<std::string> Values = { "Third", "First", "Second" };
Transformation = sort(Index);
Index is now { 1, 2, 3};
... magic happens as Transformation is applied to Values ...
Values are now { "First", "Second", "Third" };

Answer 1

Aquí hay una implementación relativamente simple que utiliza la asignación de índice entre los names ordenados y desordenados que se utilizarán para hacer coincidir las ages con los names ordenados:

void ordered_pairs()
{
std::vector<std::string> names;
std::vector<int> ages;
// read input and populate the vectors
populate(names, ages);
// print input
print(names, ages);
// sort pairs
std::vector<std::string> sortedNames(names);
std::sort(sortedNames.begin(), sortedNames.end());
std::vector<int> indexMap;
for(unsigned int i = 0; i < sortedNames.size(); ++i)
{
for (unsigned int j = 0; j < names.size(); ++j)
{
if (sortedNames[i] == names[j])
{
indexMap.push_back(j);
break;
}
}
}
// use the index mapping to match the ages to the names
std::vector<int> sortedAges;
for(size_t i = 0; i < indexMap.size(); ++i)
{
sortedAges.push_back(ages[indexMap[i]]);
}
std::cout << "Ordered pairs:/n";
print(sortedNames, sortedAges);
}

Para completar, aquí están las funciones populate() e print() :

void populate(std::vector<std::string>& n, std::vector<int>& a)
{
std::string prompt("Type name and age, separated by white space; ''q'' to exit./n>>");
std::string sentinel = "q";
while (true)
{
// read input
std::cout << prompt;
std::string input;
getline(std::cin, input);
// exit input loop
if (input == sentinel)
{
break;
}
std::stringstream ss(input);
// extract input
std::string name;
int age;
if (ss >> name >> age)
{
n.push_back(name);
a.push_back(age);
}
else
{
std::cout <<"Wrong input format!/n";
}
}
}

y:

void print(const std::vector<std::string>& n, const std::vector<int>& a)
{
if (n.size() != a.size())
{
std::cerr <<"Different number of names and ages!/n";
return;
}
for (unsigned int i = 0; i < n.size(); ++i)
{
std::cout <<''('' << n[i] << ", " << a[i] << '')'' << "/n";
}
}

Y finalmente, main() convierte en:

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
void ordered_pairs();
void populate(std::vector<std::string>&, std::vector<int>&);
void print(const std::vector<std::string>&, const std::vector<int>&);
//=======================================================================
int main()
{
std::cout << "/t/tSimple name - age sorting./n";
ordered_pairs();
}
//=======================================================================
// Function Definitions...

Answer 2

Coloque sus valores en un contenedor Boost Multi-Index y repítalo para leer los valores en el orden que desee. Incluso puede copiarlos a otro vector si lo desea.

Answer 3

Creo que lo que realmente necesitas (pero corrígeme si estoy equivocado) es una forma de acceder a los elementos de un contenedor en algún orden.

En lugar de reorganizar mi colección original, tomaría prestado un concepto del diseño de la base de datos: mantener un índice ordenado según un determinado criterio. Este índice es una indirección adicional que ofrece una gran flexibilidad.

De esta forma, es posible generar múltiples índices de acuerdo con diferentes miembros de una clase.

using namespace std;
template< typename Iterator, typename Comparator >
struct Index {
vector<Iterator> v;
Index( Iterator from, Iterator end, Comparator& c ){
v.reserve( std::distance(from,end) );
for( ; from != end; ++from ){
v.push_back(from); // no deref!
}
sort( v.begin(), v.end(), c );
}
};
template< typename Iterator, typename Comparator >
Index<Iterator,Comparator> index ( Iterator from, Iterator end, Comparator& c ){
return Index<Iterator,Comparator>(from,end,c);
}
struct mytype {
string name;
double number;
};
template< typename Iter >
struct NameLess : public binary_function<Iter, Iter, bool> {
bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->name < t2->name; }
};
template< typename Iter >
struct NumLess : public binary_function<Iter, Iter, bool> {
bool operator()( const Iter& t1, const Iter& t2 ) const { return t1->number < t2->number; }
};
void indices() {
mytype v[] = { { "me" , 0.0 }
, { "you" , 1.0 }
, { "them" , -1.0 }
};
mytype* vend = v + _countof(v);
Index<mytype*, NameLess<mytype*> > byname( v, vend, NameLess<mytype*>() );
Index<mytype*, NumLess <mytype*> > bynum ( v, vend, NumLess <mytype*>() );
assert( byname.v[0] == v+0 );
assert( byname.v[1] == v+2 );
assert( byname.v[2] == v+1 );
assert( bynum.v[0] == v+2 );
assert( bynum.v[1] == v+0 );
assert( bynum.v[2] == v+1 );
}

Answer 4

El enfoque de friol es bueno cuando se combina con el tuyo. Primero, construye un vector que consta de los números 1 ... n , junto con los elementos del vector que dicta el orden de clasificación:

typedef vector<int>::const_iterator myiter;
vector<pair<size_t, myiter> > order(Index.size());
size_t n = 0;
for (myiter it = Index.begin(); it != Index.end(); ++it, ++n)
order[n] = make_pair(n, it);

Ahora puede ordenar esta matriz con un clasificador personalizado:

struct ordering {
bool operator ()(pair<size_t, myiter> const& a, pair<size_t, myiter> const& b) {
return *(a.second) < *(b.second);
}
};
sort(order.begin(), order.end(), ordering());

Ahora ha capturado el orden de reordenamiento dentro del order (más precisamente, en el primer componente de los ítems). Ahora puede usar este orden para ordenar sus otros vectores. Probablemente exista una variante en contexto muy inteligente que se ejecute al mismo tiempo, pero hasta que alguien más se le ocurra, aquí hay una variante que no está en su lugar. Utiliza el order como una tabla de búsqueda para el nuevo índice de cada elemento.

template <typename T>
vector<T> sort_from_ref(
vector<T> const& in,
vector<pair<size_t, myiter> > const& reference
) {
vector<T> ret(in.size());
size_t const size = in.size();
for (size_t i = 0; i < size; ++i)
ret[i] = in[reference[i].first];
return ret;
}

Answer 5

Esto habría sido una adición a la respuesta de Konrad, ya que es un enfoque para una variante in situ de aplicar el orden de clasificación a un vector. De todos modos, dado que la edición no se realizará, la pondré aquí

Aquí hay una variante in situ con una complejidad de tiempo ligeramente mayor que se debe a una operación primitiva de comprobación de un booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del compilador de espacio eficiente. La complejidad de un vector puede eliminarse si el orden dado puede ser modificado.

Aquí hay una variante in situ con una complejidad de tiempo ligeramente mayor que se debe a una operación primitiva de comprobación de un booleano. La complejidad de espacio adicional es de un vector que puede ser una implementación dependiente del compilador de espacio eficiente. La complejidad de un vector puede eliminarse si el orden dado puede ser modificado. Este es un ejemplo de lo que el algoritmo está haciendo. Si el orden es 3 0 4 1 2, el movimiento de los elementos según lo indicado por los índices de posición sería 3 ---> 0; 0 ---> 1; 1 ---> 3; 2 ---> 4; 4 ---> 2.

template<typename T>
struct applyOrderinPlace
{
void operator()(const vector<size_t>& order, vector<T>& vectoOrder)
{
vector<bool> indicator(order.size(),0);
size_t start = 0, cur = 0, next = order[cur];
size_t indx = 0;
T tmp;
while(indx < order.size())
{
//find unprocessed index
if(indicator[indx])
{
++indx;
continue;
}
start = indx;
cur = start;
next = order[cur];
tmp = vectoOrder[start];
while(next != start)
{
vectoOrder[cur] = vectoOrder[next];
indicator[cur] = true;
cur = next;
next = order[next];
}
vectoOrder[cur] = tmp;
indicator[cur] = true;
}
}
};

Answer 6

La respuesta de ltjax es un gran enfoque, que en realidad se implementa en el zip_iterator de boost http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html

Se empaqueta en una tupla cualquiera que sea el iterador que le proporcione.

A continuación, puede crear su propia función de comparación para una clasificación basada en cualquier combinación de valores de iterador en su tupla. Para esta pregunta, sería el primer iterador de tu tupla.

Una buena característica de este enfoque es que te permite mantener la memoria de cada vector individual contigua (si estás usando vectores y eso es lo que quieres). Tampoco necesita almacenar un vector de índice separado de ints.

Answer 7

Muchos hicieron esta pregunta y a nadie se le ocurrió una respuesta satisfactoria. Aquí hay un auxiliar std :: sort que permite ordenar dos vectores simultáneamente, teniendo en cuenta los valores de un solo vector. Esta solución se basa en un RadomIt personalizado (iterador aleatorio) y opera directamente en los datos vectoriales originales, sin copias temporales, reestructuración de la estructura o índices adicionales:

C ++, ordena un vector basado en otro

Answer 8

Probablemente pueda definir un iterador de "fachada" personalizado que haga lo que necesita aquí. Almacenaría iteradores a todos sus vectores o, alternativamente, derivaría los iteradores para todos menos el primer vector del desplazamiento del primero. La parte difícil es a lo que se refiere el iterador: piense en algo como boost :: tuple y haga un uso inteligente de boost :: tie. (Si desea ampliar esta idea, puede compilar estos tipos de iteradores de forma recursiva mediante plantillas, pero probablemente nunca desee escribir el tipo de eso, por lo que necesita c ++ 0x auto o una función de envoltura para ordenamiento que tome rangos)

Answer 9

Solo me viene a la mente una solución aproximada: crea un vector que sea la suma de todos los demás vectores (un vector de estructuras, como {3, Third, ...}, {1, First, ...}) luego ordena esto vector por el primer campo, y luego divide las estructuras nuevamente.

Probablemente hay una mejor solución dentro de Boost o usando la biblioteca estándar.

Answer 10

Una variante un poco más compacta de la respuesta de xtofl para si solo buscas iterar a través de todos tus vectores en base al vector de una sola keys . Crea un vector de permutación y úsalo para indexar en tus otros vectores.

#include <boost/iterator/counting_iterator.hpp>
#include <vector>
#include <algorithm>
std::vector<double> keys = ...
std::vector<double> values = ...
std::vector<size_t> indices(boost::counting_iterator<size_t>(0u), boost::counting_iterator<size_t>(keys.size()));
std::sort(begin(indices), end(indices), [&](size_t lhs, size_t rhs) {
return keys[lhs] < keys[rhs];
});
// Now to iterate through the values array.
for (size_t i: indices)
{
std::cout << values[i] << std::endl;
}

Answer 11

**// C++ program to demonstrate sorting in vector
// of pair according to 2nd element of pair
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>
using namespace std;
// Driver function to sort the vector elements
// by second element of pairs
bool sortbysec(const pair<char,char> &a,
const pair<int,int> &b)
{
return (a.second < b.second);
}
int main()
{
// declaring vector of pairs
vector< pair <char, int> > vect;
// Initialising 1st and 2nd element of pairs
// with array values
//int arr[] = {10, 20, 5, 40 };
//int arr1[] = {30, 60, 20, 50};
char arr[] = { '' a'', ''b'', ''c'' };
int arr1[] = { 4, 7, 1 };
int n = sizeof(arr)/sizeof(arr[0]);
// Entering values in vector of pairs
for (int i=0; i<n; i++)
vect.push_back( make_pair(arr[i],arr1[i]) );
// Printing the original vector(before sort())
cout << "The vector before sort operation is:/n" ;
for (int i=0; i<n; i++)
{
// "first" and "second" are used to access
// 1st and 2nd element of pair respectively
cout << vect[i].first << " "
<< vect[i].second << endl;
}
// Using sort() function to sort by 2nd element
// of pair
sort(vect.begin(), vect.end(), sortbysec);
// Printing the sorted vector(after using sort())
cout << "The vector after sort operation is:/n" ;
for (int i=0; i<n; i++)
{
// "first" and "second" are used to access
// 1st and 2nd element of pair respectively
cout << vect[i].first << " "
<< vect[i].second << endl;
}
getchar();
return 0;`enter code here`
}**

Answer 12

typedef std::vector<int> int_vec_t;
typedef std::vector<std::string> str_vec_t;
typedef std::vector<size_t> index_vec_t;
class SequenceGen {
public:
SequenceGen (int start = 0) : current(start) { }
int operator() () { return current++; }
private:
int current;
};
class Comp{
int_vec_t& _v;
public:
Comp(int_vec_t& v) : _v(v) {}
bool operator()(size_t i, size_t j){
return _v[i] < _v[j];
}
};
index_vec_t indices(3);
std::generate(indices.begin(), indices.end(), SequenceGen(0));
//indices are {0, 1, 2}
int_vec_t Index = { 3, 1, 2 };
str_vec_t Values = { "Third", "First", "Second" };
std::sort(indices.begin(), indices.end(), Comp(Index));
//now indices are {1,2,0}

Ahora puede usar el vector "índices" para indexar en el vector "Valores".