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.

Quote:

---

Originally Posted by tiliavirga

I personally prefer structure over logic and that's why the (benign) goto in my solution doesn't bother me at all.

---

I don't quite understand what you mean by "structure over logic" here though: isn't the structure entirely a logical structure?

One advantage of using the generic algorithm is that the abstraction provides the reader with immediate information, i.e., instead of parsing the loop to figure out what it does, the reader knows that the aim is to try and find something. The logical structure remains essentially the same, except that part of the details is hidden by an abstraction. In this particular case, an additional advantage is that now we only need to break from a non-nested loop, so the simple break does the job.

Quote:

---

Originally Posted by tiliavirga

And if break is so disgusting

---

You are mistaken: the break (whether the keyword or simulated with goto because C++'s break does not allow breaking from within an inner loop out of an outer loop) is not disgusting. Rather, it is appropriate to the logic here, and in fact I notice that it is you who wrote the appropriately used goto in the first place.

Quote:

---

Originally Posted by tiliavirga

why didn't you replace the outermost loop with a function too (say find_if).

---

I think that the range-based for loop would be sufficient. Using find_if would not necessarily improve the readability of the code because the predicate might not be simpler than the current loop body.

Instead, for abstraction, the entire code snippet could be moved to a separate function instead to abstract away the entire "want to know which PDN it belongs to" search logic.

Quote:

---

Originally Posted by tiliavirga

That would remove also the remaning break from your code.

---

Removing a break just for the sake of removing a break, without improving the readability of the code, is a misguided approach.

@laserlight: ok ..anyway i wont be doing this search over and over again ..i am trying to understand and digest all the very useful inputs given.

Quote:

---

Originally Posted by laserlight

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.

---

I personally prefer structure over logic and that's why the (benign) goto in my solution doesn't bother me at all. It rather makes the code clearer to me.

But if break is so disgusting why didn't you replace the outermost loop with a function too (say find_if)? That would remove also the remaning break from your code.

Furthermore the C++ range for-loops are stateless and count as functions in my book so I don't feel any particular urge to replace them with functions for functional paradigmic reasons.

Finally many problems (like this one) can easily be executed in parallel. Then it becomes limiting to implement them using inherently sequential functions from the standard library. A solution based on range for-loops is much more readily converted into parallel (using available concurrency librares).

Weird, did the posts go out of sync? I was fairly certain that I was replying to tiliavirga's post, but it looks like my post now appears before the post that I was responding to.

Quote:

---

Originally Posted by laserlight

Weird, did the posts go out of sync? I was fairly certain that I was replying to tiliavirga's post, but it looks like my post now appears before the post that I was responding to.

---

You must have replied to an earlier post I accidentally posted and then deleted. My reply to your post is #18. I'm not used to quick replies at this forum but I'll be more careful from now on.

Quote:

---

Originally Posted by tiliavirga

You must have replied to an earlier post I accidentally posted and then deleted. My reply to your post is #18.

---

No, my post #16 is a reply to your post #18. That is why I found it strange, but yeah, "posted then deleted" does explain it. Talk about concurrency :D

Anyway, to address your additional points:

Quote:

---

Originally Posted by tiliavirga

Furthermore the C++ range for-loops are stateless and count as functions in my book so I don't feel any particular urge to replace them with functions for functional paradigmic reasons.

---

That does not make sense to me: a range-based for loop is a loop statement, not a function. That said, I do like them precisely because I feel that they make things simpler these days such that there is less benefit in some previously useful application of generic algorithms. For example, previously if you want to say, print the elements of a vector (or more generally, a container that might not have random access by index, hence the use of iterators) to standard output, you have a choice between something pretty verbose like this:

Code:

---

for (std::vector<T>::iterator iter = some_vector.begin(); iter != some_vector.end(); ++iter)
{
    std::cout << *iter << " ";
}

---

and this:

Code:

---

std::copy(some_vector.begin(), some_vector.end(), std::ostream_iterator<T>(std::cout, " "));

---

whereas now this may span more lines than the generic algorithm version and lack the descriptive element of the name, but it is arguably easier to read and understand (no need to figure out the ostream_iterator) so the lack of the algorithm name is no loss:

Code:

---

for (const auto& item : some_vector)
{
    std::cout << item << " ";
}

---

Quote:

---

Originally Posted by tiliavirga

Finally many problems (like this one) can easily be executed in parallel. Then it becomes limiting to implement them using inherently sequential functions from the standard library. A solution based on range for-loops is much more readily converted into parallel (using available concurrency librares).

---

Good point, but it seems to me that it would be useful to have a library of generic algorithms that can cater to this.

Quote:

---

Originally Posted by laserlight

Removing a break just for the sake of removing a break, without improving the readability of the code, is a misguided approach.

---

We are not talking about incomprehensible pieces of junk here but the same algorithm implemented slighly differently using standard C++ 11 features. All three versions have the same complexity and are equally efficient.

1. Two nested range-based for-loops with a terminating goto upon search hit.

2. As 1 but the innermost loop is replaced by std::find. The goto is replaced by a break.

3. As 2 but the outermost loop is replaced by std::find_if and the inner std::find is supplied by lambda. There is no break.

My personal favourite is #1. It is the most readable to me because this is how a two-dimensional search has been implemented since the dawn of programming. The range-based for-loop is core C++ and exceptionally terse and simple and even "functional" since it's stateless (no loop variable). Any programmer should grasp it with just a quick glance. In addition range-based for-loops are easily replaced by parallel equivalents from some existing concurrency library.

My personal runner up is #3. It's functional in the sense that all looping has been replaced by C++ standard functions. The downside is that sequentiality is permanent and to make it parallel the code has to be rewritten. On the upside there is no jumping (no goto no break). It's very readable to people like me who like the functional approach using lots of functions and lambdas.

My beef with #2 is that it's neither nor. It combines the drawbacks of #1 and #3 without achieving any of their benefits. You claim it's the most "readable" version but that's your personal view and even though your likings and dislikings may be important to you and your fan club it's not an argument in itself. So why is #2 more readable apart from that's what you think?

Quote:

---

Originally Posted by tiliavirga

It's very readable to people who like the functional approach using lots of functions and lambdas.

---

That's a good point: part of readability depends on the reader's familiarity with the paradigms in use. Yet, C++ is multiparadigm, so I do not see a problem with mixing and matching, hence I disagree with your criticism of #2 as being "neither nor" as a drawback.

Quote:

---

Originally Posted by tiliavirga

It combines the drawbacks of #1 and #3 without achieving any of their benefits. You claim it is the most "readable" version but that's your personal view only and even though it's important to you it's not an argument.

---

I have stated why I think it is more readable. So, it is not merely my personal view with no substantiation other than personal preference.

I vote for #3 as it makes the intent instantaneously clear ( no need to ask yourself what's going on in the loops ) and fluent ( as long as you read it correctly )

Code:

---

auto sPDN = std::find_if( CPCRF::m_mPDN2RxSessionIds.begin(), CPCRF::m_mPDN2RxSessionIds.end(), [&]( auto const& keypair )
    { return std::find( keypair.second.begin(), keypair.second.end(), sSessionId ) != keypair.second.end(); } );

if( sPDN != CPCRF::m_mPDN2RxSessionIds.end() )
{
    // ...
}

---

even better, with ( hopefully ) c++17 range support

Code:

---

if( auto sPDN = std::find_if( CPCRF::m_mPDN2RxSessionIds, [&]( auto const& keypair )
    { return std::find( keypair.second, sSessionId ); } ) )
{
    auto foundPDN = sPDN.front().first;

    // ...
}

---

Quote:

---

Originally Posted by superbonzo

even better, with ( hopefully ) c++17 range support

---

That looks good. Could you link to the relevant proposal?

Quote:

---

Originally Posted by laserlight

That's a good point: part of readability depends on the reader's familiarity with the paradigms in use. Yet, C++ is multiparadigm, so I do not see a problem with mixing and matching, hence I disagree with your criticism of #2 as being "neither nor" as a drawback.

---

Personally I consider the range-based for-loop and the standard functions to be well within the functional paradigm so #2 doesn't even represent a mix and match of paradigms to me.

I dislike #2 simply because it represents the worst of #1 and #3. The function in #2 cements sequentiality (which #1 doesn't) without getting rid of break (which #3 does).

Quote:

---

I have stated why I think it is more readable. So, it is not merely my personal view with no substantiation other than personal preference.

---

Where please?

All I see is your personal view dressed up as tokens of high readability.

Quote:

---

Originally Posted by laserlight

That looks good. Could you link to the relevant proposal?

---

there are many of them ( the code above is essentially boost.range ); I think the most advanced design to date is Niebler's range v3 but I don't think it's ready for inclusion in the std. If I had to bet, I wouldn't count on a 2017 ship date ... :(

after all, ranges are a major abstraction with vast interactions with the standard ( including yet to be released features like the much awaited Concept Lite ) and a lot of still unresolved issues ...

Quote:

---

Originally Posted by superbonzo

I vote for #3 as it makes the intent instantaneously clear ( no need to ask yourself what's going on in the loops ) and fluent ( as long as you read it correctly )

---

I agree but I find #1 better for reasons of familiarity and potential concurrency.

Firstly, #1 should be more comprehensible to a larger audience. Two nested loops iterating over a two-dimensional data structure is as old as the hills.

Secondly, #1 is easily modified to parallel execution using available concurrency libraries. This reduces the risk of having to rethink and rewrite the algorithm in the future.

Quote:

---

Originally Posted by tiliavirga

I agree but I find #1 better for reasons of familiarity and potential concurrency.

Firstly, #1 should be more comprehensible to a larger audience. Two nested loops iterating over a two-dimensional data structure is as old as the hills.

---

in my ( personal ) experience, descriptive and truth-telling names are far more important than anything else. Moreover, I'd have serious problems working with a programmer that finds std algorithms "unfamiliar" ...

the problem with #1 is that range based for loops ( however terse ) mean "traverse something" whereas I want that code to tell me "find something", the difference is huge IMO ... especially when you review/change your code months/years later ...

Quote:

---

Originally Posted by tiliavirga

Secondly, #1 is easily modified to parallel execution using available concurrency libraries. This reduces the risk of having to rethink and rewrite the algorithm in the future.

---

uhm, I'd also have serious problems working with a programmer that does not *think* ( and think and think and think ... ) when adding parallelism to some piece of code ... yes, you can easily gain orders of magnitude of run time with those libraries, but exploting your parallel hardware optimally and packing the result in a quality product looks like another story ...

Quote:

---

Originally Posted by superbonzo

there are many of them ( the code above is essentially boost.range ); I think the most advanced design to date is Niebler's range v3 but I don't think it's ready for inclusion in the std. If I had to bet, I wouldn't count on a 2017 ship date ...

---

I see. Thanks!

Quote:

---

Originally Posted by superbonzo

after all, ranges are a major abstraction with vast interactions with the standard ( including yet to be released features like the much awaited Concept Lite ) and a lot of still unresolved issues ...

---

Yeah, I recall reading Stepanov, if I remember correctly, arguing that ranges would be superior to explicit iterator pairs, but I was unaware that such a proposal might actually be close to becoming standard.

Quote:

---

Originally Posted by tiliavirga

Firstly, #1 should be more comprehensible to a larger audience.

---

I think that, correspondingly, that is a weakness with the use of generic algorithms: if you do not remember what the parameters mean, you'll have to look them up, thus negating the advantage conferred by the context supplied by the generic algorithm's name.

Quote:

---

Originally Posted by tiliavirga

Two nested loops iterating over a two-dimensional data structure is as old as the hills.

---

True, but you still need to figure out why, and it is "as old as the hills" precisely because it is so common that a great many reasons are plausible. This might not be hard (and it certainly is not hard to see that a search is being done in the case that we were discussing), but a generic algorithm would immediately provide some of that information.

Quote:

---

If you have problems exiting from them you probably shouldn't be a programmer. :)

---

I think people who can't recognize they are fallible are the ones that shouldn't be programmers.

Quote:

---

Originally Posted by monarch_dodra

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.

---

using break to exit a loop and return right away is a clean design approach. If the style guide objects to it, maybe you should ask your team WHY it's a bad thing.
Dragging conditionals into your loop makes the code more complex, adds more cases to test for, and ultimatey and most importantly makes your runtime bigger and slower because it needs to do the extra tests each loop.

in case of nested loops, breaking out out of that is probably the ONLY good reason I have for using goto. Just be sure to slap a comment on it just for good measure. Again, if your styule guide prohibits is, it maybe a good idea to change the style guide to make this exception, while "goto is nasty", the alternative is even more nasty, adding extra tests to each layer in the nested loops. So the performance impact could be even worse.


Also: be careful with trying to break or goto out of a algorithm with a predicate (lambda).. Things may not work entirely as you planned them to. :D

Quote:

---

Originally Posted by superbonzo

in my ( personal ) experience, descriptive and truth-telling names are far more important than anything else. Moreover, I'd have serious problems working with a programmer that finds std algorithms "unfamiliar" ...

the problem with #1 is that range based for loops ( however terse ) mean "traverse something" whereas I want that code to tell me "find something", the difference is huge IMO ... especially when you review/change your code months/years later ...

---

What's wrong with putting in a comment, or wrapping up general code in a function giving it a telling name?

The purpose of a standard library is to provide functionality, not to supply particularly telling function names. And even though library names can be telling they're often kind of bland aren't they? Why use plain find when find_string, find_out or find_love may fit the occasion better? Don't let the standard library limit your creativity.

Besides, relying on standard function names to express purpose can be misleading. Take find_if for example. In essence it's a range-based for-loop so when using find_if you may just be iterating and breaking not looking to find anything. The suggestive function name turns out a diversion rather than a help. Don't rely on standard function names to convey intent.

Furthermore, when your ignorant collegues put in a range-based for-loop there is no reason for you to sulk in your cubicle. Instead smile affirmingly as they have used find_if without even knowing.

Quote:

---

uhm, I'd also have serious problems working with a programmer that does not *think* ( and think and think and think ... ) when adding parallelism to some piece of code ... yes, you can easily gain orders of magnitude of run time with those libraries, but exploting your parallel hardware optimally and packing the result in a quality product looks like another story ...

---

Then be happy Mother Nature took a chance and made your brain work in parallel. Otherwise you wouldn't be able to finish one single thought in your lifetime regardless of how hard you were thinking.

After many long hours and much deliberation the C++ standards committee in 2011 finally agreed on a concurrent version of C++. It was a milestone in C++ history and just in the nick of time because most computers came with multiple cores already. But when the operating system generously offers many cores to your applications you stubbornly decline, saying thank you but no thank you; One core will be just fine; Many cores gives me the creeps; Better slow and safe than sorry. This is both unprofessional and uncharacteristic. C++ is about efficiency and C++ programmers traditionally are performance conscious and known for their wish and ability to squeeze the last drop out of available hardware. Ignoring concurrency is no longer an option. It's time to shape up or ship out.