这个矢量是否发生在

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没有那么多空间，他们抛出SIGABRT错误。你知道任何其他有效的哈希方法可以在这种情况下工作吗？

Answer 1

这样做的简单方法是将你的向量存储在另一个向量中，并使用std :: sort（）函数族来维护它的顺序，使用std :: lexigraphical_compare作为排序谓词。这将允许二进制为O搜索列表中（日志（n））的分期时间，在昂贵的半昂贵的排序操作，这或许可以通过玩一些游戏与heapifying或分区的列表的向量可以减少你加载它。

比这更有效的，但是，是你的矢量存储为字典树（https://en.wikipedia.org/wiki/Trie），其中向下的字典树的每个路径存储从您的载体的独特序列。根据数据的差异，这可以更节省空间，并且添加和搜索都是O（log（n））操作。

听我的劝告与一粒盐，但是，10^4的元素其实是一个很小的数字。我的经验是，在效率排序&搜索算法的差别真的只是开始展现自己在现代硬件上，当你在10^6-10^7范围内为您的数据集是。在这个尺度下，最简单的，最容易缓存的算法胜出。

另一种选择，如果你只是对原材料的速度，和你的载体清单扫描是众所周知的，静态的，是用一个有限状态机来接受/拒绝您的输入。像Ragel这样的工具可以解决这些问题。

Answer 2

这是非常begineer的做法，但我想用我从折叠和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 3

如果你定义了你的矢量一个完整的订购之一，你可以做一个合理有效的查找方法有两种：

• 存储中的现有向量在std::set或std::map。这些是有序的容器类，具有合理有效的成员资格/查找方法。
• 存放在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>
• 一个线索 - 其中AFAIK没有std::实施，你需要追踪一个图书馆或滚动你自己