blocks|key|1214696|text|如果可能，您可以使用find函数构建位置数组，然后对该数组进行排序。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1214697|或者，您可以使用一个map，其中key是元素，值是元素在即将到来的数组(A、B和C)中的位置列表。|1214698|这取决于以后对这些数组的使用。|1214699|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

If it's possible, you can build the position array using find function, and then sort the array.

Or maybe you can use a map where the key would be the element, and the values a list of its position in the upcoming arrays (A, B and C)

It depends on later uses of those arrays.

blocks|key|1429599|text|向量中的项是唯一的吗？如果是这样的话，复制向量，用STL+Sort对其中一个副本进行排序，然后你就可以找到每个项目在原始向量中的索引。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1429600|如果向量应该处理重复项，我认为你最好实现你自己的排序例程。|1429601|entityMap|0|LINK|mutability|MUTABLE|url|http://www.sgi.com/tech/stl/sort.html^0|P|8|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

Are the items in the vector unique? If so, copy the vector, sort one of the copies with <a href="http://www.sgi.com/tech/stl/sort.html" rel="nofollow noreferrer">STL Sort</a> then you can find which index each item had in the original vector.

If the vector is supposed to handle duplicate items, I think youre better of implementing your own sort routine.

blocks|key|1214804|text|你可以对std::pair进行排序，而不仅仅是int+--第一个int是原始数据，第二个int是原始索引。然后提供一个只对第一个int进行排序的比较器。示例：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1214805|Your+problem+instance:+v+=+[5+7+8]
New+problem+instance:+v_prime+=+[<5,0>,+<8,1>,+<7,2>]|code-block|syntax|javascript|1214806|使用比较器对新问题实例进行排序，例如：|1214807|typedef+std::pair<int,int>+mypair;
bool+comparator+(+const+mypair&+l,+const+mypair&+r)
+++{+return+l.first+<+r.first;+}
//+forgetting+the+syntax+here+but+intent+is+clear+enough|1214808|使用该比较器对v_prime执行std::sort的结果应该是：|1214809|v_prime+=+[<5,0>,+<7,2>,+<8,1>]|1214810|您可以通过遍历向量，从每个std：：对中抓取.second来剥离索引。|1214811|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|W|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

You could sort std::pair instead of just ints - first int is original data, second int is original index. Then supply a comparator that only sorts on the first int. Example:

<pre><code>Your problem instance: v = [5 7 8]
New problem instance: v_prime = [&lt;5,0&gt;, &lt;8,1&gt;, &lt;7,2&gt;]
</code></pre>

Sort the new problem instance using a comparator like:

<pre><code>typedef std::pair&lt;int,int&gt; mypair;
bool comparator ( const mypair&amp; l, const mypair&amp; r)
 { return l.first &lt; r.first; }
// forgetting the syntax here but intent is clear enough
</code></pre>

The result of std::sort on v_prime, using that comparator, should be:

<pre><code>v_prime = [&lt;5,0&gt;, &lt;7,2&gt;, &lt;8,1&gt;]
</code></pre>

You can peel out the indices by walking the vector, grabbing .second from each std::pair.

