Erase by value in a vector of shared pointers

Question

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).

Don't use bits/c++.h and you should probably do something about not finding the string... — Matthieu Brucher, Dec 04 '18 at 09:12
Do you wish to interleave insertions and deletions? Or do all the insertions happen up front, followed only by deletions and lookup? — StoryTeller - Unslander Monica, Dec 04 '18 at 09:20
this might be of interest https://stackoverflow.com/questions/9053883/erase-after-performing-remove-if — Andrew Kashpur, Dec 04 '18 at 09:21

snake_style · Answer 1 · 2018-12-04T09:43:11.420

3

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

edited Dec 04 '18 at 09:43

answered Dec 04 '18 at 09:15

snake_style

1,139
7
16

Indeed, this covers the issue of not finding the string properly. – Matthieu Brucher Dec 04 '18 at 09:28
@MatthieuBrucher That's correct. Iterator passed to erase allowed to be _end()_; – snake_style Dec 04 '18 at 09:38
I will just stress that this idiom is no way more efficient, though it is what you should use for `vectors`. – kabanus Dec 04 '18 at 09:50

kabanus · Answer 2 · 2018-12-04T11:08:51.247

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.

what if i am using unordered_set instead of vector , any efficient way then ? @kabanus — Uddhav Mishra, Dec 04 '18 at 09:26
@UddhavMishra what hash function and equality check you use in that unordered set ? — Piotr Skotnicki, Dec 04 '18 at 09:36

score -1 · Answer 3 · answered Dec 04 '18 at 09:21

-1

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.

answered Dec 04 '18 at 09:21

Iris Technologies

57
5

Erase by value in a vector of shared pointers

3 Answers3