stl map of vectors

Hello,

I have a map of stl vectors. Is there any easy was of iterating through the vectors.

typedef std::vector<string> RxSessionIds;
typedef std::map<std::string, RxSessionIds> PDN2RxSessionIdMap;


I have a value of Rx session Id..Want to know which PDN it belongs to

thanks a lot
~pdk

The map only maps one way, so you have to go over the mapped values (i.e., the vectors) and search each vector to find the given Rx session Id.

Thanks a lot laserlight. I tried the following..It compiles..Not tested yet (takes some time to do the live testing). But looks like this is the way to go , as you suggested

Code:

---

        string sPDN;

        // If there is a default bearer, then only send a request to PCRF.
        while (!bFound && iIter != CPCRF::m_mPDN2RxSessionIds.end())
        {
                std::vector<string> strvec = iIter->second;

                for(int i = 0; i < strvec.size(); i++)
                {
                        if (strvec[i] == sSessionId)
                        {
                          bFound=true;
                          sPDN = iIter->first;
                        }
                }
        }

---

Quote:

---

Originally Posted by pdk5

Hello,

I have a map of stl vectors. Is there any easy was of iterating through the vectors.

typedef std::vector<string> RxSessionIds;
typedef std::map<std::string, RxSessionIds> PDN2RxSessionIdMap;


I have a value of Rx session Id..Want to know which PDN it belongs to

thanks a lot
~pdk

---

As answered by laserlight, with what you currently have, you have no choice other than to simply iterate your map, and search each vector individually. Searching the vectors individually can be done with std::find. You *could* also search the map with std::find_if, but I think a simple for loop is better here. Either way, the operation is linear, so not optimal.

Whenever you find yourself creating a map/set of containers, always consider if the "multi" variant might not be a better fit. In this case, searching would be easier, as you would not need to have nested loops. But you'd still have bad performance.

If you find yourself doing this often, then consider a reverse map (or better yet, unordered_map) of RxSessionIds to their corresponding PDN2 strings.

Yet even better, you could use boosts' Bimap, though there's a learning curve on that.

Quote:

---

Originally Posted by monarch_dodra

You *could* also search the map with std::find_if, but I think a simple for loop is better here.

---

std::find would suffice, and I think that it would be appropriate:

Code:

---

const std::vector<string>& strvec = iIter->second;
if (std::find(strvec.begin(), strvec.end(), sSessionId) != strvec.end())
{
    bFound = true;
    sPDN = iIter->first;
}

---

After all, presently the for loop keeps looping even after a match is found.

Out of curiosity though, pdk5: are you compiling with respect to C++11 or later? Your code snippet is problematic in that you do not seem to have written the part that will declare and initialise iIter, and then you seem to have forgotten about incrementing iIter. With C++11, a range-based for loop might make life simpler.

EDIT:
Oh, I misread monarch_dodra's post by missing "Searching the vectors individually can be done with std::find."

Quote:

---

Originally Posted by pdk5

Thanks a lot laserlight. I tried the following..It compiles..Not tested yet (takes some time to do the live testing). But looks like this is the way to go , as you suggested

Code:

---

        string sPDN;

        // If there is a default bearer, then only send a request to PCRF.
        while (!bFound && iIter != CPCRF::m_mPDN2RxSessionIds.end())
        {
                std::vector<string> strvec = iIter->second;

                for(int i = 0; i < strvec.size(); i++)
                {
                        if (strvec[i] == sSessionId)
                        {
                          bFound=true;
                          sPDN = iIter->first;
                        }
                }
        }

---

---

You forgot to incrment your iterator I believe. Try this:

Code:

---

        string sPDN;
        // If there is a default bearer, then only send a request to PCRF.
        for (; iIter != CPCRF::m_mPDN2RxSessionIds.end(); ++iIter) {
                const std::vector<string>& strvec = iIter->second; // Notice the reference here! No need to copy.
                if (find(strvec.begin(), strvec.end(), sSessionId) != strvec.end()) {
                        sPDN = iIter->first;
                        break;
                }
        }

---

1. Almost always prefer a "for" loop over a "while": No matter what happens in your loop, a "for" will never forget to increment its counters.
2. Use std::algorithms. Not only is it less typing and less chance of error (ergo more robust), it also means less control structures, which later makes it easier to do things such a "break" or continue (less need of things such as "bFound").

@laserlight: Thanks a lot for the inputs. It is much appreciated.

I had written the initialiser for the iterator, but forgot to copy it.
std::map<std::string, RxSessionIds>::iterator iIter = CPCRF::m_mPDN2RxSessionIds.end();
Regarding the compiler, I tried to check my huge (blocks of cryptic makefiles), couldnot find the info..