blocks|key|1214858|text|我写了索引排序的泛型版本。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1214859|template+<class+RAIter,+class+Compare>
void+argsort(RAIter+iterBegin,+RAIter+iterEnd,+Compare+comp,+
++++std::vector<size_t>&+indexes)+{

++++std::vector<+std::pair<size_t,RAIter>+>+pv+;
++++pv.reserve(iterEnd+-+iterBegin)+;

++++RAIter+iter+;
++++size_t+k+;
++++for+(iter+=+iterBegin,+k+=+0+;+iter+!=+iterEnd+;+iter%2B%2B,+k%2B%2B)+{
++++++++pv.push_back(+std::pair<int,RAIter>(k,iter)+)+;
++++}

++++std::sort(pv.begin(),+pv.end(),+
++++++++[&comp](const+std::pair<size_t,RAIter>&+a,+const+std::pair<size_t,RAIter>&+b)+->+bool+
++++++++{+return+comp(*a.second,+*b.second)+;+})+;

++++indexes.resize(pv.size())+;
++++std::transform(pv.begin(),+pv.end(),+indexes.begin(),+
++++++++[](const+std::pair<size_t,RAIter>&+a)+->+size_t+{+return+a.first+;+})+;
}|code-block|syntax|javascript|1214860|使用方法与std::sort相同，只是使用索引容器接收排序后的索引。测试：|1214861|int+a[]+=+{+3,+1,+0,+4+}+;
std::vector<size_t>+indexes+;
argsort(a,+a+%2B+sizeof(a)+/+sizeof(a[0]),+std::less<int>(),+indexes)+;
for+(size_t+i+:+indexes)+printf("%25d\n",+int(i))+;|1214862|您应该得到2+1+0+3。对于没有c%2B%2B0x支持的编译器，将lamba表达式替换为类模板：|1214863|template+<class+RAIter,+class+Compare>+
class+PairComp+{
public:
++Compare+comp+;
++PairComp(Compare+comp_)+:+comp(comp_)+{}
++bool+operator()+(const+std::pair<size_t,RAIter>&+a,+
++++const+std::pair<size_t,RAIter>&+b)+const+{+return+comp(*a.second,+*b.second)+;+}++++++++
}+;|1214864|并将std::sort重写为|1214865|std::sort(pv.begin(),+pv.end(),+PairComp(comp)())+;|1214866|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

I wrote generic version of index sort.

<pre><code>template &lt;class RAIter, class Compare&gt;
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
 std::vector&lt;size_t&gt;&amp; indexes) {

 std::vector&lt; std::pair&lt;size_t,RAIter&gt; &gt; pv ;
 pv.reserve(iterEnd - iterBegin) ;

 RAIter iter ;
 size_t k ;
 for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
 pv.push_back( std::pair&lt;int,RAIter&gt;(k,iter) ) ;
 }

 std::sort(pv.begin(), pv.end(), 
 [&amp;comp](const std::pair&lt;size_t,RAIter&gt;&amp; a, const std::pair&lt;size_t,RAIter&gt;&amp; b) -&gt; bool 
 { return comp(*a.second, *b.second) ; }) ;

 indexes.resize(pv.size()) ;
 std::transform(pv.begin(), pv.end(), indexes.begin(), 
 [](const std::pair&lt;size_t,RAIter&gt;&amp; a) -&gt; size_t { return a.first ; }) ;
}
</code></pre>

Usage is the same as that of std::sort except for an index container to receive sorted indexes.
testing:

<pre><code>int a[] = { 3, 1, 0, 4 } ;
std::vector&lt;size_t&gt; indexes ;
argsort(a, a + sizeof(a) / sizeof(a[0]), std::less&lt;int&gt;(), indexes) ;
for (size_t i : indexes) printf("%d\n", int(i)) ;
</code></pre>

you should get 2 1 0 3.
for the compilers without c++0x support, replace the lamba expression as a class template:

<pre><code>template &lt;class RAIter, class Compare&gt; 
class PairComp {
public:
 Compare comp ;
 PairComp(Compare comp_) : comp(comp_) {}
 bool operator() (const std::pair&lt;size_t,RAIter&gt;&amp; a, 
 const std::pair&lt;size_t,RAIter&gt;&amp; b) const { return comp(*a.second, *b.second) ; } 
} ;
</code></pre>

and rewrite std::sort as

<pre><code>std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;
</code></pre>

blocks|key|1429797|text|使用C%2B%2B+11+lambdas：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1429798|#include+<iostream>
#include+<vector>
#include+<numeric>++++++//+std::iota
#include+<algorithm>++++//+std::sort,+std::stable_sort

using+namespace+std;

