map with iterator as key?

Hi

I'd like to have a map where the key type is an iterator. This will not work out of the box because a map requires the availability of the less than operator for each key (and my understanding is that most (all?) iterator types do not have a less than operator by default). Does anyone know a way of defining a less than operator to an iterator? Perhaps using memory addresses (which are unique)?

Thanks

Edit:

Why is this not compiling?

#include <iostream>
#include <set>
#include <map>

bool operator < (std::map<int, std::string>::iterator const& lhs, std::map<int, std::string>::iterator const& rhs)
{
    return &lhs < &rhs; // use memory addresses to compare
}

int main() {
    // Write C++ code here
    std::map<int, std::string> data;
    std::map<int, std::string>::iterator it = data.begin();
    
    std::set<std::map<int, std::string>::iterator> meta;
    
    meta.insert(it);
    
    return 0;
}

Last edited on

lastchance (6980)

I have a lot of qualms about the idea of putting iterators in sets. They might get invalidated when you have your back turned. This compiles and runs, but I don't like it.

What are you actually intending to do with your program?

#include <iostream>
#include <set>
#include <map>

struct classcomp {
  bool operator() (const std::map<int, std::string>::iterator & lhs, const std::map<int, std::string>::iterator & rhs) const
  {return &lhs<&rhs;}
};

int main() {
    std::map<int, std::string> data;   data[10] = "Hello";
    std::map<int, std::string>::iterator it = data.begin();
    
    std::set<std::map<int, std::string>::iterator,classcomp> meta;
    meta.insert(it);
    
    for ( auto iter : meta )
    {
       std::cout << iter->first << "  " << iter->second << '\n';
    }
}

But I confess that I don't understand why your original code didn't compile. It was failing at the insert statement, but I can't see why it didn't fail at the set constructor.

Last edited on

rozick1 (218)

Thanks

What I am really trying to do is to link two separate entries in a multimap:

std::multimap<int, std::string> data;

As an example, "data" above might be:

Key:        Value:
0             "a"
0             "b"
1             "c"
2             "d"
2             "e"

What I need to do is to link a particular "entry" to another "entry". So, for example, link {1, "c"} to {2, "e"} so that if I was on {1, "c"} then I would know to lookup {2, "e"}.

My idea was to do this via a map of iterators (with the key being one iterator and the linked iterator being the value).

I'm open to other suggestions. I did think about the value being a struct of the value and the linked iterator but I don't particularly wish to do this as it will expose something to the client which shouldn't really be exposed.

Thanks

jonnin (11437)

if I understood you correctly, this looks like place for a hashed value.
The idea is you make a function that can generate a unique value from the data, to tie the entities together. Its pretty much exactly what you are already trying to do, except you need to use the data (eg 1,c) to make some intermediate value that you can use to find 2,e.
you may be able to do that directly with unordered map, without dealing with the hashed value yourself, such that unordered_map m[{1,'c'}] == {2,'e'}
however if something else also points to 2,e that simple approach won't cut it.
it may be that you need to get the data into something where it stays put, like a vector, and once it is locked into location, map the data using the vector index (as if a pointer) with the more exotic data structures. The good news is the mapping structures all lead back to the vector, everything not the vector is very, very lightweight, just an 'organizational layer' kind of like sorting an array of pointers to real data is cheaper than sorting very fat objects with copies and all...

Last edited on

JLBorges (13770)

> Does anyone know a way of defining a less than operator to an iterator?
> Perhaps using memory addresses (which are unique)?

We can't use address of an iterator as the key: iterators use value semantics.

> link two separate entries in a multimap

We can exploit the fact that references to an element in a multimap are not invalidated when items are added or other elements are erased.

Note that there is no undefined behaviour here: the specialization of std::less for pointer types yields a well defined strict total order (even though the built-in < operator may not).

#include <iostream>
#include <string>
#include <map>

int main()
{
    std::multimap<int,std::string> mmap { {0,"ab"}, {0,"cd"}, {0,"ab"}, {0,"ef"}, {1,"gh"}, {1,"ij"} } ;

    using kv_pair = std::pair<const int,std::string> ;
    std::map< const kv_pair*, const kv_pair* > links ;

    // link {0,"cd"} to {1,"ij"}

    // get address of node {0,"cd"}
    kv_pair* key = nullptr ;
    for( auto [iter,till] = mmap.equal_range(0) ; iter != till ; ++iter )
            if( iter->second == "cd" ) key = std::addressof(*iter) ;

    // get address of node {1,"ij"}
    kv_pair* value = nullptr ;
    for( auto [iter,till] = mmap.equal_range(1) ; iter != till ; ++iter )
            if( iter->second == "ij" ) value = std::addressof(*iter) ;

    // create the link
    if( key && value ) links.emplace( key, value ) ;

    // test it
    for( const kv_pair& pair : mmap )
    {
        const auto iter = links.find( std::addressof(pair) ) ;
        if( iter != links.end() )
        {
            std::cout << '{' << iter->first->first << ',' << iter->first->second << "} is linked to {"
                             << iter->second->first << ',' << iter->second->second << "}\n" ;
        }
    }
}

http://coliru.stacked-crooked.com/a/fad620378996c927

Last edited on

Topic archived. No new replies allowed.

C++

Forum

map with iterator as key?