@monarch : Thanks a lot for the comments. They are really helpful to improve my c++ and generic coding skills.

Regarding the code snippet there is minor compilation error:
if (find(strvec.begin(), strvec.second(), sSessionId) != strvec.end()) {
should have been
if (find(strvec.begin(), strvec.end(), sSessionId) != strvec.end()) {

For loops are preferred , but "breaks" are also not preferred much i guess. I might be wrong, not from computer programming background.

Quote:

---

Originally Posted by pdk5

For loops are preferred , but "breaks" are also not preferred much i guess.

---

It really depends. Just make sure your loops are not too convoluted. *Personally*, I hate having variables such as "done" or "found". It bloats the code with later tests. I think a good break, return or (sometimes) even goto can be more expressive, as it reduces the amount of later conditional tests. But to each their own. The real goal is to break down your code into simple blocks until there simply is no complexity left.

Don't let anyone (including me) tell you that something is "bad" or "good" without backing and explaining why, and make sure you build your own opinion.

That said, when in Rome, do as the Romans, and if you have a style guide that says "don't use breaks", then by all means, don't use break.

Thanks a lot monarch.

I think it was to avoid multiple exits from the function. I dont remember now the reasoning behind that.

yes in our current legacy code, i see mostly the while loops with the "bFound" logic being used. So i retained it. I think with your inputs i can now justify using the for loop. (and breaking the current conventions :) )

Quote:

---

Originally Posted by pdk5

But looks like this is the way to go

---

If you're using C++ 11 a much simpler and more efficient version could look like this,

Code:

---

    string sPDN = "";
//    bool bFound = false; // may not be needed, only the OP knows
    for (const auto& pair : CPCRF::m_mPDN2RxSessionIds) { // all pairs in map
        for (const auto& str : pair.second) { // all strings in vector
            if (str == sSessionId) {
                sPDN = pair.first; 
 //              bFound = true;
                goto out; // exit on first hit
            }
        }
    }
out:

---

Here nothing is copied from the map during search. Pairs, vectors and strings stay "in place".

Regarding the goto. This is a so called benign goto. Some languages even have built-in special syntax for it. Java for example calls it a labeled break.

---

I've corrected some errors in the code that a compiler would've caught. Also during editing I had a break in place of the goto which may have caused confusion. Sorry for that. Hope it's correct now.

Quote:

---

Originally Posted by tiliavirga

If you're using C++ 11 a much simpler and more efficient version could look like this,

---

You are using a C++11 range based for loop which is good, but for some reason, you decided to manually write a second (nested) loop instead of using simply using std::find.

While not a mistake in and out of itself, it does mean your loops are now nested, and, as mentioned, that "break; // exit on first hit" does not actually do that anymore. You'll only break out of the vector search loop, but not the map search :/

Quote:

---

Originally Posted by monarch_dodra

You are using a C++11 range based for loop which is good, but for some reason, you decided to manually write a second (nested) loop instead of using simply using std::find.

---

Aye, it looks like a strange decision to me, especially since it would eliminate the need for a goto to break out of the nested loops. Besides, I get the impression that bFound exists solely to control the loops, so it probably does not need to be maintained.

Prior to mentioning a range-based for loop in post #5, I confess that I wrote a code snippet to test so that I could be certain that it would really be simpler for pdk5. In the process I also made tiliavirga's mistake of treating the pair as an iterator rather than as a std::pair :) but it was not hard to fix it to:

Code:

---

string sPDN;
for (const auto& pair : CPCRF::m_mPDN2RxSessionIds)
{
    const auto& strvec = pair.second;
    if (std::find(strvec.begin(), strvec.end(), sSessionId) != strvec.end())
    {
        sPDN = pair.first;
        break;
    }
}

---

Anyway, pdk5: going back to the original problem, will you be doing this search over and over again? As monarch_dodra noted in post #4, it is not optimal.

Quote:

---

Originally Posted by monarch_dodra

You are using a C++11 range based for loop which is good, but for some reason, you decided to manually write a second (nested) loop instead of using simply using std::find.

While not a mistake in and out of itself, it does mean your loops are now nested, and, as mentioned, that "break; // exit on first hit" does not actually do that anymore. You'll only break out of the vector search loop, but not the map search :/

---

What's wrong with nested loops? If you have problems exiting from them you probably shouldn't be a programmer. :)

Quote:

---

Originally Posted by tiliavirga

What's wrong with nested loops?

---

In themselves, nothing, except that in this case the std::find generic algorithm expresses the intent more clearly with a name and removes the need to break out of nested loops with a goto as the simpler break would suffice.