template+<typename+T>
vector<size_t>+sort_indexes(const+vector<T>+&v)+{

++//+initialize+original+index+locations
++vector<size_t>+idx(v.size());
++iota(idx.begin(),+idx.end(),+0);

++//+sort+indexes+based+on+comparing+values+in+v
++//+using+std::stable_sort+instead+of+std::sort
++//+to+avoid+unnecessary+index+re-orderings
++//+when+v+contains+elements+of+equal+values+
++stable_sort(idx.begin(),+idx.end(),
+++++++[&v](size_t+i1,+size_t+i2)+{return+v[i1]+<+v[i2];});

++return+idx;
}|code-block|syntax|javascript|1429799|现在，您可以在迭代中使用返回的索引向量，例如|1429800|for+(auto+i:+sort_indexes(v))+{
++cout+<<+v[i]+<<+endl;
}|1429801|您还可以选择提供原始索引向量、排序函数、比较器，或者使用额外的向量在sort_indexes函数中自动重新排序v。|1429802|entityMap^0|2|3|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|W|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|X|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|Y|8|@]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|D|@]|E|$]]]|R|$]]

Using <code>C++</code> 11 lambdas:

<pre><code>#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;numeric&gt; // std::iota
#include &lt;algorithm&gt; // std::sort, std::stable_sort

using namespace std;

template &lt;typename T&gt;
vector&lt;size_t&gt; sort_indexes(const vector&lt;T&gt; &amp;v) {

 // initialize original index locations
 vector&lt;size_t&gt; idx(v.size());
 iota(idx.begin(), idx.end(), 0);

 // sort indexes based on comparing values in v
 // using std::stable_sort instead of std::sort
 // to avoid unnecessary index re-orderings
 // when v contains elements of equal values 
 stable_sort(idx.begin(), idx.end(),
 [&amp;v](size_t i1, size_t i2) {return v[i1] &lt; v[i2];});

 return idx;
}
</code></pre>

Now you can use the returned index vector in iterations such as

<pre><code>for (auto i: sort_indexes(v)) {
 cout &lt;&lt; v[i] &lt;&lt; endl;
}
</code></pre>

You can also choose to supply your original index vector, sort function, comparator, or automatically reorder v in the sort_indexes function using an extra vector.

blocks|key|1429856|text|我遇到了这个问题，并认为直接对迭代器进行排序是一种对值进行排序和跟踪索引的方法；不需要定义额外的(pair，index+)容器，这在值是大对象时很有帮助；迭代器提供对值和索引的访问：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1429857|/*
+*+a+function+object+that+allows+to+compare
+*+the+iterators+by+the+value+they+point+to
+*/
template+<+class+RAIter,+class+Compare+>
class+IterSortComp
{
++++public:
++++++++IterSortComp+(+Compare+comp+):+m_comp+(+comp+)+{+}
++++++++inline+bool+operator(+)+(+const+RAIter+&+i,+const+RAIter+&+j+)+const
++++++++{
++++++++++++return+m_comp+(+*+i,+*+j+);
++++++++}
++++private:
++++++++const+Compare+m_comp;
};

template+<class+INIter,+class+RAIter,+class+Compare>
void+itersort+(+INIter+first,+INIter+last,+std::vector+<+RAIter+>+&+idx,+Compare+comp+)
{+
++++idx.resize+(+std::distance+(+first,+last+)+);
++++for+(+typename+std::vector+<+RAIter+>::iterator+j+=+idx.begin(+);+first+!=+last;+%2B%2B+j,+%2B%2B+first+)
++++++++*+j+=+first;

++++std::sort+(+idx.begin(+),+idx.end(+),+IterSortComp<+RAIter,+Compare+>+(+comp+)+);
}|code-block|syntax|javascript|1429858|至于使用示例：|1429859|std::vector+<+int+>+A+(+n+);

//+populate+A+with+some+random+values
std::generate+(+A.begin(+),+A.end(+),+rand+);

