通过 find_if() 或迭代器之外的键访问成对向量中的元素
Access an element in a vector of pairs by a key besides find_if() or iterators
所以我有一个对向量,它包含另一个这样写的对向量(与 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 ...)
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-data结构很繁琐。您可能应该重新考虑数据结构要求,并且应该想出一些更轻的东西。其次,您的访问方式没有问题。这是正确的。 SEE THIS
您可能提供了错误的密钥(key1
和 key2
)来访问矢量内容。需要注意的一件事是,您引入的密钥对不会按预期工作,因为 std::vector
不是 std::map
.
当您执行 MyWords[key1]. and rest.....
时,例如 Key1 = 0
,您正在访问向量 MyWords
的第一个元素,其中第一个 int
可以是任何值.(不一定 0
,正如您提到的那样,您有一个未排序的向量)。我认为您假设这会发生并尝试一些大于 MyWords.size()
.
的值
您的问题的解决方案是使用 iterator based looping/ accessing,它只会显示您在里面得到的内容,或者坚持使用 std::find_if
,因为它会 return 向量迭代器的结尾,以防在里面找不到键。
#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
迭代器之间的距离最多线性 ,根据 predicate
您提供,它将搜索每个元素,直到找到匹配项。
作为替代方案,您可以将 std::lower_bound
与自定义 lambda/ 谓词一起使用(仅在找到匹配项时 return,否则它也会 return 指向指向的迭代器向量中的下一个更大 元素,如果可用)根据第一个值(键)对 MyWords
向量排序后。 std::lower_bound
只有O(longn)的时间复杂度,会比std::find_if
快很多。
所以我有一个对向量,它包含另一个这样写的对向量(与 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 ...)
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-data结构很繁琐。您可能应该重新考虑数据结构要求,并且应该想出一些更轻的东西。其次,您的访问方式没有问题。这是正确的。 SEE THIS
您可能提供了错误的密钥(key1
和 key2
)来访问矢量内容。需要注意的一件事是,您引入的密钥对不会按预期工作,因为 std::vector
不是 std::map
.
当您执行 MyWords[key1]. and rest.....
时,例如 Key1 = 0
,您正在访问向量 MyWords
的第一个元素,其中第一个 int
可以是任何值.(不一定 0
,正如您提到的那样,您有一个未排序的向量)。我认为您假设这会发生并尝试一些大于 MyWords.size()
.
您的问题的解决方案是使用 iterator based looping/ accessing,它只会显示您在里面得到的内容,或者坚持使用 std::find_if
,因为它会 return 向量迭代器的结尾,以防在里面找不到键。
#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
迭代器之间的距离最多线性 ,根据 predicate
您提供,它将搜索每个元素,直到找到匹配项。
作为替代方案,您可以将 std::lower_bound
与自定义 lambda/ 谓词一起使用(仅在找到匹配项时 return,否则它也会 return 指向指向的迭代器向量中的下一个更大 元素,如果可用)根据第一个值(键)对 MyWords
向量排序后。 std::lower_bound
只有O(longn)的时间复杂度,会比std::find_if
快很多。