Talk:cpp/container/unordered multiset

For an ordered multiset it is (obviously) the case that on linear traversal (begin to end) all elements with the same value come one after the other.

Therefore it is possible to retrieve the count for some element value and skip following elements with the same value (or process these in a special ways), i.e. it is easy to "group" elements with the same value on sequential traversal.

How is that for the unordered_set (and same question for the keys in an unordered_map)?

On sequential traversal, are all elements with the same value visited in sequence or is this only the case for all elements in the same bucket (i.e. hashing to the same index), but may these elements be visited in any mix?

Or is even nothing of the above guaranteed for sequential traversal of unordered containers?

If it is not guaranteed that elements with the SAME VALUE are visited one after the other on sequential traversal, I think it should be shortly mentioned (may be it is, but on a different page?), as otherwise it may be an evil pitfall when switching from ordered to unordered sets (or maps) for efficiency reasons, and elements with the same value are processed in "groups" (as described above). Especially as the problem might not show on tests, as long as there are no two values hashing to the same bucket.

For the moment I suppose the existance of a member function like equal_range forces an implementation to store elements with the same value consecutively, but I didn't find an explicit statement about it.

--Mwe (talk) 00:27, 26 May 2015 (PDT)

I think this is the explicit statement that you want (quoted from N4527 §13.2.5[unord.req]p6, bold mine):

An unordered associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. unordered_set and unordered_map support unique keys. unordered_multiset and unordered_multimap support equivalent keys. In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container. Thus, although the absolute order of elements in an unordered container is not specified, its elements are grouped into equivalent-key groups such that all elements of each group have equivalent keys. Mutating operations on unordered containers shall preserve the relative order of elements within each equivalent-key group unless otherwise specified.

C++11 has exactly the same wording. --D41D8CD98F (talk) 04:36, 26 May 2015 (PDT)

Is this (or at least the boldened part from above) already somewhere in cppreference.com?

If not, where would be the logical place to include it?

I'm willing to contribute a short example which groups equivalent keys while iterating over an unordered_multiset or map, for which the above guarantee is important.

--Mwe (talk) 05:11, 26 May 2015 (PDT)

I added a short note to the leads, not sure where such an example would be fitting.. perhaps in std::unordered_multiset::begin? --Cubbi (talk) 06:16, 26 May 2015 (PDT)

OK, below is the example I wanted to contribute ... but when clicking "edit" I get only a list of includes(?) that seem to name versions of that page in different languages. No clue where and how I would really add example code to appear on the suggested page ...

Count words using unordered_multiset

Run this code

#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>
 
/*
 * Note:
 * this depends on the guarantee that values with equivalent keys are
 * adjacent to each other when iterating over an unordered_multiset
*/
int main() {
    const std::unordered_multiset<std::string> words = {
        "some", "words", "to", "count",
        "count", "these", "words"
    };
 
    auto it = words.begin();
    while (it != words.end()) {
        auto cnt = words.count(*it);
        std::cout << *it << ":\t" << cnt << std::endl;
        while (cnt-- > 0)
            ++it;
    }
}

added --Cubbi (talk) 07:33, 26 May 2015 (PDT)

thanks, and after some more studying the wiki page structure and inclusion via macros I think I have now understood how I can insert examples in the "real" wiki pages.

Before I do, let me know if the following (similar example) is OK as example for unordered_multimap::begin.

demonstrate unordered_multimap

Run this code

#include <iostream>
#include <string>
#include <unordered_map>
 
int main() {
    const std::unordered_multimap<std::string, int> words = {
        { "some",       1 },
        { "words",      2 },
        { "enumerated", 3 },
        { "with",       4 },
        { "some",       5 },
        { "duplicated", 6 },
        { "words",      7 },
    };
 
    for (auto it = words.begin(); it != words.end(); )
    {
        std::cout << it->first << ':';
        for (auto cnt = words.count(it->first); cnt != 0; --cnt)
            std::cout << ' ' << (it++)->second; // elements with equal keys
        std::cout << std::endl;
    }
}

--Mwe (talk) 10:00, 26 May 2015 (PDT)

the examples on this wiki don't use endl where flushing is not required by the example (see std::endl). Also to me the inner loop is becoming a little bit hairy, but the best alternative I could think of on the spot was for (auto p = words.equal_range(it->first); it != p.second; ++it) std::cout << ' ' << it->second; which isn't much of an improvement. Don't forget the |p=true and |output=... --Cubbi (talk) 11:19, 26 May 2015 (PDT)

Thanks, I'll use '\n'-s in place of std::endl-s for future contributions.

Also, wrt the nested loops, I share your view that these usualy should get attention because of their potential to cause O(N*N) performance, but in this case the inner loop is just a different place to do the increment of the iterator from the outer loop, so performance is still O(N).

Looking once more how you inserted my first example in the begin()/cbegin() page for the container classes, I'm a bit worried whether I'm really expected to make all examples part of a big macro-switch in single page. There seems to be a more manageable solution for other examples (with separate files per example?) but I don't quite get it still. (I'm really not THAT much experienced with MediaWiki and its macro/template machinery.)

--Mwe (talk) 00:50, 27 May 2015 (PDT) I will also include output in future cases, but I'm not quite sure if

it's not the algorithmic complexity I'm pointing out (it's linear either way), it's simplicity of the example: the reader has to mentally switch from incrementing it to both decrementing cnt and incrementing it on every iteration, my suggested version with equal_range just keeps doing ++it. As for the giant switch, most pages aren't as heavily templated, and for most heavily-templated pages, the examples usually try to be as generic as possible, see Template:cpp/container/resize. There are templates that group containers by type (sequential, ordered, associative), so it's sometimes possible to make use of that. --Cubbi (talk) 03:02, 27 May 2015 (PDT)

Since the example for Container::begin() can't be so generic, I think each container having its own example page might be better. Template:cpp/thread/mutex/try_lock already tried this way. --D41D8CD98F (talk) 06:45, 28 May 2015 (PDT)