Re: Find specific element of multimap?

Discussion in 'C++' started by John Harrison, Aug 14, 2003.

  1. "Dave O'Hearn" <> wrote in message
    news:...
    > Is there any way to search for a specific (key,value) pair in multimap
    > with complexity guarantees? Like if I had this thing,
    >
    > std::multimap<int,double> my_map;
    > my_map.insert(std::make_pair(1, 1.1));
    > my_map.insert(std::make_pair(1, 1.2));
    > my_map.insert(std::make_pair(2, 2.1));
    > my_map.insert(std::make_pair(2, 2.2));
    >
    > Can I ask the multimap "does 1 map to 1.2 at all?" with O(N)
    > complexity, or do I have to ask for the lower bound on 1 and scan
    > forwards?


    You mean O(log N)? A scan forward will give you O(N) complexity.

    >
    > I'm guessing no. Right now, I made a class that represents a
    > many-to-many relation between 2 value types. It uses two maps of sets,
    > each one does the lookup in one direction. It works, and is a great
    > improvement over the old structures I replaced with it. But something
    > about this...
    >
    > template<typename T1, typename T2>
    > class many_to_many
    > {
    > private:
    > typedef std::set<T1> T1set;
    > typedef std::set<T2> T2set;
    > typedef std::map<T1, T2set> forward_rel;
    > typedef std::map<T2, T1set> inverse_rel;
    > forward_rel map1;
    > inverse_rel map2;
    >
    > Well, it feels very heavy weight, and I'm looking for a more elegant
    > way to express the relationship.
    >


    If you just want to look up whether two items are related then simply

    class many_to_many
    {
    std::set< std::pair<T1, T2> > rel;
    };

    but I guess that is only part of your requirements.

    > --
    > Dave O'Hearn
     
    John Harrison, Aug 14, 2003
    #1
    1. Advertising

  2. John Harrison

    Dave O'Hearn Guest

    "John Harrison" <> wrote:
    > "Dave O'Hearn" <> wrote:
    > > Can I ask the multimap "does 1 map to 1.2 at all?" with O(N)
    > > complexity, or do I have to ask for the lower bound on 1 and scan
    > > forwards?

    >
    > You mean O(log N)? A scan forward will give you O(N) complexity.


    Yeah, I meant O(lg N).

    > If you just want to look up whether two items are related then simply
    >
    > class many_to_many
    > {
    > std::set< std::pair<T1, T2> > rel;
    > };
    >
    > but I guess that is only part of your requirements.


    I do have a few cases like that, and I didn't create any fancy
    wrappers around them; they are just sets of pairs. But the "relation"
    class I have does have more requirements like you guessed. I have to
    be able to search for or drop everything that matches one half of the
    relation. I made it a class because it's full of invariants on the
    maps being inverses of each other, and it needed a restricted
    interface.

    I also thought of using 2 sets of pairs, instead of 2 maps of sets.
    With a set of pairs, I can search for an exact match if I want. But I
    couldn't find any way to express the lower_bound and upper_bound
    operations on a set. I know algorithms to do it if I have access to
    the tree structure, but sets don't expose those details.

    --
    Dave O'Hearn
     
    Dave O'Hearn, Aug 14, 2003
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    446
    Mark P
    Oct 20, 2005
  2. Victor Bazarov
    Replies:
    15
    Views:
    1,208
    Vaclav Haisman
    Aug 16, 2009
  3. mazdotnet
    Replies:
    2
    Views:
    421
    Alexey Smirnov
    Oct 2, 2009
  4. joseph cook
    Replies:
    1
    Views:
    921
    Steve
    Nov 28, 2009
  5. Steve
    Replies:
    0
    Views:
    288
    Steve
    Nov 28, 2009
Loading...

Share This Page