std::vector+<+std::vector+<+int+>::const_iterator+>+idx;
itersort+(+A.begin(+),+A.end(+),+idx,+std::less+<+int+>+(+)+);|1429860|现在，例如，排序向量中第五个最小的元素将具有值**idx[+5+]，并且其在原始向量中的索引将是distance(+A.begin(+),+*idx[+5+]+)或简称为*idx[+5+]+-+A.begin(+)。|1429861|entityMap^0|1D|4|0|0|0|0|N|A|1C|X|2D|M|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|V|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|W|8|@]|D|@]|E|$]]|$1|M|3|N|5|H|7|X|8|@]|D|@]|E|$I|J]]|$1|O|3|P|5|6|7|Y|8|@$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]]|D|@]|E|$]]|$1|Q|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|R|$]]

I came across this question, and figured out sorting the iterators directly would be a way to sort the values and keep track of indices; There is no need to define an extra container of <code>pair</code>s of ( value, index ) which is helpful when the values are large objects; The iterators provides the access to both the value and the index:

<pre><code>/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template &lt; class RAIter, class Compare &gt;
class IterSortComp
{
 public:
 IterSortComp ( Compare comp ): m_comp ( comp ) { }
 inline bool operator( ) ( const RAIter &amp; i, const RAIter &amp; j ) const
 {
 return m_comp ( * i, * j );
 }
 private:
 const Compare m_comp;
};

template &lt;class INIter, class RAIter, class Compare&gt;
void itersort ( INIter first, INIter last, std::vector &lt; RAIter &gt; &amp; idx, Compare comp )
{ 
 idx.resize ( std::distance ( first, last ) );
 for ( typename std::vector &lt; RAIter &gt;::iterator j = idx.begin( ); first != last; ++ j, ++ first )
 * j = first;

 std::sort ( idx.begin( ), idx.end( ), IterSortComp&lt; RAIter, Compare &gt; ( comp ) );
}
</code></pre>

as for the usage example:

<pre><code>std::vector &lt; int &gt; A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector &lt; std::vector &lt; int &gt;::const_iterator &gt; idx;
itersort ( A.begin( ), A.end( ), idx, std::less &lt; int &gt; ( ) );
</code></pre>

now, for example, the 5th smallest element in the sorted vector would have value <code>**idx[ 5 ]</code> and its index in the original vector would be <code>distance( A.begin( ), *idx[ 5 ] )</code> or simply <code>*idx[ 5 ] - A.begin( )</code>.

blocks|key|1215068|text|在函数中创建std::pair，然后对其进行排序：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1215069|通用版本：|1215070|template<+class+RandomAccessIterator,class+Compare+>
auto+sort2(RandomAccessIterator+begin,RandomAccessIterator+end,Compare+cmp)+->
+++std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
++++using+valueType=typename+std::iterator_traits<RandomAccessIterator>::value_type;
++++using+Pair=std::pair<std::uint32_t,RandomAccessIterator>;

++++std::vector<Pair>+index_pair;
++++index_pair.reserve(std::distance(begin,end));

++++for(uint32_t+idx=0;begin!=end;%2B%2Bbegin,%2B%2Bidx){
++++++++index_pair.push_back(Pair(idx,begin));
++++}

++++std::sort(+index_pair.begin(),index_pair.end(),[&](const+Pair&+lhs,const+Pair&+rhs){
++++++++++return+cmp(*lhs.second,*rhs.second);
++++});

++++return+index_pair;
}|code-block|syntax|javascript|1215071|ideone|1215072|entityMap|0|LINK|mutability|MUTABLE|url|https://ideone.com/zCLx2W^0|6|9|0|0|0|0|6|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Z|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|10|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|11|8|@]|D|@$9|12|A|13|1|14]]|E|$]]|$1|O|3|-4|5|6|7|15|8|@]|D|@]|E|$]]]|P|$Q|$5|R|S|T|E|$U|V]]]]

Make a <code>std::pair</code> in function then sort pair : 

generic version : 

