벡터 중 하나만 사용하는 기준을 사용하여 동일한 방식으로 두 벡터를 정렬하려면 어떻게해야합니까?
벡터 중 하나만 사용하는 기준을 사용하여 동일한 방식으로 두 벡터를 정렬하려면 어떻게해야합니까?
예를 들어, 크기가 같은 두 개의 벡터가 있다고 가정합니다.
vector<MyObject> vectorA;
vector<int> vectorB;
그런 다음 vectorA비교 기능을 사용하여 정렬 합니다. 정렬 순서가 변경되었습니다 vectorA. 동일한 재정렬을 vectorB어떻게 적용 할 수 있습니까?
한 가지 옵션은 구조체를 만드는 것입니다.
struct ExampleStruct {
MyObject mo;
int i;
};
다음 정렬의 내용을 포함하는 벡터 vectorA와 vectorB하나의 벡터로 압축 업 :
// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;
이것은 이상적인 해결책이 아닌 것 같습니다. 특히 C ++ 11에 다른 옵션이 있습니까?
정렬 순열 찾기
std::vector<T>a와의 비교가 주어지면 T이 비교를 사용하여 벡터를 정렬하는 경우 사용할 순열을 찾을 수 있기를 원합니다.
template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
const std::vector<T>& vec,
Compare& compare)
{
std::vector<std::size_t> p(vec.size());
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
return p;
}
정렬 순열 적용
a std::vector<T>와 순열이 주어지면 순열 std::vector<T>에 따라 재정렬 되는 새로운 것을 만들 수 있기를 원합니다 .
template <typename T>
std::vector<T> apply_permutation(
const std::vector<T>& vec,
const std::vector<std::size_t>& p)
{
std::vector<T> sorted_vec(vec.size());
std::transform(p.begin(), p.end(), sorted_vec.begin(),
[&](std::size_t i){ return vec[i]; });
return sorted_vec;
}
물론 apply_permutation새로 정렬 된 복사본을 반환하는 대신 벡터를 변경 하도록 수정할 수 있습니다. 이 접근 방식은 여전히 선형 시간 복잡성이며 벡터의 항목 당 1 비트를 사용합니다. 이론적으로는 여전히 선형적인 공간 복잡성입니다. 그러나 실제로 sizeof(T)큰 경우 메모리 사용량이 크게 감소 할 수 있습니다. ( 자세히보기 )
template <typename T>
void apply_permutation_in_place(
std::vector<T>& vec,
const std::vector<std::size_t>& p)
{
std::vector<bool> done(vec.size());
for (std::size_t i = 0; i < vec.size(); ++i)
{
if (done[i])
{
continue;
}
done[i] = true;
std::size_t prev_j = i;
std::size_t j = p[i];
while (i != j)
{
std::swap(vec[prev_j], vec[j]);
done[j] = true;
prev_j = j;
j = p[j];
}
}
}
예
vector<MyObject> vectorA;
vector<int> vectorB;
auto p = sort_permutation(vectorA,
[](T const& a, T const& b){ /*some comparison*/ });
vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);
자원
제가 생각 해낸 확장 프로그램으로 기여하고 싶습니다. 목표는 간단한 구문을 사용하여 여러 벡터를 동시에 정렬 할 수있는 것입니다.
sortVectorsAscending(criteriaVec, vec1, vec2, ...)
알고리즘은 Timothy가 제안한 것과 동일하지만 가변 템플릿을 사용 하므로 임의 유형의 여러 벡터를 동시에 정렬 할 수 있습니다.
다음은 코드 조각입니다.
template <typename T, typename Compare>
void getSortPermutation(
std::vector<unsigned>& out,
const std::vector<T>& v,
Compare compare = std::less<T>())
{
out.resize(v.size());
std::iota(out.begin(), out.end(), 0);
std::sort(out.begin(), out.end(),
[&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}
template <typename T>
void applyPermutation(
const std::vector<unsigned>& order,
std::vector<T>& t)
{
assert(order.size() == t.size());
std::vector<T> st(t.size());
for(unsigned i=0; i<t.size(); i++)
{
st[i] = t[order[i]];
}
t = st;
}
template <typename T, typename... S>
void applyPermutation(
const std::vector<unsigned>& order,
std::vector<T>& t,
std::vector<S>&... s)
{
applyPermutation(order, t);
applyPermutation(order, s...);
}
template<typename T, typename Compare, typename... SS>
void sortVectors(
const std::vector<T>& t,
Compare comp,
std::vector<SS>&... ss)
{
std::vector<unsigned> order;
getSortPermutation(order, t, comp);
applyPermutation(order, ss...);
}
// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
const std::vector<T>& t,
std::vector<SS>&... ss)
{
sortVectors(t, std::less<T>(), ss...);
}
Ideone 에서 테스트하십시오 .
나는 이 블로그 포스트 에서 이것을 조금 더 잘 설명한다 .
순열을 사용한 내부 정렬
데이터가 너무 크고 정렬 된 벡터에 더 많은 메모리를 할당하고 싶지 않다면 제자리에서 수행해야하지만 Timothy와 같은 순열을 사용합니다 . 다음은 순열을 사용한 O (n) (선형 복잡성) 내부 정렬 의 예입니다 .
트릭은 순열과 역순 열을 가져와 마지막 정렬 단계에서 데이터를 덮어 쓸 위치를 아는 것입니다.
template <class K, class T>
void sortByKey(K * keys, T * data, size_t size){
std::vector<size_t> p(size,0);
std::vector<size_t> rp(size);
std::vector<bool> sorted(size, false);
size_t i = 0;
// Sort
std::iota(p.begin(), p.end(), 0);
std::sort(p.begin(), p.end(),
[&](size_t i, size_t j){ return keys[i] < keys[j]; });
// ----------- Apply permutation in-place ---------- //
// Get reverse permutation item>position
for (i = 0; i < size; ++i){
rp[p[i]] = i;
}
i = 0;
K savedKey;
T savedData;
while ( i < size){
size_t pos = i;
// Save This element;
if ( ! sorted[pos] ){
savedKey = keys[p[pos]];
savedData = data[p[pos]];
}
while ( ! sorted[pos] ){
// Hold item to be replaced
K heldKey = keys[pos];
T heldData = data[pos];
// Save where it should go
size_t heldPos = rp[pos];
// Replace
keys[pos] = savedKey;
data[pos] = savedData;
// Get last item to be the pivot
savedKey = heldKey;
savedData = heldData;
// Mark this item as sorted
sorted[pos] = true;
// Go to the held item proper location
pos = heldPos;
}
++i;
}
}
range-v3을 사용하면 간단하며 zip보기를 정렬 할 수 있습니다.
std::vector<MyObject> vectorA = /*..*/;
std::vector<int> vectorB = /*..*/;
ranges::v3::sort(ranges::view::zip(vectorA, vectorB));
또는 명시 적으로 투영을 사용합니다.
ranges::v3::sort(ranges::view::zip(vectorA, vectorB),
std::less<>{},
[](const auto& t) -> decltype(auto) { return std::get<0>(t); });
개별 벡터에서 쌍으로 구성된 벡터를 만듭니다.
쌍의 벡터 초기화 쌍의 벡터에
더하기사용자 정의 정렬 비교기 만들기 :
사용자 정의 개체의 벡터 정렬
http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B쌍으로 구성된 벡터를 정렬하십시오.
쌍으로 구성된 벡터를 개별 벡터로 분리하십시오.
이 모든 것을 함수에 넣으십시오.
암호:
std::vector<MyObject> vectorA;
std::vector<int> vectorB;
struct less_than_int
{
inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
{
return (a.second < b.second);
}
};
sortVecPair(vectorA, vectorB, less_than_int());
// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{
std::vector<pair<T,R>> vecC;
vecC.reserve(vecA.size());
for(int i=0; i<vecA.size(); i++)
{
vecC.push_back(std::make_pair(vecA[i],vecB[i]);
}
std::sort(vecC.begin(), vecC.end(), cmp);
vecA.clear();
vecB.clear();
vecA.reserve(vecC.size());
vecB.reserve(vecC.size());
for(int i=0; i<vecC.size(); i++)
{
vecA.push_back(vecC[i].first);
vecB.push_back(vecC[i].second);
}
}
vectorA와 vectorB의 길이가 같다고 가정합니다. 또 다른 벡터를 생성 할 수 있습니다. pos라고합시다. 여기서 :
pos[i] = the position of vectorA[i] after sorting phase
그런 다음 pos를 사용하여 vectorB를 정렬 할 수 있습니다. 즉, vectorBsorted를 만들 수 있습니다.
vectorBsorted[pos[i]] = vectorB[i]
그런 다음 vectorBsorted는 vectorA와 동일한 인덱스 순열로 정렬됩니다.
I am not sure if this works but i would use something like this. For example to sort two vectors i would use descending bubble sort method and vector pairs.
For descending bubble sort, i would create a function that requires a vector pair.
void bubbleSort(vector< pair<MyObject,int> >& a)
{
bool swapp = true;
while (swapp) {
int key;
MyObject temp_obj;
swapp = false;
for (size_t i = 0; i < a.size() - 1; i++) {
if (a[i].first < a[i + 1].first) {
temp_obj = a[i].first;
key = a[i].second;
a[i].first = a[i + 1].first;
a[i + 1].first = temp_obj;
a[i].second = a[i + 1].second;
a[i + 1].second = key;
swapp = true;
}
}
}
}
After that i would put your 2 vector values into one vector pair. If you are able to add values at the same time use this one and than call the bubble sort function.
vector< pair<MyObject,int> > my_vector;
my_vector.push_back( pair<MyObject,int> (object_value,int_value));
bubbleSort(my_vector);
If you want to use values after adding to your 2 vectors, you can use this one and than call the bubble sort function.
vector< pair<MyObject,int> > temp_vector;
for (size_t i = 0; i < vectorA.size(); i++) {
temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
}
bubbleSort(temp_vector);
I hope this helps. Regards, Caner
'Program Tip' 카테고리의 다른 글
| Node.js 용 유효성 검사 라이브러리 (0) | 2020.10.24 |
|---|---|
| Android : API 수준 VS. (0) | 2020.10.24 |
| WebView의 메모리 누수 (0) | 2020.10.24 |
| CSS에서 'property : 0'또는 'property : 0px'? (0) | 2020.10.24 |
| $ {}와 # {}의 차이점은 무엇입니까? (0) | 2020.10.24 |