kissu_pari_na's blog

Use Structure as a key of map
By kissu_pari_na, history, 7 years ago, In English

Is it possible to use a structure as the key of a map?! If it is, then how can I do this? thanks in advance.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 5   Vote: I like it +22 Vote: I do not like it

Yes, but you have to implement the Boolean comparison operator '<' that the map class uses to order the entries.

For example:


struct mystruct { 

    int x, y; 

    bool operator < ( const mystruct &b ) { return x < b.x || ( x == b.x && y < b.y ); }

};


map< mystruct, int > z;
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Got it.. Thanks man.. Using this just solve today's CF round D2 E.. :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      With pleasure.

      The Boolean comparison operator< is also used by the sort() function to sort an array of structure items, and by other containers such as a set or a list when it is required to order a set or a list of structure items.

      For example,


      mystruct a[ 100 ]; set< mystuct > b; list< mystruct > c;

sort( a, a + 100 ); c.sort();

      This method helps in solving many CF problems as well.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for your kind information :)

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Suppose I have a vector of a structure. It is sorted by the operator overloading method. Now, can I apply upper_bound and lower_bound operations on this vector ? how ?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Yes, as long as the vector has been sorted using the Boolean operator<.

          Example:


          struct mystruct: public pair< int, int > {

    mystruct( const int x, const int y ) { first = x, second = y; }

    bool operator < ( const mystruct &b ) const { return first < b.first || ( first == b.fist && second < b.second); }

    friend ostream& operator << ( ostream &os, const mystruct &b ) { return os << b.first << " " << b.second; }
};

int main()
{
    vector< mystruct > z;

    z.emplace_back( 3, 4 );
    z.emplace_back( 1, 2 );
    z.emplace_back( 5, 6 );

    sort( z.begin(), z.end() );

    for( auto x: z )
        cout << x << endl;

    cout << endl;

    cout << *lower_bound( z.begin(), z.end(), mystruct( 3, 3 ) ) << endl;

    cout << *upper_bound( z.begin(), z.end(), mystruct( 4, 4 ) ) << endl;
}

          Output:

          1 2

          3 4

          5 6

          3 4

          5 6

          → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          The following is the previous example augmented with struct myvector wrapper for vector< mystruct >: 


          struct mystruct: public pair< int, int > {

    mystruct( const int x, const int y ) { first = x, second = y; }

    bool operator < ( const mystruct &a ) const { return first < a.first || ( first == a.first && second < a.second ); }

    friend ostream& operator << ( ostream &os, const mystruct &a ) { return os << x.first << " " << x.second; }
};

struct myvector: public vector< mystruct >
{

    void order() { sort( begin(), end() ); }

    friend ostream& operator << ( ostream& os, const myvector &v )
    {
        for( auto x: v )
            os << x << endl;

        return os;
    }

    iterator lb( const mystruct &x ) { return lower_bound( begin(), end(), x ); }

    iterator ub( const mystruct &x ) { return upper_bound( begin(), end(), x ); }

} z;

