다른 std :: 벡터의 값으로 std :: 벡터를 어떻게 정렬합니까?
https://stackoverflow.com/questions/236172
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 몇 가지가있다 std::vector, 모두 같은 길이. 이 벡터 중 하나를 정렬하고 다른 모든 벡터에 동일한 변환을 적용하고 싶습니다. 깔끔한 방법이 있습니까? (바람직하게는 STL 또는 부스트 사용)? 벡터 중 일부는 고정됩니다 intS와 그들 중 일부 std::string에스.
의사 코드 :
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" };
해결책
Friol의 접근 방식은 당신과 결합 할 때 좋습니다. 먼저 숫자 1으로 구성된 벡터를 작성하십시오.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);
이제 사용자 정의 분류기를 사용 하여이 배열을 정렬 할 수 있습니다.
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());
이제 내부 재 배열 순서를 포착했습니다 order (보다 정확하게는 항목의 첫 번째 구성 요소에서). 이제이 순서를 사용하여 다른 벡터를 정렬 할 수 있습니다. 아마도 매우 영리한 내 위치 변형이 동시에 실행될 수 있지만 다른 사람이 그것을 내놓을 때까지, 여기에 내장이 아닌 하나의 변형이 있습니다. 사용합니다 order 각 요소의 새로운 인덱스에 대한 조회 테이블로.
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;
}
다른 팁
당신의 가치를 a에 넣으십시오 멀티 인덱스 컨테이너를 부스트하십시오 그런 다음 반복하여 원하는 순서로 값을 읽으십시오. 원한다면 다른 벡터에 복사 할 수도 있습니다.
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}
이제 "인덱스"벡터를 사용하여 "값"벡터로 색인 할 수 있습니다.
단 하나의 거친 솔루션만이 내 마음에 온다 : 다른 모든 벡터의 합인 벡터를 만듭니다 ({3, 셋째, ...}, {1, first, ...}와 같은 구조의 벡터)를 정렬하십시오. 첫 번째 필드에 의해 벡터를 벡터 한 다음 구조물을 다시 나눕니다.
아마도 Boost 나 표준 라이브러리를 사용하는 더 나은 솔루션이있을 것입니다.
여기에서 필요한 작업을 수행하는 사용자 정의 "Facade"Iterator를 정의 할 수 있습니다. 반복자를 모든 벡터에 저장하거나 첫 번째 오프셋에서 첫 번째 벡터를 제외한 모든 반복자를 대안으로 도출합니다. 까다로운 부분은 반복자가 다음과 같은 것입니다. 부스트 :: 튜플과 같은 것을 생각하고 부스트 :: tie를 영리하게 사용합니다. (이 아이디어를 확장하려면 템플릿을 사용 하여이 반복자 유형을 재귀 적으로 빌드 할 수 있지만 그 유형을 기록하고 싶지 않을 것입니다. 따라서 C ++ 0X Auto 또는 래퍼 기능이 필요합니다).
나는 당신이 무엇을 생각합니다 진짜 필요합니다 (그러나 내가 틀렸다면 정확 해)는 컨테이너의 요소에 어떤 순서로 액세스하는 방법입니다.
원래 컬렉션을 재정렬하지 않고 데이터베이스 디자인에서 개념을 빌려야합니다. 특정 기준에 따라 주문한 색인 유지. 이 지수는 유연성을 제공하는 추가 간접입니다.
이렇게하면 클래스의 다른 구성원에 따라 여러 지수를 생성 할 수 있습니다.
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 );
}
Ltjax의 답변은 큰 접근 방식입니다. 실제로 Boost의 Zip_iterator에서 구현됩니다. http://www.boost.org/doc/libs/1_43_0/libs/iterator/doc/zip_iterator.html
그것은 당신이 제공하는 반복자가 무엇이든 튜플로 함께 패키지합니다.
그런 다음 튜플의 반복자 값 조합을 기반으로 정렬에 대한 고유 한 비교 함수를 만들 수 있습니다. 이 질문에서는 튜플의 첫 번째 반복자 일뿐입니다.
이 접근법의 좋은 특징은 각 개별 벡터의 메모리를 연속적으로 유지할 수 있다는 것입니다 (벡터를 사용하는 경우 원하는 경우). 또한 INT의 별도 인덱스 벡터를 저장할 필요가 없습니다.
싱글을 기준으로 모든 벡터를 반복하려는 경우에 대한 XTOFL의 답변의 약간 더 컴팩트 한 변형 keys 벡터. 순열 벡터를 만들고 이것을 사용하여 다른 벡터로 인덱싱하십시오.
#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;
}
이것은 정렬 순서를 벡터에 적용하는 내 위치 변형에 대한 접근 방식으로 Konrad의 답변에 대한 부록이었을 것입니다. 어쨌든 편집이 통과하지 않기 때문에 여기에 넣을 것입니다.
다음은 부울 점검의 원시 작동으로 인한 약간 높은 시간 복잡성을 가진 내 위치 변형입니다. 추가 공간 복잡성은 공간 효율적인 컴파일러 종속 구현이 될 수있는 벡터입니다. 주어진 순서 자체를 수정할 수있는 경우 벡터의 복잡성을 제거 할 수 있습니다.
다음은 부울 점검의 원시 작동으로 인한 약간 높은 시간 복잡성을 가진 내 위치 변형입니다. 추가 공간 복잡성은 공간 효율적인 컴파일러 종속 구현이 될 수있는 벡터입니다. 주어진 순서 자체를 수정할 수있는 경우 벡터의 복잡성을 제거 할 수 있습니다. 이것은 알고리즘이 수행하는 일의 예입니다. 순서가 3 0 4 1 2 인 경우, 위치 지수로 표시된 요소의 이동은 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;
}
}
};
다음은 비교적 간단한 구현을 사용합니다 인덱스 매핑 순서대로 정렬되지 않은 것 사이 names 그것은 일치하는 데 사용됩니다 ages 주문에 names:
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);
}
완전성을 위해 다음은 기능이 있습니다. populate() 그리고 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";
}
}
}
그리고:
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";
}
}
그리고 마지막으로, main() :
#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...
**// 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`
}**
C ++ 11 Lambdas 및 Konrad Rudolph와 Gabriele D 'Antona의 답변을 기반으로 한 STL 알고리즘 :
template< typename T, typename U >
std::vector<T> sortVecAByVecB( std::vector<T> & a, std::vector<U> & b ){
// zip the two vectors (A,B)
std::vector<std::pair<T,U>> zipped(a.size());
for( size_t i = 0; i < a.size(); i++ ) zipped[i] = std::make_pair( a[i], b[i] );
// sort according to B
std::sort(zipped.begin(), zipped.end(), []( auto & lop, auto & rop ) { return lop.second < rop.second; });
// extract sorted A
std::vector<T> sorted;
std::transform(zipped.begin(), zipped.end(), std::back_inserter(sorted), []( auto & pair ){ return pair.first; });
return sorted;
}
많은 사람들 이이 질문을했고 아무도 만족스러운 대답을 내놓지 않았습니다. 다음은 하나의 벡터의 값을 고려하여 두 벡터를 동시에 정렬 할 수있는 STD :: 정렬 헬퍼입니다. 이 솔루션은 사용자 정의 Radomit (랜덤 반복자)을 기반으로하며 임시 사본, 구조 재 배열 또는 추가 지수없이 원래 벡터 데이터에서 직접 작동합니다.
