如何将独特的项目为载体？(How to insert unique items into vecto

我有一种称为Neighbors ：

typedef vector<pair<data,int>> Neighbors;

和这里的data ：

struct data
{
    int par[PARAMETERS];
    int cluster;
    bool visited;
    bool noise;
};

我想写插入值从一个函数_NeighborPts到NeighborPts （但只有那些已经不在NeighborPts ）：

void insert_unique(Neighbors* NeighborPts, const Neighbors& _NeighborPts)
{
    Neighbors_const_it _it = _NeighborPts.begin();
    while(_it != _NeighborPts.end())
    {
        if(/* _it->first.par isn't in *NeighborPts */)
            NeighborPts->push_back(*_it);
        ++_it;
    }
}

和我已经有一个函数equal()其检查如果2 par s为相等。

那么，我必须通过迭代NeighborPts在while循环和检查，如果该项目被发现？或可我使用一些内置的find或find_if函数来为我做的？

Answer 1:

您可以维护一个排序向量。使用lower_bound从C ++函数算法每次找到插入位置。如果在插入位置的元素等于插入元素那么你有一个重复。

除非矢量变得太大的这一性能将是相当不错的。点上，你已经开使用一组更好或unordered_set变化，你需要基准来找到它。

Answer 2:

您当前的与载体溶液将为O运行（N ^ 2）的时间，这是效率不高。为了有效解决关联容器将是巨大的 - 比如std ::集。你还需要有一定的“操作少”（而不是“等于（）”），传递给函数。

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

所以，你需要提供比较类

struct data_compare {
    bool operator() (const data& lhs, const data& rhs) const{
      //...
    }
};

set<int64_t, data_compare> exising_items;

你可能在结构数据限定这样的功能，或覆盖“操作符<”。

插入从 “_NeighborPts” 所有 “数据” 为一组 - O（N *日志（N））的时间

的std ::集other_items; 在一个循环 - 循环_NeighborPts和插入数据元素

other_items.insert (_NeighborPts [i]);

的std ::集my_items; 在一个循环 - 循环_NeighborPts和插入数据元素

my_items.insert (NeighborPts [i]);

现在，你需要在2套之间进行比较：你可以用它做的std :: set_intersection 。或构建体所设置的“my_items”如果在other_items当前元素不在_my_items一个简单的循环，在“NeighborPts”插入

这种解决方案将在Ö运行（n日志（N））的时间

Answer 3:

没有避过迭代中的项目_NeighborPts 。
只要您使用std::vector ，没有周围的检查得到确定项目是否在NeighborPts在其插入之前。

您可以使代码更容易些通过阅读std::for_each和仿函数。

struct UniqueItemInserter
{
   UniqueItemInserter(Neighbors* neighborsIn) : neighbors(neighborsIn) {}

   void operator(pair<data,int> const& item)
   {
     if ( std::find(neighbors->begin(), neighbors->end(), item) != neighbors->end() )
     {
        neighbors->push_back(item);
     }
   }

   Neighbors* neighbors;
};

void insert_unique(Neighbors* NeighborPts, const Neighbors& _NeighborPts)
{
    std::for_each(_NeighborPts.begin(), _NeighborPts.end(), UniqueItemInserter(NeighborPts));
}

文章来源: How to insert unique items into vector?