Hi,
Given a map:
typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that
has the long value of x?
At the moment I'm iterating through the map and keeping count of when I
hit it.
Thanks
Steve 13 4969
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
Check out the member functions of std::map, notably, find.
Your algorithm is O(n), the member function is probably O(log2 n).
Ben Pope

I'm not just a number. To many, I'm known as a string...
In article <44**********************@taz.nntpserver.com>,
Ben Pope <be***************@gmail.com> wrote: Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
Check out the member functions of std::map, notably, find.
Your algorithm is O(n), the member function is probably O(log2 n).
Ben Pope
Thanks, but that returns an iterator to the element. I'm not sure how
this helps me determine its index.
Steve
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x?
std::map<> is an associative container with elements sorted based on
some comparison operator. In other words, it doesnot really mean
anything to find "index" of an element in std::map<>  (You cannot
really insert an element in a map at a "given position", unlike say,
std::vector<>, where you can).
If by the word "index" you actually mean the "iterator" to the element,
then the member function find() will do the trick. This function takes
a key and returns the iterator to the element with that key (and the
iterator to end() otherwise if no such element exists)
Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope <be***************@gmail.com> wrote:
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it. Check out the member functions of std::map, notably, find.
Your algorithm is O(n), the member function is probably O(log2 n).
Ben Pope
Thanks, but that returns an iterator to the element. I'm not sure how this helps me determine its index.
#include <iostream>
#include <string>
#include <map>
int main()
{
std::map<int, std::string> m;
m[3] = "foo";
m[6] = "bar";
m[9] = "baz";
m[12] = "qux";
m[15] = "quux";
std::map<int, std::string>::iterator iter = m.find(3);
if(iter != m.end()) {
std::cout
<< "element with key: " << iter>first
<< " , value: " << iter>second
<< " , has index: " << std::distance(m.begin(), iter)
<< std::endl;
}
return 0;
}
Does that help?
Ben Pope

