C++ std::map different key addressing the same index

Question

Whilst doing refactoring I've somehow screwed up my code so the std::map I'm using stopped working properly.

I'm reassembling fragmented IPv4 packet. Partially parsed Packet comes and if it's fragment of packet it becomes Fragment which has function for reassembling.

...    
if(packet.isIPv4() && packet.isFragment()){
    auto keyForMap = packet.key();
    auto it = fragments.find(keyForMap);
    auto fragmentNotFound = fragments.end();

    std::cout << "-----------------------"  << std::endl;        
    std::cout << "Fragments len: " << fragments.size() << std::endl;        

    keyForMap.print();

    if(it == fragmentNotFound){
        std::cout << "Not Found" << std::endl;
        fragments[keyForMap] = Fragment(packet);
    } else {
        std::cout << "Found" << std::endl;

        fragments[keyForMap].add(packet);
        /* reassembling function call and some processing */
        }
    }
}
...

Data types used: IPv4 is std::array<uchar_t, 4>

fragments is fragments_t &

fragments_t is std::map<FragmentCommon, Fragment>

struct FragmentCommon{
    FragmentCommon(IPv4 ipsrc,
                   IPv4 ipdst,
                   uchar_t protocol,
                   uint16_t identification) : ip_src(ipsrc),
                                              ip_dst(ipdst),
                                              protocol(protocol),
                                              identification(identification){};

    void print(){
        printf("key>%d.%d.%d.%d ", ip_src[0], ip_src[1], ip_src[2], ip_src[3]);
        printf("%d.%d.%d.%d ", ip_dst[0], ip_dst[1], ip_dst[2], ip_dst[3]);
        printf("%d %d\n", protocol, identification);
    };

    IPv4 ip_src;
    IPv4 ip_dst;
    uchar_t protocol;
    uint16_t identification;
};

static bool operator<(const struct FragmentCommon &lhs, const struct FragmentCommon &rhs){
    return lhs.ip_dst         < rhs.ip_dst &&
           lhs.ip_src         < rhs.ip_src &&
           lhs.protocol       < rhs.protocol &&
           lhs.identification < rhs.identification;
}

This is output my code gives me:

-----------------------
Fragments len: 0 // Correct (this is first fragment so nothing is in map)
key>192.168.1.3 192.168.1.4 6 1
Not Found // So it's added into map
-----------------------
Fragments len: 1 // Correct (1st fragment is in map)
key>192.168.1.5 192.168.1.6 6 1
Found // Not correct...keys are different
-----------------------
Fragments len: 1
key>192.168.1.5 192.168.1.6 6 1
Found
-----------------------
Fragments len: 1
key>192.168.1.5 192.168.1.6 6 1
Found
-----------------------

Does FragmentCommon have operator <? I'm not sure how it would ever work without, but it's not shown and your map doesn't have a custom comparator. — Useless
– Useless, Commented Oct 28, 2017 at 22:54
@Useless Yes it has static bool operator<(const struct FragmentCommon &lhs, const struct FragmentCommon &rhs){ return lhs.ip_dst < rhs.ip_dst; } — gnivirht
– gnivirht, Commented Oct 28, 2017 at 22:58
Please edit your question to add that critical information. So given that definition, what does operator< for IPv4 do? — aschepler
– aschepler, Commented Oct 28, 2017 at 23:00
That should have been included in the question, since it's part of the public interface of the type. The function is actually wrong in general (it should compare all members), but ought to work in your example. However, since you don't show your actual code: is that operator visible when the map is declared? Is it in the same namespace as FragmentCommon and definitely being used? When you test it in isolation, does it do what you expect? — Useless
– Useless, Commented Oct 28, 2017 at 23:01
@SamoPoláček -- You posted irrelevant functions such as print(), but you left out operator < in your question, which is the major part of std::map and how it works. — PaulMcKenzie
– PaulMcKenzie, Commented Oct 28, 2017 at 23:02

PaulMcKenzie · Accepted Answer · 2017-10-29 01:25:27Z

2

Given what you've posted and stated in the question, since IPv4 is a std::array<uchar_t,4> (I'm assuming that uchar_t is an alias for unsigned char), you can define operator < for FragmentCommon using std::tie.

Using std::tie is simpler and less-error prone for defining a strict-weak ordering (required for std::map keys) when dealing with multiple values to test for in a "cascading" fashion.

#include <tuple>
//...
static bool operator < (const struct FragmentCommon &lhs, const struct FragmentCommon &rhs)
{
    return std::tie(lhs.ip_dst, lhs.ip_src, lhs.protocol, lhs.identification) < 
           std::tie(rhs.ip_dst, rhs.ip_src, rhs.protocol, rhs.identification);
}

Since std::array has operator < defined, using std::tie works correctly when using all 4 arguments in each std::tie.

answered Oct 29, 2017 at 1:25

PaulMcKenzie

35.6k4 gold badges26 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

C++ std::map different key addressing the same index

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related