<pre><code>template&lt; class RandomAccessIterator,class Compare &gt;
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) -&gt;
 std::vector&lt;std::pair&lt;std::uint32_t,RandomAccessIterator&gt;&gt;
{
 using valueType=typename std::iterator_traits&lt;RandomAccessIterator&gt;::value_type;
 using Pair=std::pair&lt;std::uint32_t,RandomAccessIterator&gt;;

 std::vector&lt;Pair&gt; index_pair;
 index_pair.reserve(std::distance(begin,end));

 for(uint32_t idx=0;begin!=end;++begin,++idx){
 index_pair.push_back(Pair(idx,begin));
 }

 std::sort( index_pair.begin(),index_pair.end(),[&amp;](const Pair&amp; lhs,const Pair&amp; rhs){
 return cmp(*lhs.second,*rhs.second);
 });

 return index_pair;
}
</code></pre>

<a href="https://ideone.com/zCLx2W" rel="nofollow">ideone</a>

blocks|key|1429930|text|有另一种方法可以解决这个问题，使用地图：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1429931|vector<double>+v+=+{...};+//+input+data
map<double,+unsigned>+m;+//+mapping+from+value+to+its+index
for+(auto+it+=+v.begin();+it+!=+v.end();+%2B%2Bit)
++++m[*it]+=+it+-+v.begin();|code-block|syntax|javascript|1429932|不过，这将消除不唯一的元素。如果这是不可接受的，请使用multimap：|1429933|vector<double>+v+=+{...};+//+input+data
multimap<double,+unsigned>+m;+//+mapping+from+value+to+its+index
for+(auto+it+=+v.begin();+it+!=+v.end();+%2B%2Bit)
++++m.insert(make_pair(*it,+it+-+v.begin()));|1429934|为了输出索引，遍历map或multimap：|1429935|for+(auto+it+=+m.begin();+it+!=+m.end();+%2B%2Bit)
++++cout+<<+it->second+<<+endl;|1429936|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

There is another way to solve this, using a map:

<pre><code>vector&lt;double&gt; v = {...}; // input data
map&lt;double, unsigned&gt; m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
 m[*it] = it - v.begin();
</code></pre>

This will eradicate non-unique elements though. If that's not acceptable, use a multimap:

<pre><code>vector&lt;double&gt; v = {...}; // input data
multimap&lt;double, unsigned&gt; m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
 m.insert(make_pair(*it, it - v.begin()));
</code></pre>

In order to output the indices, iterate over the map or multimap:

<pre><code>for (auto it = m.begin(); it != m.end(); ++it)
 cout &lt;&lt; it-&gt;second &lt;&lt; endl;
</code></pre>

blocks|key|1215170|text|好吧，我的解决方案是使用残差技术。我们可以将排序的值放在较高的2个字节中，并将元素的索引放在较低的2个字节中：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1215171|int+myints[]+=+{32,71,12,45,26,80,53,33};

for+(int+i+=+0;+i+<+8;+i%2B%2B)
+++myints[i]+=+myints[i]*(1+<<+16)+%2B+i;|code-block|syntax|javascript|1215172|然后像往常一样对数组myints进行排序：|offset|length|style|CODE|1215173|std::vector<int>+myvector(myints,+myints%2B8);
sort(myvector.begin(),+myvector.begin()%2B8,+std::less<int>());|1215174|之后，您可以通过residuum访问元素的索引。下面的代码打印按升序排序的值的索引：|1215175|for+(std::vector<int>::iterator+it+=+myvector.begin();+it+!=+myvector.end();+%2B%2Bit)
+++std::cout+<<+'+'+<<+(*it)%25(1+<<+16);|1215176|当然，这种技术只适用于原始数组myints中相对较小的值(即那些可以放入int的高2个字节的值)。但它还有一个好处，那就是区分相同的myints值:它们的索引将按正确的顺序打印。|1215177|entityMap^0|0|0|A|6|0|0|0|0|F|6|10|3|1U|6|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Y|8|@$I|Z|J|10|K|L]]|9|@]|A|$]]|$1|M|3|N|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|13|8|@]|9|@]|A|$E|F]]|$1|S|3|T|5|6|7|14|8|@$I|15|J|16|K|L]|$I|17|J|18|K|L]|$I|19|J|1A|K|L]]|9|@]|A|$]]|$1|U|3|-4|5|6|7|1B|8|@]|9|@]|A|$]]]|V|$]]