int main()
{
    z.emplace_back( 3, 4 );
    z.emplace_back( 1, 2 );
    z.emplace_back( 5, 6 );

    z.order();

    cout << z << endl;

    cout << *z.lb( mystruct( 3, 3 ) ) << endl;

    cout << *z.ub( mystruct( 4, 4 ) ) << endl;
}
          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    And that is not a valid comparison operator. Please read http://en.cppreference.com/w/cpp/concept/Compare .

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for your comment.

      A C++11 solution for problem 869E - The Untended Antiquity has successfully used this operator to order points and rectangles in a 2D grid, please read 31224413.

      Can you briefly explain the reason that this operator is invalid?

      Thanks in advance.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        The equivalence established by operator isn't transitive. For pairs a=(1, 5), b=(3,1), c=(4, 2) a=b a=c and b<c. It might work if if input is guaranteed not to contain such input or were simply lucky that with given inputs and STL implementation details output was suitable to rest of your code.

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        So on cppreference page it says that transitivity for equiv function should be fullfilled where equiv(a,b) = !comp(a,b) && !comp(b,a) where comp is your comparison function.

        In your case it is not fullfilled. For example:

        1. (2,1) is equivalent to (1,3) (because neither (2,1)<(1,3), nor (1,3)<(2,1) is true)
        2. (1,3) is equivalent to (3,2) (same reasoning)
        3. (3,2) on the other hand is not equivalent to (2,1) because (2,1) < (3,2) is true.

        What implications it may have during sort:

        For example: (3,2), (1,3), (2,1) is technically valid sorted sequence even though (2,1) < (3,2). If during our sort we compare only neighbour values then our sort would stop without any changes because sequence is already observably sorted.

        As for why it worked for the task — I don't know, it probably requires some additional investigation. But you better avoid using such operators since result is undefined.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Thanks for the clarification.

          In the statement of the aforementioned problem, it is guaranteed that no two rectangle boundaries intersect.

          The solution uses a rectangle_tree class whose root node is the entire 2500 x 2500 area. The children of each node (u) in the rectangle_tree are the largest non-intersecting rectangles contained in (u). Insertions and deletions update the tree according to inserted/deleted rectangles. A walk query returns "Yes" if and only if the smallest rectangles containing the source and the target cells are the same.

          The Boolean operator are used to compare the corresponding upper-left and lower-right of rectangle pairs preserving the order of the corner cells, and to compare query points to those corner cells. Therefore, there is on luck in the success of the solution.

          It is just the case that those counterexamples mentioned in your clarification are guaranteed to never take place.

          The Boolean operator< is NOT used to sort an array of 2D points. It is just used to update the rectangle tree when a rectangle is inserted or deleted.

          Best Regards.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I thought we were talking about comparator for STL functions. The requirements are what STL expects. If you only use it yourself it can do whatever you want even multipliciation. That doesn't mean it's always a good idea even more so if you give it as example of how to use it with map. Abusing operator overloading can easily cause misunderstandings like this when it is not obvious what operator X does for structure Y or it doesn't match conventions.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 5   Vote: I like it 0 Vote: I do not like it

              Thanks for your precious comments.

              I agree with you that giving that example for sorting an array of structures was not a good choice; my apologies for the inconvenience, and my appreciation for your effort to clarify what confused you.

              If you check the submitted solution, you will find that the operators 


              bool operator <  ( const cell &c1, const cell &c2 )
{
    return c1.first <  c2.first && c1.second < c2.second;
}

bool operator <= ( const cell &c1, const cell &c2 )
{
    return c1.first <= c2.first && c1.second <= c2.second;
}

              are called from the rectangle_tree methods:


              bool contains( const rectangle_tree &r ) const
{
   return first < r.first && r.second < second;
}

bool contains( const cell &c ) const
{
        return first <= c && c <= second;
}

              The former contains() function returns true when the rectangle object contains rectangle (r), and the latter contains() function returns true when the rectangle object contains the query point given by the cell (r).

              The base class pair< cell, cell > is used to hold the upper-left and lower-right corners of the rectangle.

              → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The example for implementing bool operator< has been updated to comply with STL requirements.

    A word of gratitude is due to KarlisS and predelnik for their fruitful comments and efforts to elaborate the problem with the previous example.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it

    If x and y in the previous example are known to be positive integers <= 4294967295U (UINT_MAX), then it is possible to concatenate the two 32-bit unsigned integers into one 64-bit unsigned integer using c++ union as follows:


    #include <bits/stdc++.h>

using namespace std;

const unsigned one = 1U; const bool little_endian = *( (char *) ( &one ) ), big_endian = !little_endian;

struct mystruct
{
    union { unsigned u[ 2 ]; unsigned long long v; } data;

    mystruct( const unsigned x0 = 0, const unsigned y0 = 0 ) { data.u[ big_endian ] = x0, data.u[little_endian ] = y0; }

    bool operator < ( const mystruct &b ) const { return data.v < b.data.v; }

    void read() { scanf( "%u %u", data.u + big_endian, data.u + little_endian ); }

    void write() { printf( "%u %u", data.u[ big_endian ], data.u[ little_endian ] ); }
};

struct myvector: public vector< mystruct >
{

    void order() { sort( begin(), end() ); }

    void read( const unsigned n ) { mystruct a; for( unsigned i = 0; i < n; i++ ) a.read(), push_back( a ); }

    void write() { for( auto p: *this ) p.write(), putchar( '\n' ); }

    mystruct& lb( const mystruct &x ) { return *lower_bound( begin(), end(), x ); }

    mystruct& ub( const mystruct &x ) { return *upper_bound( begin(), end(), x ); }
} z;

int main()
{
    unsigned n;

    scanf( "%u", &n ), z.read( n ), z.order(), z.write(), putchar( '\n' );

    mystruct a;

    a.read(), z.lb( a ).write(), putchar( '\n' );

    a.read(), z.ub( a ).write(), putchar( '\n' );
}

    The Boolean operator< compares the corresponding 64-bit numbers directly.

    → Reply