CODEWITHSUNDEEP
c++c++11stlc++14shared-ptr
Uddhav Mishra
Uddhav Mishra

Reputation: 76

Erase by value in a vector of shared pointers

I want to erase by value from a vector of shared ptr of string (i.e vector<shared_ptr<string>>) . Is there any efficient way of doing this instead of iterating the complete vector and then erasing from the iterator positions.

#include <bits/stdc++.h>
using namespace std;

int main()
{
  vector<shared_ptr<string>> v;
  v.push_back(make_shared<string>("aaa"));
  int j = 0,ind;
  for(auto i : v) {
    if((*i)=="aaa"){
       ind = j;
     }
    j++;
  }
 v.erase(v.begin()+ind);
}

Also I dont want to use memory for a map ( value vs address).

Upvotes: 0

Views: 355

Answers (3)

kabanus
kabanus

Reputation: 25895

There is no better way then O(N) - you have to find the object in a vector, and you have to iterate the vector once to find it. Does not really matter if it is a pointer or any object.

The only way to do better is to use a different data structure, which provides O(1) finding/removal. A set is the first thing that comes to mind, but that would indicate your pointers are unique. A second option would be a map, such that multiple pointers pointing to the same value exist at the same hash key.

If you do not want to use a different structure, then you are out of luck. You could have an additional structure hashing the pointers, if you want to retain the vector but also have O(1) access.

For example if you do use a set, and define a proper key - hasher or key_equal. probably hasher is enough defined as the hash for *elementInSet, so each pointer must point to a distinct string for example:

struct myPtrHash {
    size_t operator()(const std::shared_ptr<std::string>& p) const {
        //Maybe we want to add checks/throw a more meaningful error if p is invalid?
        return std::hash<std::string>()(*p);
    }
};

such that your set is:

std::unordered_set<std::shared_ptr<std::string>,myPtrHash > pointerSet;

Then erasing would be O(1) simply as:

std::shared_ptr<std::string> toErase = make_shared("aaa");
pointerSet.erase(toErase)

That said, if you must use a vector a more idomatic way to do this is to use remove_if instead of iterating yourself - this will not improve time complexity though, just better practice.

Upvotes: 1

snake_style
snake_style

Reputation: 1169

Try like that (Erase-Remove Idiom):

string s = "aaa";
auto cmp = [s](const shared_ptr<string> &p) { return s == *p; };

v.erase(std::remove_if(v.begin(), v.end(), cmp), v.end());

Upvotes: 3

Iris Technologies
Iris Technologies

Reputation: 57

Don't include bits/stdc++.h, and since you're iterating through the hole vector, you should be using std::for_each with a lambda.

Upvotes: -1

Related Questions