c++ - 除了 find_if() 或迭代器之外，还可以通过键访问对 vector 中的元素

Question

所以我有一个对 vector ，其中包含另一个像这样编写的对 vector (与 2D vector 相同，但“int”有点像元素的键):

struct Item
{
    string word = "";
    int count[3] = {0, 0, 0};
};

vector< pair<int, vector< pair<int, Item> > > > MyWords;

目前，在给定两个整数键的情况下，我访问唯一元素的方式如下:

//Find the pair with a key == key1 in the main vector
auto it1 = find_if(MyWords.begin(), MyWords.end(), 
           [](const pair<int, vector<pair<int, Item> > >& element){
               return element.first == key1;
           });

//Find the pair with a key == key2 in the vector that has a key == key1
auto it2 = find_if(it1 -> second.begin(), it1 -> second.end(),
           [](const pair<int, Item>& element){
               return element.first == key2;
           });

//Access the element using the returned iterator
it2 -> second.count[0] = A_Number_Here;

我正在尝试找到一种更好的方法来访问元素，例如使用像索引一样的键(键从 0 开始)。不幸的是，使用 [] 结果导致段错误:

MyWords[key1].second[key2].second.count[0] = A_Number_Here;

还有其他想法吗？我知道还有其他 STL 容器，例如 map 和集合，但我目前正在尝试使用 vector 来实现。

顺便问一下，find_if()的时间复杂度是多少？

编辑:键对可能不连续(0,1,2,3 ...)

Answer 1

I'm trying to access an element by using the keys like an index. Unfortunately, I always receive a segmentation fault.

MyWords[key1].second[key2].second.count[0] = A_Number_Here;

Any other ideas?

首先，做这样的 vector 数据结构很乏味。您可能应该重新考虑数据结构要求，并应该提出更简单的东西。其次，您的访问方式没有问题。这是正确的。 <强> SEE THIS

您可能提供了错误的 key (key1 和 key2)来访问 vector 内容。需要注意的一件事是，您引入的 key 对将无法按预期工作，因为 std::vector 不是 std::map。

当您执行MyWords[key1]时。剩下的......，例如Key1 = 0，您正在访问 vector MyWords的第一个元素，其中第一个 int 可以是任何值。(不一定是 0，正如您提到的，您有一个未排序的 vector )。我认为您假设会发生这种情况并尝试一些大于 MyWords.size() 的值。

解决您的问题的方法是使用 iterator based looping/ accessing ，它只会显示你里面的内容，或者坚持使用 std::find_if，因为它会返回 vector 迭代器的末尾，以防在里面找不到键。

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

struct Item
{
   std::string word;
   std::vector<int> count; // changed to vector array
};
using Pair = std::pair<int, std::vector< std::pair<int, Item> > >;

int main()
{
   std::vector< Pair > MyWords =
   {  //int, <std::pair<int,          Item            > > >
      {1   , {        {    4,  Item{"String1", {1,2,3}} } }       },
      {0   , {        {    5,  Item{"String2", {5,2,8}} } }       },
      {2   , {        {    8,  Item{"String3", {1,7,9}} }, {    9,  Item{"String4", {11,77,99}} } }       }
   };

   for(const auto& bigPair: MyWords)
   {
      std::cout << "Key : " << bigPair.first;

      for(const auto& smallPair: bigPair.second)
      {
         std::cout << "\nValues: " << smallPair.first << "\t";

         std::cout << smallPair.second.word << " "
                  << smallPair.second.count[0] << " "
                  << smallPair.second.count[1] << " "
                  << smallPair.second.count[2] ;
      }
      std::cout << "\n\n";
   }

   return 0;
}

I would also like to ask what is the time complexity of find_if()?

std::find_if根据谓词，时间复杂度可以达到first和last迭代器之间的距离线性您提供的内容将搜索每个元素，直到找到匹配项。

作为替代者，您可以使用 std::lower_bound使用自定义 lambda/谓词(仅在找到匹配项时返回，否则它还将返回指向 vector 中下一个更大元素的迭代器(如果有))排序后 根据第一个值(键)的 MyWords vector 。 std::lower_bound 的时间复杂度仅为 O(longn)，这比 std::find_if 快得多。