这个向量以前出现过吗

Question

我有很多向量（大约 10^4，甚至更多！）而且我将从流的输入中获得更多向量。所以，例如，我有

v1 = 1 0 4 1 1
v2 = 1 1 2 5 3 6 2
v3 = 0 1 1 5 0

我有 10^4 个这样的向量现在，我输入一个向量 v4 = 0 1 1 5 0，我想检查它之前是否出现过，你建议我怎么做？

我会列出我想到的技巧，以及伴随它们出现的错误：

使用std::map，或std::set。但是，std::map std::set 不支持向量作为参数。
要将向量中的每个整数转换为字符串类型，请按顺序附加它们并将字符串存储在映射中。错误：v5 = 11 1 1 1 和 v6 = 1 1 1 1 1 的大小写将显示为相同。
同上，只是在每个整数后面加一个分隔符。错误：编码太繁琐？

我想知道你是否可以想出一些方法来实现这个？

编辑：对于 10^4，这是可以实现的。我的新任务要求我最多存储 10^9。我个人认为STL没有那么多space，他们抛出了SIGABRT错误。你知道在这种情况下可以使用的任何其他有效的哈希方法吗？

Answer 1

这是非常初学者的方法，但我正在尝试使用我从折叠和 stl 中学到的东西

方法说明：

1.Created 一个向量列表（输入目的可以随便）

2.Kept一个主向量v，它将存储主折叠向量

3.used stl 包括在折叠之前继续检查序列是否存在

输入集

std::vector<int> x ={1,2,3};
std::vector<int> y ={7,8,9};
std::vector<int> z ={1,2,3};
std::vector<int> a ={1,2,3};  
std::vector<int> v5 = {11,1,1,1}; //as mentioned in question
std::vector<int> v6 = {1,1,1,1};  //as mentioned in question

方法

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

template <typename T>
void Concat(std::vector<T>& v, const std::vector<T>& v2)
{
    v.insert(v.end(), v2.begin(), v2.end());
}

template <typename T>
void Concat(std::vector<T>& v, const T& value)
{
    v.push_back(value);
}

template<typename T, typename... Args>
void push_back_vec(std::vector<T>& v, Args&&... args)
{
    (Concat(v, args), ...);
}
int main()
{
    std::vector<int> v;
    std::list<std::vector<int> > m ;
    std::vector<int> x ={1,2,3};
    std::vector<int> y ={7,8,9};
    std::vector<int> z ={1,2,3};
    std::vector<int> a ={1,2,3};
    std::vector<int> v5 = {11,1,1,1};
    std::vector<int> v6 = {1,1,1,1};
    m.push_back(x);
    m.push_back(y);
    m.push_back(z);
    m.push_back(a);
    m.push_back(v5);
    m.push_back(v6);

    for (std::list<std::vector<int> >::iterator it1 = m.begin(); it1 != m.end(); ++it1)
    {


        if (std::includes(v.begin(), v.end(), (*it1).begin(), (*it1).end()))
        {
            std::cout<<"Already present"<<std::endl;
            }
        else
            {
            push_back_vec(v,(*it1));

            }
    }

    for (int i : v) std::cout << i << ' ';

}

输出

Already present
Already present
1 2 3 7 8 9 11 1 1 1 1 1 1 1 Program ended with exit code: 0

我知道可以有很多改进，在某些极端情况下可能会失败。这只是其中一种尝试，欢迎批评并帮助我改进

Answer 2

如果您在向量上定义了一个完整的顺序，您可以通过两种方式进行相当有效的查找：

将现有向量存储在 std::set 或 std::map 中。这些是有序容器类，具有合理有效的 membership/lookup 方法。
将现有向量按排序顺序存储在 std::vector 中，并使用 std::binary_search

对载体进行排序的默认选择是字典顺序。这是由 std::vector 实现提供的 operator< 提供的；它实际上做的是这样的：

bool operator<(const std::vector<int> &a, const std::vector<int> &b) {
  auto a_it = a.cbegin();
  auto b_it = b.cbegin();
  while(a_it < a.cend() && b_it < b.cend()) {
    if(*a_it < *b_it) {
      return true;
    }
    if(*b_it < *a_it) {
      return false;
    }
    ++a_it;
    ++b_it;
  }
  if(a_it == a.cend() && b_it < b.cend()) {
    return true;
  }
  return false;
}

请注意，此代码可以提前退出：如果输入向量的第一个元素不同，则不需要进一步检查。只有当有一个长公共前缀（或者如果向量实际上相同）时才需要检查所有元素。

如评论中所述，您还可以通过以下方式解决此问题：

哈希映射 (std::unordered_map) -- 要求您为 std::vector<int>
a trie -- AFAIK 没有 std:: 实现，您需要找到一个库或自己滚动

Answer 3

执行此操作的简单方法是将您的向量存储在另一个向量中，并使用 std::lexigraphical_compare 作为排序谓词，使用 std::sort() 函数族维护该向量的顺序。这将允许在 O(log(n)) 摊销时间内对列表进行二进制搜索，代价是半成本排序操作的代价，这可能可以通过玩一些堆化或划分向量列表的游戏来减少你加载它。

然而，比这更有效的是将您的向量存储为一个特里树 (https://en.wikipedia.org/wiki/Trie)，其中特里树中的每条路径都存储一个来自您的向量的唯一序列。根据数据的差异，这可能 space 效率更高，加法和搜索都是 O(log(n)) 操作。

请对我的建议持保留态度，但是，10^4 个元素实际上是一个很小的数字。我的经验是，当您的数据集处于 10^6-10^7 范围内时，效率排序和搜索算法的差异实际上只会开始在现代硬件上显现出来。低于这个规模，通常最简单、对缓存最友好的算法会胜出。

如果您只是追求原始速度，并且要扫描的向量列表是众所周知且静态的，另一种选择是使用有限状态机 accept/reject 您的输入。像 Ragel 这样的工具可以快速解决这些问题。

这个向量以前出现过吗

Has this vector occured before

c++

implementation

stl

vector