如何用链表替换std::vector?
How to replace std::vector by linked list?
我已经使用 std::vector
来制作我的算法。我想用链表替换向量。
为了做到这一点,我正在考虑使用 std::list
,但我不知道该怎么做,例如我尝试了以下示例来查找 [=24= 中的值]:
void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2)
{
if (input_vector[0] >= value) { // too small
rv1 = 0; rv2 = 0; return;
}
int index = (int)input_vector.size() - 1;
if (input_vector[index] <= value) { // too big
rv1 = index; rv2 = index; return;
}
// somewhere inside
index = 0;
while (input_vector[index] <= value) {
index++;
}
rv1 = index - 1; rv2 = index; return;
}
void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2)
{
if (*input_list.begin() >= value) { // too small
rv1 = 0; rv2 = 0; return;
}
if (*input_list.end() <= value) { // too big
rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return;
}
// somewhere inside
int index = 0; int temp = *input_list.begin();
while (temp <= value) {
temp = *input_list.next(); index++;
}
rv1 = index - 1; rv2 = index; return;
}
这似乎不起作用,因为成员函数 next()
不存在。但是我记得浏览链表是通过从头开始,然后进一步移动到下一个元素直到到达某个点来完成的。我已经看到有一种方法可以通过在 for 循环中使用 interator
来完成此操作,但我想知道我的方法有什么问题?我的印象是 std::list
是双向链表的标准实现,或者我错了,在那种情况下,std
class 是链表的实现list(不一定是双向链表)?
遍历容器的标准方式是这样的:
for(std::list<int>::iterator it = input_list.begin();
it != input_list.end();
it++)
{
....
}
这也适用于矢量、地图、双端队列等。迭代器概念在整个 STL 中始终如一地实现,因此最好习惯这个概念。
对于不同类型的迭代器,还有std::distance
和std::advance
等迭代器操作(我建议您阅读它们及其advantages/limitations)
如果你有可用的 C++ 11,你也可以使用这个语法(虽然可能对你的问题没有用。)
for(const auto& value : input_list)
{
...
}
这也适用于整个 STL 容器。
这应该适用于 vector、list、deque 和 set(假设内容已排序)。
template <class T>
void find_values_in_container(const T& container, int value, int &rv1, int &rv2)
{
rv1 = rv2 = 0; // Initialize
if (container.empty() || container.front() >= value)
{
return;
}
for (const auto& v : container)
{
rv2++;
if (v > value)
{
break;
}
rv1++;
}
return;
}
我已经使用 std::vector
来制作我的算法。我想用链表替换向量。
为了做到这一点,我正在考虑使用 std::list
,但我不知道该怎么做,例如我尝试了以下示例来查找 [=24= 中的值]:
void find_values_in_vector(const std::vector<int>& input_vector, int value, int &rv1, int &rv2)
{
if (input_vector[0] >= value) { // too small
rv1 = 0; rv2 = 0; return;
}
int index = (int)input_vector.size() - 1;
if (input_vector[index] <= value) { // too big
rv1 = index; rv2 = index; return;
}
// somewhere inside
index = 0;
while (input_vector[index] <= value) {
index++;
}
rv1 = index - 1; rv2 = index; return;
}
void find_values_in_list(const std::list<int>& input_list, int value, int &rv1, int &rv2)
{
if (*input_list.begin() >= value) { // too small
rv1 = 0; rv2 = 0; return;
}
if (*input_list.end() <= value) { // too big
rv1 = (int)input_list.size() - 1; rv2 = (int)input_list.size() - 1; return;
}
// somewhere inside
int index = 0; int temp = *input_list.begin();
while (temp <= value) {
temp = *input_list.next(); index++;
}
rv1 = index - 1; rv2 = index; return;
}
这似乎不起作用,因为成员函数 next()
不存在。但是我记得浏览链表是通过从头开始,然后进一步移动到下一个元素直到到达某个点来完成的。我已经看到有一种方法可以通过在 for 循环中使用 interator
来完成此操作,但我想知道我的方法有什么问题?我的印象是 std::list
是双向链表的标准实现,或者我错了,在那种情况下,std
class 是链表的实现list(不一定是双向链表)?
遍历容器的标准方式是这样的:
for(std::list<int>::iterator it = input_list.begin();
it != input_list.end();
it++)
{
....
}
这也适用于矢量、地图、双端队列等。迭代器概念在整个 STL 中始终如一地实现,因此最好习惯这个概念。
对于不同类型的迭代器,还有std::distance
和std::advance
等迭代器操作(我建议您阅读它们及其advantages/limitations)
如果你有可用的 C++ 11,你也可以使用这个语法(虽然可能对你的问题没有用。)
for(const auto& value : input_list)
{
...
}
这也适用于整个 STL 容器。
这应该适用于 vector、list、deque 和 set(假设内容已排序)。
template <class T>
void find_values_in_container(const T& container, int value, int &rv1, int &rv2)
{
rv1 = rv2 = 0; // Initialize
if (container.empty() || container.front() >= value)
{
return;
}
for (const auto& v : container)
{
rv2++;
if (v > value)
{
break;
}
rv1++;
}
return;
}