Home > Software design >  How to find out new index of the element in a vector after using std::unique
How to find out new index of the element in a vector after using std::unique

Time:09-07

In the following function, impObj argument currently points to a particular index in myVec and after using std::unique I want to update impObj to point to the same MyClass instance in vector (or the instance which was sequentially equal to original)

void RemoveSequentialDuplicates(std::vector<MyClass>& myVec, int& impObj)
{
    auto itrLast = std::unique(myVec.begin(), myVec.end(), [](const MyClass& first, const MyClass& second) -> bool {
       return first == second;
    });
    myVec.erase(itrLast, myVec.end());
}

One way to do it is -

void RemoveSequentialDuplicates(std::vector<MyClass>& myVec, int& index)
{
    int leftIndex = 0, rightIndex = 1;
    auto itrLast = std::unique(myVec.begin(), myVec.end(), [&leftIndex, &rightIndex, &impObj](const MyClass& first, const MyClass& second) -> bool {
        bool equals = false;
        if (first == second)
            equals = true;
        else
            leftIndex  ;

        if(impObj == rightIndex)
            impObj = leftIndex;

        rightIndex  ;
        return equals;
    });
    myVec.erase(itrLast, myVec.end());
}

Is there a better way to do it?

Note: I want to keep the order of the elements same

CodePudding user response:

Details are missing, but it could be done by spiting operation into two steps:

  • before impObj (equivalent)
  • and from impObj (equivalent)
void RemoveSequentialDuplicates(std::vector<MyClass>& myVec, int& impObj)
{
    // find first item equal to impObj, lower_bound is naive approach 
    auto firstObj = std::lower_bound(begin(myVec), end(myVec), myVec[impObj]);

    auto before = std::unique(begin(myVec), firstObj);
    impObj = std::distance(begin(myVec), before);
    auto newEnd = std::unique_copy(firstObj, end(myVec), before);
    myVec.erase(newEnd, myVec.end());
}

https://godbolt.org/z/c8Ysj6j45

Note use of std::lower_bound is a quick first choice. Depending on exact scenario there are better choices. Possible improvement.

Disclaimer

This was not specified in question so code assumes that:

  • vector is not empty
  • value of impObj is in bounds of myVec

CodePudding user response:

If you want to remove duplicates from container consider using std::list instead of std::vector like so:

std::list<int> values{ 1,1,5,5,7 };
values.sort(); 
values.unique();

Note that we use the sort() function because the unique() function only erase element that are next to each other.

Also if you want to use your class in here it must contain operator <=> which is in c 20 and above like so:

struct myclass {
    std::strong_ordering operator<=>(myclass& other) {
        return this->x <=> other.x;
    }

    int x;
};
  • Related