std::map key values

Hi, I have a map object with a key of integers.
std::map<int, CJob> m_PendingJobs;

I need to generate new unique key values. I could just find the largest key with a reverse iterator and add one. A remote, but conceivable problem is that the key values keep growing until they are too large for int. Since I ecpect elements of the map to be removed at a pretty good rate, I decided to find the first available key value. Here is an idea of how to do this.

PHP Code:

---

    int NewKey = 0;
    BOOL FoundKey = FALSE;
    //the sequence of the map is ordered according to the key, integers, so last element has largest key value
    //Use a reverse iterator to retrieve this key value. Search for the first available key, if none found use last
    //key value plus one.  If map is empty use 0.
    if (!m_PendingJobs.empty())
    {
        std::map<int,CJob>::reverse_iterator rit = m_PendingJobs.rbegin();
        for (int i = 0; i < (*rit).first; i++)
        {
            if (m_PendingJobs.find(i) == m_PendingJobs.end())
            {
                 NewKey = i;
                 FoundKey = TRUE;
            }
        }
        if (!FoundKey)
            NewKey = (*rit).first + 1;
    } 


---

Anyone have any better ideas?

I am going to toss some more code here. This one takes
a char array of the form e.g. [1.2334;2233.33;2;4;5.788]
of arbitrary length and pulls the "numbers" out, converts
them to doubles and plops them in a vector.

I guess I don't feel all that confident with the STL
containers and so just want to know if I am doing these
things in a really inefficient way.

PHP Code:

---

    std::vector<double> ArrayData;
    double TempVal = 0.0;
    BOOL Done = FALSE;
    std::string::size_type Semi = 0;
    std::string::size_type NextSemi = 0;
    while(!Done)
    {
        NextSemi = TheArray.find(';', Semi + 1);
        if (std::string::npos == NextSemi)
            Done = TRUE;
        ArrayData.push_back(atof(TheArray.substr(Semi + 1,NextSemi - Semi + 1).c_str()));
        Semi = NextSemi;        
    } 


---

In the first example, are the keys always in a sequence, i.e. 0, 1, 2, 3, 4? If yes, one solution is to simply get the map size and use it as the next key.

Kuphryn

Well no, thats the problem. This map holds "jobs" which are created in response to clients. When the job is finished the job will be removed from the map, and so its key would be available for use. There could also be a quite large number of requests.

One solution is a sorted queue of keys. If the queue is empty, generate a new key. Otherwise, use the first key in the queue. Insert an unused key back in the queue as the program removes a job from the map.

Kuphryn

Now that is a good idea. Thanks. What about the second code chunk? I think it is ok

The solution in second example is efficient. Since data are stored in a string object, so find() and substr() work well.

Kuphryn

Thanks Kuphryn. I knew there had to be a better way for the keys. I have to say that the STL containers are just great:)

Definitely!

Kuphryn

Another possibility for the first question ...


What you are doing now is this :

Check if an element in the map has a key of 0 using find(). This
is an O(logn) operation. If found, you check for 1 (another O(logn)
operation), etc. . A more efficent way would be to just look
for the first "open" key value ...

Code:

---

    int NewKey = 0;

    if (!m_PendingJobs.empty())
    {
        std::map<int,CJob>::iterator it = m_PendingJobs.begin();
        while (it != m_PendingJobs.end() && (*it).first==NewKey)
        {
            ++NewKey;
            ++it;
        }
    }

---

As you mentioned, the possiblilty of the key value
getting to large is remote, so you might put a
check to see if the key to be added is greater than
the largest possible int (or some other pre-defined max)

Code:

---

    if (!m_PendingJobs.empty())
    {
        std::map<int,CJob>::reverse_iterator rit = m_PendingJobs.rbegin();
        int last_key = (*rit).first;
        if ( last_key < std::numeric_limits<int>::max() ) // include <limits>
        {
            NewKey = last_key + 1;
        }
        else
        {
            std::map<int,CJob>::iterator it = m_PendingJobs.begin();
            while (it != m_PendingJobs.end() && (*it).first==NewKey)
            {
                ++NewKey;
                ++it;
            }
        }
    }

---

Quote:

---

Originally posted by souldog
Well no, thats the problem. This map holds "jobs" which are created in response to clients. When the job is finished the job will be removed from the map, and so its key would be available for use. There could also be a quite large number of requests.

---

Philip,

The problem with just finding the first available key is that as soon as there are a lot of jobs (and they do not get deleted quickly), the process of finding an available key will be O(n).

What I would do is use a hash_map (non-standard extension of STL, but most STL implementations ship with one) and when a new job comes in, generate a random int. If that int is already used in the hash_map, then generate one again etc. If the number of active jobs is significantly (i.e. a few orders of magnitude) less than max(int) then this will be O(1) in practice.

Yves

Code:

---

#include <hash_map>

class job_holder
{
  std::hash_map<int, CJob>  m_jobs;
  // could be in stdext or some other namespace depending on your STL
public:
  int find_new_key();
};

int job_holder::find_new_key()
{
  int key;
  do {
    key = rand();
  } while (m_jobs.find(key) != m_jobs.end())
  return key;
}

---

Thanks for the replies. Let me post what I ended up doing based on Kuphryn's idea. The keys here are just integers. I store any available keys which are less than the largest key currently in use in a deque

std::deque<int> m_JobKeys;

When a job is completed, if it's key is not the largest one then I will add the key into the deque

PHP Code:

---

if (wParam != m_PendingJobs.size() - 1)
        m_JobKeys.push_back(wParam); 


---

here wParam is just the key.
To find a new Key I use

PHP Code:

---

int CUIUCNTCPinterfaceDlg::GetJobKey()
{
    int NewKey = 0;
    //the sequence of the map is ordered according to the key, integers, so last element has largest key value
    //Use a reverse iterator to retrieve this key value. Check the deque for any available keys, if none found use last
    //key value plus one.  If map is empty use 0.
    if (!m_PendingJobs.empty())
    {
        if (m_JobKeys.empty())
        {
            std::map<int,CJob>::reverse_iterator rit = m_PendingJobs.rbegin();
            NewKey = (*rit).first + 1;
        }
        else
        {
            NewKey = *(m_JobKeys.begin());
            m_JobKeys.pop_front();
        }
    }

    return NewKey;
} 


---

The time needed to do this should not depend on the number of pendings jobs (up to a couple of steps) and so is O(1)

But when do you insert new keys into m_JobKeys ? Actually you could do that when a job has finished, so its key will become available... True, this looks like a pretty good solution to me.

PHP Code:

---

if (wParam != m_PendingJobs.size() - 1)
        m_JobKeys.push_back(wParam); 


---

This is where keys are inserted when the job is completed. To keep the key deque from growing unnecessarily I don't insert the largest key of all pending jobs.

I should buy new glasses ;)