I'm not just a number. To many, I'm known as a string...
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
No. The problem is that <map> is designed so inserting an element is
fast. Yet
if you insert a new element at rank 1, all existing items have their
rank changed.
If this rank was stored, getting the rank would be fast but insertion
would be slow.
It's a design tradeoff, and std::map wasn't designed for it. You could
try a
vector<pair<long,string>, notstd::pair_greater_first> vmapOfFreq
HTH,
Michiel Salters
In article <gf***********************@news.btinternet.com>,
Steve Edwards <gf*@lineone.net> wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope <be***************@gmail.com> wrote:
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
Check out the member functions of std::map, notably, find.
Your algorithm is O(n), the member function is probably O(log2 n).
Ben Pope
Thanks, but that returns an iterator to the element. I'm not sure how this helps me determine its index.
Once you have the iterator, you can use std::distance.

Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
In article <44**********************@taz.nntpserver.com>,
Ben Pope <be***************@gmail.com> wrote: std::distance(m.begin(), iter)
Thanks, that's the function I couldn't figure out.
Steve
Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope <be***************@gmail.com> wrote:
std::distance(m.begin(), iter)
Thanks, that's the function I couldn't figure out.
Steve
Of course this call is still O(n)  as any solution must be. Something
tells me you should instead use a std::vector for your job and keep it
sorted. This assumes that the data in the map doesn't normally change,
but if it does your "rank" is not of much use anyway.
/Peter
In article <11**********************@t39g2000cwt.googlegroups .com>, Mi*************@tomtom.com wrote: Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
No. The problem is that <map> is designed so inserting an element is fast. Yet if you insert a new element at rank 1, all existing items have their rank changed. If this rank was stored, getting the rank would be fast but insertion would be slow.
It's a design tradeoff, and std::map wasn't designed for it. You could try a vector<pair<long,string>, notstd::pair_greater_first> vmapOfFreq
HTH, Michiel Salters
Thanks, I can see why rank is not stored. But I wondered if when you did
a retrievalbykey, the behindthescenes search algorithm would become
aware of the position within the sorted list, and hence be able to
provide the rank as a byproduct of the search.
In article <11*********************@v46g2000cwv.googlegroups. com>,
"Neelesh Bodas" <ne***********@gmail.com> wrote: Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x?
std::map<> is an associative container with elements sorted based on some comparison operator. In other words, it doesnot really mean anything to find "index" of an element in std::map<>  (You cannot really insert an element in a map at a "given position", unlike say, std::vector<>, where you can).
If by the word "index" you actually mean the "iterator" to the element, then the member function find() will do the trick. This function takes a key and returns the iterator to the element with that key (and the iterator to end() otherwise if no such element exists)
Thanks, I do take your point, but that's not to say that the rank isn't
a very useful bit of info. (sets that store scores often need to be
queried for rank i.e. "who came 7th?", "what rank is the one that scored
x?")
No problem, I can just iterate over them, or use
std::distance(m.begin(), iter) as Ben suggested.
Steve
In article <11**********************@e56g2000cwe.googlegroups .com>,
"peter koch" <pe***************@gmail.com> wrote: Steve Edwards wrote: In article <44**********************@taz.nntpserver.com>, Ben Pope <be***************@gmail.com> wrote:
std::distance(m.begin(), iter)
Thanks, that's the function I couldn't figure out.
Steve
Of course this call is still O(n)  as any solution must be. Something tells me you should instead use a std::vector for your job and keep it sorted. This assumes that the data in the map doesn't normally change, but if it does your "rank" is not of much use anyway.
/Peter
Yes, after reading the various posts I appreciate the problem now.
Searching by key is the most important job I have to do though, so I'll
just put up with having to determine rank manually.
Steve
Steve Edwards <gf*@lineone.net> wrote in
news:gf***********************@news.btinternet.com : In article <11**********************@t39g2000cwt.googlegroups .com>, Mi*************@tomtom.com wrote:
Thanks, I can see why rank is not stored. But I wondered if when you did a retrievalbykey, the behindthescenes search algorithm would become aware of the position within the sorted list, and hence be able to provide the rank as a byproduct of the search.
Nope. Nothing says that the map is stored in any sort of linear way. It's
far more likely that it's stored in some sort of tree data structure.
Steve Edwards wrote: Hi,
Given a map: typedef map<long, string, greater<long> > mapOfFreq;
Is there a quicker way to find the rank (i.e. index) of the elememt that has the long value of x? At the moment I'm iterating through the map and keeping count of when I hit it.
As others have pointed out, std::map<> does not support this. If performance
of this operation turns out to be critical, you can, however, design a
container very much like std::map<> based upon a balanced tree. In addition
to a key/value pair, every node would also keep a count of the size of the
subtree whose root the given node is. This way, you can obtain the position
of a node in the traversal order in log(N) time by adding some sizes along
a path. The costs for updating the size information is also logarithmic.
Thus, you can keep log(N) performance for insert/erase.
Best
KaiUwe Bux This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: john smith 
last post by:
Hi, I have a question about map and classes that contain maps. My problem
is declaring any class methods const that would do something to the map.
Presumably it's because when operator is...

by: Markus Hämmerli 
last post by:
I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two key.
Do you have a little example.
Thanks Markus

by: Florian Liefers 
last post by:
"Hello World\n",
i have the following problem:
One of my headerfiles for a lib is including <vector>.
When i compile the lib, everything is done well.
In my application another file is...

by: Carl Youngblood 
last post by:
I recognize that I may not be giving sufficient information with this,
but in the interest of not bogging the list down with too much code,
I'll try and post just a little information and then if...

by: Pierre Couderc 
last post by:
I am looking for a "special" kind of map :
 it is read like a map
 if the searched element exists, it is given back imediately
 if the searched element does not exist, an initialise() is...

by: laurence 
last post by:
I am implementing a comprehensive imagemap generator utility, so have been
studying W3C HTML 4.01 Specification
(http://www.w3.org/TR/html4/struct/objects.html#h13.6) on image maps (among
other...

by: Evgeny 
last post by:
Hi, all!
I didn't find yet solution for this problem! Somebody knows where is a
catch?
Looks like "operator =" or copy constructor not implemented in one of
internal templates....
Thanks in...

by: Steve Edwards 
last post by:
Hi,
After making an iterator to a map and stepping through a loop, I want to
delete any entries that satisfy a test from an external function.
MyMapType::const_iterator iter;
for(iter =...

by: Faith0G 
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

by: isladogs 
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...

by: taylorcarr 
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...

by: Charles Arthur 
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone

by: aa123db 
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...

by: ryjfgjl 
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and timeconsuming...

by: emmanuelkatto 
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel

by: Sonnysonu 
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by columnwise with in the specific length.
suppose the i have to...

by: Hystou 
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
 