Стереть по значению в векторе общих указателей

Question

Я хочу стереть по значению из вектора общего ptr строки (т.е. vector<shared_ptr<string>>).Есть ли эффективный способ сделать это вместо итерации полного вектора, а затем стереть с позиций итератора.

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

Также я не хочу использовать память для карты (значение против адреса).

Answer 1

Нет лучшего способа, чем O(N) - вам нужно найти объект в векторе, и вам нужно один раз повторить вектор, чтобы найти его.В действительности не имеет значения, является ли это указателем или каким-либо объектом.

Единственный способ добиться большего успеха - это использовать другую структуру данных, которая обеспечивает O(1) поиск / удаление.set - это первое, что приходит на ум, но это указывает на то, что ваши указатели уникальны.Вторым вариантом будет карта, такая, что несколько указателей, указывающих на одно и то же значение, существуют в одном хеш-ключе.

Если вы не хотите использовать другую структуру, вам не повезло.Вы можете иметь дополнительную структуру, хэширующую указатели, если вы хотите сохранить вектор, но также имеете доступ O(1).

Например, если вы используете набор и задаете правильный ключ - hasher или key_equal.вероятно, hasher достаточно определить как хеш для *elementInSet, поэтому каждый указатель должен указывать на отдельную строку, например:

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

, чтобы ваш набор был:

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

Тогда стирание будет O(1) просто как:

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

Тем не менее, если вам нужно использовать вектор, то более логичный способ сделать это - использовать remove_if вместоитерирование себя - это не улучшит сложность времени, а только улучшит практику.

Answer 2

Не включайте биты / stdc ++. H, и, поскольку вы перебираете вектор дырок, вы должны использовать std :: for_each с лямбдой.

Answer 3

Попробуйте вот так ( Стереть-Удалить идиома ):

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