Доступ к элементу в векторе пар по ключу кроме find_if () или итераторов - PullRequest
Новая
       33

Доступ к элементу в векторе пар по ключу кроме find_if () или итераторов

0 голосов
/ 10 июня 2018

Итак, у меня есть вектор пар, который содержит еще один вектор пар, записанный следующим образом (такой же, как 2D-вектор, но '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 и set, но в настоящее время я пытаюсь сделать это с вектором.

Кстати, я также хотел бы спросить, какова временная сложность find_if ()?

Редактировать: ключи пар могут не быть последовательными (0,1,2,3 ...)

1 Ответ

0 голосов
/ 10 июня 2018

Я пытаюсь получить доступ к элементу, используя ключи, такие как индекс.К сожалению, я всегда получаю ошибку сегментации.

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

Есть еще идеи?

Прежде всего, утомительно создавать такую ​​структуру векторных данных.Вероятно, вам следует переосмыслить требования к структуре данных и придумать что-то более легкое.Во-вторых, нет ничего плохого в вашем способе доступа.Это правильно. СМОТРИТЕ

Возможно, вы предоставляете неправильные ключи (key1 и key2) для доступа к векторному контенту.Следует отметить, что введенная вами пара ключей не будет работать должным образом, поскольку std::vector не является std::map.

Когда вы делаете MyWords[key1]. and rest....., например, Key1 = 0, выполучают доступ к первому элементу вектора MyWords, где первый int может иметь любое значение (не обязательно 0, как вы упоминали, у вас есть несортированный вектор).Я думаю, что вы предполагаете, что это произойдет, и пытаетесь использовать некоторые значения, превышающие MyWords.size().

. Решение вашей проблемы состоит в том, чтобы либо использовать циклический вывод / доступ к , который будет показывать только то, что у вас внутри, или придерживаться std::find_if, так как он вернет конец векторного итератора, в случае, если ключ не найден внутри. 

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

Я бытакже хотел бы спросить, какова временная сложность find_if ()?

std::find_if может иметь временную сложность, от до линейного на расстояниимежду first и last итератором, согласно предоставленному вами predicate, который будет искать каждый элемент, пока не будет найдено совпадение.

В качестве альтернативного натива вы можете использовать std::lower_bound с пользовательским лямбда / предикатом (возвращает только при обнаружении совпадения, в противном случае он также возвращает итератор, указывающий на следующий больший элемент в векторе, если он доступен) после сортировки вектор MyWords в соответствии спервое значение (ключ).std::lower_bound имеет только временную сложность O (longn) , что будет намного быстрее, чем std::find_if.

...