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

user9GnG 0
Viewed 108

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());
}

Basically what I want is -
Input1 - [A, A, B, B, D, A], impObj = 5
Output1 - [A, B, D, A] impObj = 3

Input2 - [A, B, B, B, A, A, C], impObj = 2
Output2 - [A, B, A, C] impObj = 1

Use of std::unique is not mandatory, we can use any other way also.

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

unique stl algorithm c++
2 Answers

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
Marek R0

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;
};
Feniks0
Related