地图排序有关问题

map排序问题
map<int,struct A>
map排序只能对key_type排序吗？如果对data_type排序是不是很麻烦？

  key_compare key_comp() const { return _M_t.key_comp(); }
  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  allocator_type get_allocator() const { return _M_t.get_allocator(); }

有点看不懂。。。
现在我对他排序就2中想法：1.map<struct A,int>换个位置排序（不想这么搞，总觉得不舒服）； 
                         2.把struct A装到vector里在排序；
大家有没有什么好的方法啊？
[最优解释]
stl map的数据结构本来就是已序的（按key）。
lz看下 红黑树 吧，map就是这个实现
[其他解释]

引用:

参考：
Map排序问题

里面有key和value排序的具体做法

这个连接里的map是哈希表，lz用的stl里的map是红黑树，两个数据结构不一样的。

除了C++，很多语言里的map都是指hash表。
[其他解释]
按值排，boost库有已经实现好的容器，可以参考之！
[其他解释]
楼主数据要是静态的话，可以考虑用索引排序加顺序容器。
[其他解释]
参考：
Map排序问题

里面有key和value排序的具体做法
[其他解释]
楼上给的链接有点看不懂。。。。
[其他解释]

引用:

楼上给的链接有点看不懂。。。。

Sorry，给的不是C++的代码。
[其他解释]
按你说的就没有必要用map了，根据需求找更合适的容器。
[其他解释]
怎么叫没必要啊。。那你说，要根据KEY排序，又要根据Struct A里面的信息排序，
还要通过KEY直找Struct A 你说该用什么容器啊
[其他解释]
  头文件里面有：
  key_compare key_comp() const { return _M_t.key_comp(); }
  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  太花眼睛了 。。。

我就想问问map里面有没有按value_type排序的方法，
如果没有的话那应该要借助其他的比如vector来排了。
[其他解释]

引用:

  头文件里面有：
  key_compare key_comp() const { return _M_t.key_comp(); }
  value_compare value_comp() const { return value_compare(_M_t.key_comp()); }
  太花眼睛了 。。。

我就想问问map里面有没有按value_type排序的方法，
如果……

没有
[其他解释]
这个value不是指值，而是整个元素，键值对。比的还是key。
vs的实现比较乱

typedef pair<const _Kty, _Ty> value_type;
...
class value_compare
: public binary_function<value_type, value_type, bool>
{// functor for comparing two element values
friend class _Tmap_traits<_Kty, _Ty, _Pr, _Alloc, _Mfl>;

public:
bool operator()(const value_type& _Left,
const value_type& _Right) const
{// test if _Left precedes _Right by comparing just keys 
 
return (comp(_Left.first, _Right.first));
}

value_compare(key_compare _Pred)
: comp(_Pred)
{// construct with specified predicate
}

protected:
key_compare comp;// the comparator predicate for keys
};

[其他解释]
红黑树没法按值排。
事实上，这个值只是红黑树里的卫星数据，并不是这个数据结构必须有的东西。
[其他解释]
所噶，那现在我就只有用vector装value_type（struct A）的结构体指针（还要根据排序，修改结构体），然后再排序了，还有没什么好点的方法啊？
[其他解释]
不明白你既要根据key，又要根据value排是什么意思。
比如
1 - a
2 - c
3 - b
4 - b

你要怎么排？是 1，2，3，4还是 a，b，b，c？

[其他解释]
举个例比如 10个球队    
球队代号key_type 1，2，3，4，5，6，7，8，9，10
value_type 就是对应的一些胜负场数，积分情况，排名情况。排名情况是根据积分来排序的，初始化为0，排序过后在添加进去。
要求按排名排列，或者积分高低排列，，，，等等  
 
[其他解释]
那key不就是用来查哪个球队的么？不用排序。
不过这样还是要两个容器，一个vector，一个hash_map（这个查找比map快，hash是 O(1)，map是 O(logN)）。
数据量小的话，直接在vector里遍历找key就是了，可以把键值队省了。遍历几千个元素也就一瞬间的事。
[其他解释]
比如要这样显示的话：
rank     id   score 。。。
1         5     32   。。。
2         2     25   。。。
3         8     16
4         14    9
5          9    6
6          1    3
。。。
。。。
rank是要经过比较score才能确定啊，直接找key的话  rank初始为0的。我直接说我的做法吧：

struct A{
     int score；
     int rank；
}；
map<int,struct A>  10个球队，score都确定了  54,25,22等等 但 rank全部还是0；
然后 vector<struct A*>   排序 然后通过struct A*  修改rank  然后再输出上面的格式。

[其他解释]
那就只能两个容器了。
或者就用一个vector，把球队好也放到struct A里。然后要按哪个排，就sort哪个。
用球队号查元素，先sort球队号，然后binary_search。如果要经常sort这个，sort那个，还是用两个容器方便。
[其他解释]
10楼正确：
typedef pair<const _Kty, _Ty> value_type;
...
class value_compare
        : public binary_function<value_type, value_type, bool>
        {    // functor for comparing two element values
        friend class _Tmap_traits<_Kty, _Ty, _Pr, _Alloc, _Mfl>;

    public:
        bool operator()(const value_type& _Left,
            const value_type& _Right) const
            {    // test if _Left precedes _Right by comparing just keys

            return (comp(_Left.first, _Right.first));
            }

        value_compare(key_compare _Pred)
            : comp(_Pred)
            {    // construct with specified predicate
            }

    protected:
        key_compare comp;    // the comparator predicate for keys
        };

[其他解释]
map就是按key排序的，不过存储形式是key-value的pair而已，实际比较的还是pair.first，即key的比较。

楼主可以让data_type当做key,key当做data，不就得了？
[其他解释]
动态的吧
[其他解释]
如果决定用map了，但是还需要按value排序，那八成是数据结构设计有问题，建议再review一下设计 。
[其他解释]
没这么排过 等待高人。。。
[其他解释]
建2个map
map<int,struct A>
map<struct A，int>
一个查，一个排序
不就行了
[其他解释]
这个，这个C++里面的map没实现compare()方法么？

记得map本来就是有序键值对嘛~~
[其他解释]
map按value排序的方法，给个例子吧：
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm> //使用STL的sort函数
using namespace  std;

typedef pair<string, double> MyPair;
//比较函数
bool compare(const MyPair& x, const MyPair& y)
{
return x.second > y.second;
}

int main()
{
map<string, double> myMap;
myMap.insert(pair<string, double>("238",0.2785)); 
myMap.insert(pair<string, double>("154",0.7461)); 
myMap.insert(pair<string, double>("192",0.2479)); 
myMap.insert(pair<string, double>("30",0.3902)); 
myMap.insert(pair<string, double>("232",0.2717)); 
myMap.insert(pair<string, double>("220",0.2803)); 

//逐个pair插入到vector
vector<MyPair> myVector;
for(map<string, double>::iterator mIter = myMap.begin(); mIter != myMap.end(); mIter++)
{
MyPair tmpPair(mIter->first, mIter->second);
myVector.push_back(tmpPair);
}
//STL的sort函数
sort(myVector.begin(), myVector.end(), compare);

//输出排序后的数据
for(vector<MyPair>::iterator vIter = myVector.begin(); vIter != myVector.end(); vIter++)
cout<<vIter->first<<"\t"<<vIter->second<<endl;
//输出nodes
return 0;
}

执行结果:
154     0.7461
30      0.3902
220     0.2803
238     0.2785
232     0.2717
192     0.2479
请按任意键继续. . .

查看更多 下一篇