Well, my solution uses residue technique. We can place the values under sorting in the upper 2 bytes and the indices of the elements - in the lower 2 bytes:

<pre><code>int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i &lt; 8; i++)
 myints[i] = myints[i]*(1 &lt;&lt; 16) + i;
</code></pre>

Then sort the array <code>myints</code> as usual:

<pre><code>std::vector&lt;int&gt; myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less&lt;int&gt;());
</code></pre>

After that you can access the elements' indices via residuum. The following code prints the indices of the values sorted in the ascending order:

<pre><code>for (std::vector&lt;int&gt;::iterator it = myvector.begin(); it != myvector.end(); ++it)
 std::cout &lt;&lt; ' ' &lt;&lt; (*it)%(1 &lt;&lt; 16);
</code></pre>

Of course, this technique works only for the relatively small values in the original array <code>myints</code> (i.e. those which can fit into upper 2 bytes of <code>int</code>). But it has additional benefit of distinguishing identical values of <code>myints</code>: their indices will be printed in the right order.

blocks|key|1215225|text|对于这种类型的问题，将原始数组数据存储到新数据中，然后将排序的数组的第一个元素二进制搜索到复制的数组中，该索引应该存储到向量或数组中。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1215226|input+array=>a
duplicate+array=>b
vector=>c(Stores+the+indices(position)+of+the+orignal+array
Syntax:
for(i=0;i<n;i%2B%2B)
c.push_back(binarysearch(b,n,a[i]));`|code-block|syntax|javascript|1215227|这里，binarysearch是一个函数，它接受数组、数组大小、搜索项，并返回搜索项的位置|1215228|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

For this type of question
Store the orignal array data into a new data and then binary search the first element of the sorted array into the duplicated array and that indice should be stored into a vector or array.

<pre><code>input array=&gt;a
duplicate array=&gt;b
vector=&gt;c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i&lt;n;i++)
c.push_back(binarysearch(b,n,a[i]));`
</code></pre>

Here binarysearch is a function which takes the array,size of array,searching item and would return the position of the searched item

blocks|key|1430128|text|假设给定的向量是|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1430129|A=[2,4,3]|code-block|syntax|javascript|1430130|创建一个新矢量|1430131|V=[0,1,2]+//+indicating+positions|1430132|排序V和排序时，不比较V的元素，而是比较A的相应元素|1430133|+//Assume+A+is+a+given+vector+with+N+elements
+vector<int>+V(N);
+std::iota(V.begin(),V.end(),0);+//Initializing
+sort(+V.begin(),V.end(),+[&](int+i,int+j){return+A[i]<A[j];}+);|1430134|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Suppose Given vector is
<pre><code>A=[2,4,3]
</code></pre>
Create a new vector
<pre><code>V=[0,1,2] // indicating positions
</code></pre>
Sort V and while sorting instead of comparing elements of V , compare corresponding elements of A
<pre><code> //Assume A is a given vector with N elements
 vector&lt;int&gt; V(N);
 std::iota(V.begin(),V.end(),0); //Initializing
 sort( V.begin(),V.end(), [&amp;](int i,int j){return A[i]&lt;A[j];} );
</code></pre>

blocks|key|1430172|text|vector<pair<int,int>+>a;

for+(i+=+0+;i+<+n+;+i%2B%2B)+{
++++//+filling+the+original+array
++++cin+>>+k;
++++a.push_back+(make_pair+(k,i));+//+k+=+value,+i+=+original+index
}

sort+(a.begin(),a.end());

for+(i+=+0+;+i+<+n+;+i%2B%2B){
++++cout+<<+a[i].first+<<+"+"+<<+a[i].second+<<+"\n";
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1430173|现在，a既包含了我们的值，也包含了它们各自的排序索引。|unstyled|offset|length|style|CODE|1430174|i'th的a[i].first+=+value|1430175|初始数组中的a[i].second+=+idx。|1430176|entityMap^0|0|3|1|0|0|1|5|I|0|6|H|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|R|8|@$G|S|H|T|I|J]]|9|@]|A|$]]|$1|K|3|L|5|F|7|U|8|@$G|V|H|W|I|J]|$G|X|H|Y|I|J]]|9|@]|A|$]]|$1|M|3|N|5|F|7|Z|8|@$G|10|H|11|I|J]]|9|@]|A|$]]|$1|O|3|-4|5|F|7|12|8|@]|9|@]|A|$]]]|P|$]]

<pre><code>vector&lt;pair&lt;int,int&gt; &gt;a;

for (i = 0 ;i &lt; n ; i++) {
 // filling the original array
 cin &gt;&gt; k;
 a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i &lt; n ; i++){
 cout &lt;&lt; a[i].first &lt;&lt; " " &lt;&lt; a[i].second &lt;&lt; "\n";
}
</code></pre>

Now <code>a</code> contains both both our values and their respective indices in the sorted.

<code>a[i].first = value</code> at <code>i</code>'th.

<code>a[i].second = idx</code> in initial array.

blocks|key|1430215|text|@Lukasz+Wiklendt提供了漂亮的解决方案！虽然在我的例子中我需要一些更通用的东西，所以我对它做了一些修改：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1430216|template+<class+RAIter,+class+Compare>
vector<size_t>+argSort(RAIter+first,+RAIter+last,+Compare+comp)+{

++vector<size_t>+idx(last-first);
++iota(idx.begin(),+idx.end(),+0);

++auto+idxComp+=+[&first,comp](size_t+i1,+size_t+i2)+{
++++++return+comp(first[i1],+first[i2]);
++};

++sort(idx.begin(),+idx.end(),+idxComp);

++return+idx;
}|code-block|syntax|javascript|1430217|示例:+Find索引按长度对字符串的向量进行排序，第一个元素除外，它是一个虚拟元素。|1430218|vector<string>+test+=+{"dummy",+"a",+"abc",+"ab"};

auto+comp+=+[](const+string+&a,+const+string&+b)+{
++++return+a.length()+>+b.length();
};

const+auto&+beginIt+=+test.begin()+%2B+1;
vector<size_t>+ind+=+argSort(beginIt,+test.end(),+comp);

for(auto+i+:+ind)
++++cout+<<+beginIt[i]+<<+endl;|1430219|打印：|1430220|abc
ab
a|1430221|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|S|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|U|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

Beautiful solution by @Lukasz Wiklendt! Although in my case I needed something more generic so I modified it a bit:

<pre><code>template &lt;class RAIter, class Compare&gt;
vector&lt;size_t&gt; argSort(RAIter first, RAIter last, Compare comp) {

 vector&lt;size_t&gt; idx(last-first);
 iota(idx.begin(), idx.end(), 0);

 auto idxComp = [&amp;first,comp](size_t i1, size_t i2) {
 return comp(first[i1], first[i2]);
 };

 sort(idx.begin(), idx.end(), idxComp);

 return idx;
}
</code></pre>

Example: Find indices sorting a vector of strings by length, except for the first element which is a dummy.

<pre><code>vector&lt;string&gt; test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &amp;a, const string&amp; b) {
 return a.length() &gt; b.length();
};

const auto&amp; beginIt = test.begin() + 1;
vector&lt;size_t&gt; ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
 cout &lt;&lt; beginIt[i] &lt;&lt; endl;
</code></pre>

prints:

<pre><code>abc
ab
a
</code></pre>

blocks|key|1215425|text|一种解决方案是使用2D向量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1215426|#include+<algorithm>
#include+<iostream>
#include+<vector>
using+namespace+std;

int+main()+{
+vector<vector<double>>+val_and_id;
+val_and_id.resize(5);
+for+(int+i+=+0;+i+<+5;+i%2B%2B)+{
+++val_and_id[i].resize(2);+//+one+to+store+value,+the+other+for+index.
+}
+//+Store+value+in+dimension+1,+and+index+in+the+other:
+//+say+values+are+5,4,7,1,3.
+val_and_id[0][0]+=+5.0;
+val_and_id[1][0]+=+4.0;
+val_and_id[2][0]+=+7.0;
+val_and_id[3][0]+=+1.0;
+val_and_id[4][0]+=+3.0;

+val_and_id[0][1]+=+0.0;
+val_and_id[1][1]+=+1.0;
+val_and_id[2][1]+=+2.0;
+val_and_id[3][1]+=+3.0;
+val_and_id[4][1]+=+4.0;

+sort(val_and_id.begin(),+val_and_id.end());
+//+display+them:
+cout+<<+"Index+\t"+<<+"Value+\n";
+for+(int+i+=+0;+i+<+5;+i%2B%2B)+{
++cout+<<+val_and_id[i][1]+<<+"\t"+<<+val_and_id[i][0]+<<+"\n";
+}
+return+0;
}|code-block|syntax|javascript|1215427|下面是输出：|1215428|+++Index+++Value
+++3+++++++1
+++4+++++++3
+++1+++++++4
+++0+++++++5
+++2+++++++7|1215429|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

One solution is to use a 2D vector.
<pre><code>#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;
using namespace std;

int main() {
 vector&lt;vector&lt;double&gt;&gt; val_and_id;
 val_and_id.resize(5);
 for (int i = 0; i &lt; 5; i++) {
 val_and_id[i].resize(2); // one to store value, the other for index.
 }
 // Store value in dimension 1, and index in the other:
 // say values are 5,4,7,1,3.
 val_and_id[0][0] = 5.0;
 val_and_id[1][0] = 4.0;
 val_and_id[2][0] = 7.0;
 val_and_id[3][0] = 1.0;
 val_and_id[4][0] = 3.0;

 val_and_id[0][1] = 0.0;
 val_and_id[1][1] = 1.0;
 val_and_id[2][1] = 2.0;
 val_and_id[3][1] = 3.0;
 val_and_id[4][1] = 4.0;

 sort(val_and_id.begin(), val_and_id.end());
 // display them:
 cout &lt;&lt; &quot;Index \t&quot; &lt;&lt; &quot;Value \n&quot;;
 for (int i = 0; i &lt; 5; i++) {
 cout &lt;&lt; val_and_id[i][1] &lt;&lt; &quot;\t&quot; &lt;&lt; val_and_id[i][0] &lt;&lt; &quot;\n&quot;;
 }
 return 0;
}
</code></pre>
Here is the output:
<pre><code> Index Value
 3 1
 4 3
 1 4
 0 5
 2 7
</code></pre>

Using C++, and hopefully the standard library, I want to sort a sequence of samples in ascending order, but I also want to remember the original indexes of the new samples.
For example, I have a set, or vector, or matrix of samples <code>A : [5, 2, 1, 4, 3]</code>. I want to sort these to be <code>B : [1,2,3,4,5]</code>, but I also want to remember the original indexes of the values, so I can get another set which would be:
<code>C : [2, 1, 4, 3, 0 ]</code> - which corresponds to the index of each element in 'B', in the original 'A'.
For example, in Matlab you can do:
<pre><code> [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2
</code></pre>
Can anyone see a good way to do this?

C++ sorting and keeping track of indexes

数据存储

编译器

容器

使用C++ (希望还有标准库)，我希望按升序对一系列样本进行排序，但我还希望记住新样本的原始索引。例如，我有一个集合，或向量，或样本矩阵A : [5, 2, 1, 4, 3]。我想要将这些元素排序为B : [1,2,3,4,5]，但我也想记住这些值的原始索引，这样我就可以获得另一个集合：C : [2, 1, 4, 3,...

问C++对索引进行排序和跟踪
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++对索引进行排序和跟踪EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++对索引进行排序和跟踪
EN