已有帖子sorting vector of pointers,但这不是关于指针的向量,而是关于引用指针的向量。
将3个整数放入std::vector<int*>
中,然后根据指针后面的值进行排序。
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int a = 3;
int b = 2;
int c = 1;
std::vector<int*> vec;
vec.emplace_back(&a);
vec.emplace_back(&b);
vec.emplace_back(&c);
std::sort(vec.begin(), vec.end(), [](const int* a, const int* b) {
return *a < *b;
});
std::cout << "vec = " << *vec[0] << ", " << *vec[1] << ", " << *vec[2] << '\n';
std::cout << "abc = " << a << ", " << b << ", " << c << '\n';
}
但是,似乎只有矢量按输出显示排序:
vec = 1, 2, 3
abc = 3, 2, 1
我认为原因是std::sort()
在正确比较时,只是分配地址而不是值。这有什么不对?为什么我不能对这个指向值的向量进行排序?
下一部分是TL,DR,因为它显示了我解决这个问题的方法。一项简单的任务,显示出相当令人沮丧的复杂。 @Bathsheba's answer指出这是不可能的。所以下一部分,最初被认为是我的尝试的表现,现在可能被认为是不可能的原因。
我的想法是创建一个指针类包装器来提供我自己的构造函数和assignement操作符。如果容器的大小很小(std::sort()
在我的系统上),<= 32
表现不同,但在这两种情况下都有分配和移动 - 正如_Insertion_sort_unchecked
(来自<algorithm>
)函数的这个小片段所示。
(_BidIt
== std::vector<int*>::iterator
和_Iter_value_t<_BidIt>
== int*
)
_BidIt _Insertion_sort_unchecked(_BidIt _First, const _BidIt _Last, _Pr _Pred)
{ // insertion sort [_First, _Last), using _Pred
if (_First != _Last)
{
for (_BidIt _Next = _First; ++_Next != _Last; )
{ // order next element
_BidIt _Next1 = _Next;
_Iter_value_t<_BidIt> _Val = _STD move(*_Next);
if (_DEBUG_LT_PRED(_Pred, _Val, *_First))
{ // found new earliest element, move to front
_Move_backward_unchecked(_First, _Next, ++_Next1);
*_First = _STD move(_Val);
让我们创建一个类似于指针的类assignement_pointer
,除了它分配值而不是地址。
template<typename T>
class assignement_pointer {
public:
assignement_pointer(T& value) {
this->m_ptr = &value;
std::cout << "<T>& constructor\n";
}
assignement_pointer(const assignement_pointer& other) {
this->m_ptr = other.m_ptr;
std::cout << "copy constructor\n";
}
assignement_pointer(assignement_pointer&& other) {
std::cout << "move assignement constructor >> into >> ";
*this = std::move(other);
}
assignement_pointer& operator=(const assignement_pointer& other) {
*this->m_ptr = *other.m_ptr;
std::cout << "copy assignement operator\n";
return *this;
}
assignement_pointer& operator=(assignement_pointer&& other) {
std::swap(this->m_ptr, other.m_ptr);
std::cout << "move assignement operator\n";
return *this;
}
T& operator*() {
return *this->m_ptr;
}
const T& operator*() const {
return *this->m_ptr;
}
private:
T* m_ptr;
};
正如你所看到的那样,还有一些临时的std::cout
可以看到在主要通过std::sort()
时调用了哪些构造函数/分配操作符:
///...
std::vector<assignement_pointer<int>> vec;
vec.reserve(3);
vec.emplace_back(assignement_pointer(a));
vec.emplace_back(assignement_pointer(b));
vec.emplace_back(assignement_pointer(c));
std::cout << "\nsort()\n";
std::sort(vec.begin(), vec.end(), [](const assignement_pointer<int>& a, const assignement_pointer<int>& b) {
return *a < *b;
});
std::cout << "\nvec = " << *vec[0] << ", " << *vec[1] << ", " << *vec[2] << '\n';
std::cout << "abc = " << a << ", " << b << ", " << c << '\n';
给出输出:
<T>& constructor
move assignement constructor >> into >> move assignement operator
<T>& constructor
move assignement constructor >> into >> move assignement operator
<T>& constructor
move assignement constructor >> into >> move assignement operator
sort()
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
move assignement operator
vec = 1, 2, 3
abc = 3, 2, 1
std::sort()
只调用移动功能。vec
排序但不是a
,b
,c
最后一点是有道理的,因为只有移动函数被称为复制分配运算符assignement_pointer& operator=(const assignement_pointer& other);
(它具有值分配)从不被调用。可以删除不必要的复制构造函数和assignement运算符:
template<typename T>
class assignement_pointer {
public:
assignement_pointer(T& value) {
this->m_ptr = &value;
}
assignement_pointer(const assignement_pointer& other) = delete;
assignement_pointer& operator=(const assignement_pointer& other) = delete;
assignement_pointer(assignement_pointer&& other) {
std::cout << "move assignement constructor >> into >> ";
*this = std::move(other);
}
assignement_pointer& operator=(assignement_pointer&& other) {
std::swap(this->m_ptr, other.m_ptr);
std::cout << "move assignement operator\n";
return *this;
}
T& operator*() {
return *this->m_ptr;
}
const T& operator*() const {
return *this->m_ptr;
}
private:
T* m_ptr;
};
现在std::sort()
内部过程相当复杂,但最终归结为像std::swap()
这样的操作失败:
int main() {
int a = 3;
int b = 2;
std::vector<assignement_pointer<int>> vec;
vec.reserve(2); //to avoid re-allocations
vec.emplace_back(assignement_pointer(a));
vec.emplace_back(assignement_pointer(b));
std::cout << "swap()\n";
assignement_pointer<int> ptr_a{ a };
assignement_pointer<int> ptr_b{ b };
std::swap(ptr_a, ptr_b);
std::cout << "\nptrs = " << *ptr_a << ", " << *ptr_b << '\n';
std::cout << "a, b = " << a << ", " << b << '\n';
}
并且此输出显示:
move assignement constructor >> into >> move assignement operator
move assignement constructor >> into >> move assignement operator
swap()
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
ptrs = 2, 3
a, b = 3, 2
只有指针被切换而不是原始变量才是这样的。 std::swap
基本上是
_Ty _Tmp = _STD move(_Left);
_Left = _STD move(_Right);
_Right = _STD move(_Tmp);
解释
move assignement constructor >> into >> move assignement operator
move assignement operator
move assignement operator
移动赋值运算符只是交换指针,因此创建临时变量不会做任何事情。我看到两个可能的解决方案:
swap()
但两者都不起作用。
m_ptr
类的初始this->
总是nullptr
,我宁愿不解除这个。std::sort()
从不使用std::swap()
,而只是来自各地的std::move()
s。 (正如_Insertion_sort_unchecked
已经部分看到的那样)。您需要使用自己的排序功能来执行此操作。
回调lambda用于评估排序,但是你需要调整实际交换元素的部分:而C ++标准库sort
不支持你这样做。
幸运的是,快速排序没有任何花里胡哨(例如预先随机化)出现在几十行中,所以这不是一个特别繁重的任务。
只需保留原始指针向量的副本,并将排序后的值复制到:
std::vector<int*> original = vec; // Do this before the std::sort
然后打印a,b,c后:
std::vector<int> xfer;
for (auto ptr : vec) {
xfer.push_back(*ptr);
}
auto it = std::begin(xfer);
for (auto ptr : original) {
*ptr = *it++;
}
std::cout << "abc = " << a << ", " << b << ", " << c << '\n';
输出:
abc = 1, 2, 3