Coding std::sort on struct that needs deep copy

Question

I have a struct

typedef unsigned int    gsk_uint32;
typedef struct _gsk_oid {
    int                 count;
    gsk_uint32 *        elements;
} gsk_oid;
struct oidX : public gsk_oid
{
    oidX();     // Default
    oidX(int countX, gsk_uint32 first, ...);        // From list of integers
    oidX(const char* oidString);        // From dotted notation
    oidX(const gsk_oid *inOID);     // From gsk_oid
    ~oidX();        // destructor
};

I have a struct that has the above OidX as a member:

struct oidPair {
    oidX *TheOID;
    const char *Descript;
    oidPair(oidX *inputOID, const char *inputDescript); 
    ~oidPair();
};

I define an array of the above structs

oidPair testOIDs[4] = {
    oidPair(new oidX("2.23.140.1.2.3"), "Certificates issued in accordance with the CA/Browser Forum's Baseline Requirements - Individual identity asserted"),
    oidPair(new oidX("2.23.140.1.1"), "Extended Validation (EV) guidelines certificate policy"),
    oidPair(new oidX("1.3.6.1.4.1.4146.1.20"), "Organization validation certificate policy"),
    oidPair(new oidX("2.23.140.1.2.2"), "Certificates issued in accordance with the CA/Browser Forum's Baseline Requirements - Organization identity asserted") };

Yes, I could define them in sorted order but there are lot more elements than I list above and I would like to avoid traps for the unwary, so at startup I want to sort the above array. I issue std::sort(testOIDs, testOIDs+4, &Oid_less);

Here's the compare function:

int DecodeOID::Oid_cmp(const gsk_oid *left, const gsk_oid *right)
{
    int cnt = std::min(left->count, right->count);      // Shorter of the two vectors
    int ret = memcmp(left->elements, right->elements, cnt*4); // compare elements
    if ( 0 != ret ) return ret;  // if unequal we are done
    return left->count - right->count;      // else longer is considered greater
}
bool DecodeOID::Oid_less(const oidPair &left, const oidPair &right)
{
    const gsk_oid *l = left.TheOID;
    const gsk_oid *r = right.TheOID;
    int ret = Oid_cmp(l, r);
    return ret < 0;
}

The third time that sort calls Oid_less &right references an oidPair with an uninitialized OidX and it fails on a memory exception. I understand that I may need a move operator or something like that, but I don't know exactly what to code. Suggestions appreciated.

You will need copy or move constructors and copy or move assignment operators. I recommend starting with the [Copy and Swap Idiom](https://stackoverflow.com/q/3279543/4581301) because it is nearly fool-proof and usually fast enough. Profiling will let you know fairly quickly if it's not fast enough, and at that point you can ask a very well-targeted question if needed. — user4581301, Aug 09 '23 at 23:12
You haven't provided a [MCVE] here. We have no idea how ownership works for the struct members (are they borrowed? owned?). Why are you not adhering to [the Rule of Three/Five](https://stackoverflow.com/q/4172722/364696)? Why not use `std::unique_ptr` or `std::shared_ptr` to manage the memory for you? The Rule of Three/Five is *extremely* important if you're manually managing memory or other resources, plain constructors and a destructor are insufficient in that case. I agree with @user4581301 that the copy-and-swap idiom is the best way to handle this, in terms of simplicity/correctness. — ShadowRanger, Aug 09 '23 at 23:14
Side note: For `oidX(int countX, gsk_uint32 first, ...);` see if you can migrate to an [initializer list](https://en.cppreference.com/w/cpp/utility/initializer_list). Generally a little easier, and a lot safer, to use than a variable arguments list. — user4581301, Aug 09 '23 at 23:15
Firstly, your `oidPair` appears to suffer from not respecting the [Rule of Three (or Five)](https://stackoverflow.com/q/4172722/1553090). Furthermore, as of C++11 a sort operation should not require any copying if you correctly support move semantics. You appear to realize this, so all you need to do is consult reference material for the actual requirements of a move constructor / move-assignment operator. The suggestion of using copy-and-swap idiom is a perfect place to start. In practice, swaps are used more often than not when implementing move semantics. — paddy, Aug 09 '23 at 23:15
If this C code that's only pretending to be C++, gets replaced by real C++ code, that simply uses `std::vector`, then noone needs to worry about deep copy. Your C++ compiler will do it for you, automatically. — Sam Varshavchik, Aug 09 '23 at 23:51
@SamVarshavchik the underlying gsk_oid struct is in a library over which I have no control, and which will probably be C-compatible forever. — Charles, Aug 09 '23 at 23:58
@user4581301: if I declare and implement a swap method as shown, then sort will call it automatically? — Charles, Aug 09 '23 at 23:59
The automatic part is more the result of correctly observing the Rule of Three or Five. The Copy and Swap Idiom is just a simple and effective method of implementing the Rules of Three and Five. Once you have the copy and move semantics implemented for your object your life gets easier in just about every way, including swaps and sorts. — user4581301, Aug 10 '23 at 00:08
This does not, in any way, prevent using `std::vector` in all C++ code, and then simply constructing a `gsk_oid` struct when needed to call the library; letting `std::vector` correctly manage the actual memory buffer and just constructing a `gsk_oid` on the fly (pointing to the vector's contents) when needed to interface with the library. You already have an `oidX` wrapper, actually. Just broom away everything's in there, and write a single contructor that takes a `std::vector` as a parameter. Mission accomplished. — Sam Varshavchik, Aug 10 '23 at 00:25
@Charles *Coding std::sort on struct that needs deep copy* -- Another alternative is to not sort the `struct` itself, but sort using an index array. [See this example, and read the answer, especially item 3](https://stackoverflow.com/questions/46382252/sort-array-by-first-item-in-subarray-c/46382976#46382976). Your structs could be as nutty as they want to be, if they are not being moved around, then sorting can still take place by using the methods at the link — PaulMcKenzie, Aug 10 '23 at 08:16
You could also just sort a vector of `std::reference_wrapper`s that point to your original. No need to copy or move anything. — Jesper Juhl, Aug 11 '23 at 12:56

score 0 · Answer 1 · answered Aug 11 '23 at 12:51

Thank you all. Yes, adding a copy and operator=() to oidPair (based on swap) solved the problem. I was focusing on the OidX where the exception was occurring, but of course it is the oidPair's that are being sorted.

Overhead is not a major concern. The table is at this point 22 items and will probably no more than double. It starts out almost in the correct order, so the number of swaps is minimal.

    friend void swap(oidPair& first, oidPair& second) // nothrow
    {
        using std::swap;
        swap(first.TheOID, second.TheOID);
        swap(first.Descript, second.Descript);
    }
    oidPair& operator=(oidPair other) 
    {
        swap(*this, other); 
        return *this;
    }
    oidPair(const oidPair &key)      // System copy
    {
        this->TheOID = new oidX(key.TheOID);
        this->Descript = key.Descript;
    }

Coding std::sort on struct that needs deep copy

1 Answers1