【C++】-List经典面试笔试题总结-删除-插入-情况-合并-排序等经典操作

devtools/2024/10/16 2:30:36/

在C++中，list 容器是标准模板库（STL）中的一种双向链表容器。以下是一些关于 list 的经典笔试面试题及解答：

list__1">1. list 容器的主要特点是什么？

解答：
list 容器的主要特点包括：

  • 它是一个双向链表结构，每个元素都有两个指针，分别指向前一个和后一个元素。
  • 插入和删除操作的时间复杂度为 O(1)，因为这些操作只需要改变指针。
  • 不支持随机访问，访问元素需要从头开始遍历，时间复杂度为 O(n)。
  • 元素在 list 中保持插入顺序。

list__8">2. list 容器有哪些常用的成员函数？

解答：
list 容器的常用成员函数包括：

  • push_front()：在列表前端插入元素。
  • push_back()：在列表后端插入元素。
  • pop_front()：删除列表前端元素。
  • pop_back()：删除列表后端元素。
  • insert()：在指定位置插入元素。
  • erase()：删除指定位置的元素。
  • remove()：删除所有匹配特定条件的元素。
  • reverse()：反转列表中元素的顺序。
  • sort()：对列表中的元素进行排序。
  • clear()：清除列表中的所有元素。
  • empty()：检查列表是否为空。
  • size()：获取列表中元素的数量。

list__23">3. 如何反转一个 list 容器中的元素顺序？

解答：
要反转 list 容器中的元素顺序，可以使用 reverse() 成员函数：

#include <iostream>
#include <list>
#include <algorithm>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.reverse();// 现在 myList 的顺序是 5, 4, 3, 2, 1return 0;
}

或者，也可以使用 std::rotate() 函数或 std::reverse_iterator 来反转。

list__38">4. list 容器能否进行随机访问？为什么？

解答：
list 容器不能进行随机访问。在 list 中，元素不是连续存储的，因此没有固定的索引。要访问 list 中的元素，必须从头节点开始遍历，这样的访问方式时间复杂度为 O(n)，这与数组或向量等容器不同，它们可以随机访问元素，时间复杂度为 O(1)。

list__41">5. 在 list 容器中删除元素时，有哪些情况需要注意？

解答：
在 list 容器中删除元素时，需要注意以下几点：

  • 如果删除的是列表的第一个元素，需要处理特殊情况，比如使用 pop_front() 函数。
  • 如果删除的是最后一个元素，需要使用 pop_back() 函数。
  • 如果删除的是列表中间的元素，那么需要更新前一个元素和后一个元素的指针，以保持链表的连续性。
  • 当删除一个元素后，若该元素是列表中唯一的元素，那么需要特别注意列表的 empty() 和 size() 函数的返回值。

list__48">6. 如何清空一个 list 容器？

解答：
清空 list 容器有多种方式：

  • 使用 clear() 成员函数：
    myList.clear();
  • 也可以遍历列表并逐个删除元素：
    for (auto it = myList.begin(); it != myList.end(); ++it) {myList.erase(it);
}

list__62">7. list 容器中插入元素时，如果指定的位置已经存在元素，应该如何处理？

解答：
在 list 容器中插入元素时，如果指定的位置已经存在元素，新插入的元素会覆盖原来位置上的元素。例如：

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.insert(myList.begin() + 2, 100); // 在位置2插入元素100// myList 变为 1, 2, 100, 3, 4, 5return 0;
}

list__75">8. list 容器有哪些缺点？

解答：
list 容器的主要缺点包括：

  • 不支持快速随机访问，访问元素需要从头开始遍历。
  • 插入和删除操作虽然快，但是不能在中间位置插入或删除，只能在一端操作。
  • 不能直接通过下标访问或修改元素，需要使用迭代器。
  • 相对于其他STL容器如 vector 和 map，list 的使用场景较为有限。

list__82">9. 如何在一个已排序的 list 容器中插入一个新元素，以保持排序？

解答：
要在一个已排序的 list 容器中插入一个新元素以保持排序，可以使用 insert() 函数和 std::list::sort() 函数。首先，使用 insert() 函数在适当的位置插入新元素，然后调用 sort() 函数重新排序列表：

#include <iostream>
#include <list>
#include <algorithm>
int main() {std::list<int> myList{1, 3, 5, 7, 9};myList.insert(myList.begin() + 2, 4); // 在位置2插入元素4myList.sort(); // 排序，现在 myList 为 1, 3, 4, 5, 7, 9return 0;
}

list__vector__96">10. list 容器与 vector 容器的主要区别是什么？

解答：
list 容器与 vector 容器的主要区别包括：

  • list 是双向链表，而 vector 是连续存储的数组。
  • list 不支持随机访问，而 vector 支持随机访问。
  • list 的插入和删除操作在一般情况下更高效（O(1)），但在某些情况下（如在中间位置插入或删除）效率较低。
  • vector 的内存分配方式使得其在动态扩展时相对高效，而 list 的元素需要单独的节点内存。

list__104">11. 在 list 容器中，如何快速找到指定元素的下一个元素？

解答：
在 list 容器中，要快速找到指定元素的下一个元素，可以使用迭代器。首先，通过迭代器找到要查找的元素，然后使用 std::next 函数或箭头操作符 -> 获取下一个元素的迭代器。例如：

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};std::list<int>::iterator it = myList.begin();it++; // 指向第二个元素it++; // 指向第三个元素// 现在 it 指向第三个元素return 0;
}

list__119">12. list 容器中删除元素时，如何避免删除错误的元素？

解答：
在 list 容器中删除元素时，要避免删除错误的元素，可以先找到要删除的元素，然后使用 erase() 函数删除。例如：

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};std::list<int>::iterator it = myList.begin();it++; // 指向第二个元素myList.erase(it); // 删除第二个元素// 现在 myList 为 1, 3, 4, 5return 0;
}

list__134">13. 如何在一个 list 容器中删除所有值为特定值的元素？

解答：
要在一个 list 容器中删除所有值为特定值的元素，可以使用 remove_if() 函数。例如：

#include <iostream>
#include <list>
#include <algorithm>
int main() {std::list<int> myList{1, 2, 3, 4, 5, 3};myList.remove_if([](int x) { return x == 3; });// 现在 myList 为 1, 2, 4, 5return 0;
}

list__148">14. 如何反转 list 容器中的元素顺序，不使用库函数？

解答：
要反转 list 容器中的元素顺序，不使用库函数，可以使用迭代器手动交换每对相邻元素的位置。

#include <iostream>
#include <list>
void reverseList(std::list<int>& myList) {std::list<int>::iterator it1 = myList.begin();std::list<int>::iterator it2 = myList.end();while (it1 != it2) {std::iter_swap(it1, --it2);++it1;}
}
int main() {std::list<int> myList{1, 2, 3, 4, 5};reverseList(myList);// 现在 myList 的顺序是 5, 4, 3, 2, 1return 0;
}

list__169">15. 在 list 容器中，如何删除所有重复的元素？

解答：
在 list 容器中删除所有重复的元素，可以使用 std::unique() 函数和 std::sort() 函数。首先使用 std::sort() 函数排序列表，然后使用 std::unique() 函数删除重复的元素。

#include <iostream>
#include <list>
#include <algorithm>
int main() {std::list<int> myList{1, 2, 3, 4, 4, 5, 5};myList.sort();myList.unique();// 现在 myList 的顺序是 1, 2, 3, 4, 5return 0;
}

list__184">16. 如何合并两个 list 容器？

解答：
合并两个 list 容器，可以使用 std::merge() 函数。首先将两个列表排序，然后使用 std::merge() 函数将它们合并。

#include <iostream>
#include <list>
#include <algorithm>
int main() {std::list<int> list1{1, 3, 5};std::list<int> list2{2, 4, 6};list1.sort();list2.sort();std::list<int> mergedList(std::merge(list1, list2));// 现在 mergedList 的顺序是 1, 2, 3, 4, 5, 6return 0;
}

list__201">17. 如何清空一个 list 容器，同时保持其迭代器有效性？

解答：
要清空一个 list 容器，同时保持其迭代器有效性，可以使用 clear() 函数。这会删除所有元素，但不会改变容器的大小，因此迭代器仍然有效。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.clear();// myList 现在是空的，但迭代器仍然有效return 0;
}

list__214">18. 如何反转 list 容器中的元素顺序，同时保持其迭代器有效性？

解答：
要反转 list 容器中的元素顺序，同时保持其迭代器有效性，可以使用 reverse() 函数。这会交换每对相邻元素的位置，但不会改变迭代器的有效性。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.reverse();// 现在 myList 的顺序是 5, 4, 3, 2, 1，迭代器仍然有效return 0;
}

list__227">19. 在 list 容器中，如何插入元素到特定位置？

解答：
在 list 容器中，你可以使用 insert() 函数来插入元素到特定位置。这个函数接受两个参数：第一个参数是一个迭代器，表示你想要插入元素的位置；第二个参数是要插入的元素。如果插入位置已经存在元素，新元素将会覆盖那个位置上的元素。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.insert(myList.begin(), 0); // 在列表开始处插入元素0myList.insert(++myList.begin(), 200); // 在第二个元素之前插入元素200myList.insert(myList.end(), 6); // 在列表末尾插入元素6// 现在 myList 的顺序是 1, 2, 200, 3, 4, 5, 6return 0;
}

list__using__242">20. 在 list 容器中，如何删除元素 using 迭代器？

解答：
在 list 容器中，你可以使用 erase() 函数来删除元素。这个函数接受一个迭代器，表示你想要删除的元素的位置。删除操作之后，迭代器将指向下一个有效的元素。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};std::list<int>::iterator it = myList.begin();it++; // 指向第二个元素myList.erase(it); // 删除第二个元素// 现在 myList 的顺序是 1, 3, 4, 5return 0;
}

list__257">21. 如何在一个已排序的 list 容器中插入一个新元素，同时保持排序？

解答：
要在一个已排序的 list 容器中插入一个新元素同时保持排序，可以使用 emplace() 函数。这个函数直接在指定的位置创建并插入元素，避免了复制或移动元素，因此在插入大量元素时更为高效。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 3, 5, 7, 9};myList.emplace(myList.begin() + 2, 4); // 在第三个元素的位置插入元素4// 现在 myList 的顺序是 1, 3, 4, 5, 7, 9return 0;
}

list__using__270">22. 如何遍历 list 容器 using 迭代器？

解答：
遍历 list 容器 using 迭代器非常直接。你可以使用标准迭代器来逐个访问容器中的元素。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};for (std::list<int>::iterator it = myList.begin(); it != myList.end(); ++it) {std::cout << *it << " ";}// 输出： 1 2 3 4 5return 0;
}

list__285">23. 如何反转 list 容器中的元素顺序，同时保持其迭代器有效性？

解答：
要反转 list 容器中的元素顺序，同时保持其迭代器有效性，可以使用 reverse() 函数。这个函数会修改容器中的元素顺序，但不会影响迭代器的有效性。

#include <iostream>
#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};myList.reverse();// 现在 myList 的顺序是 5, 4, 3, 2, 1，迭代器仍然有效return 0;
}

list__298">24. list 容器如何进行插入操作？

解答：
在 list 容器中插入元素有多种方式：

  1. 在容器开始处插入：insert(const T& elem)，insert(const T& elem, const T& hint)
  2. 在指定位置插入：insert(const_iterator position, const T& elem)
  3. 插入多个元素：insert(const_iterator position, const T* first, const T* last)
  4. 插入范围：insert(const_iterator position, InputIt first, InputIt last)
    例如，要在列表的开始处插入一个元素，可以使用 insert(begin(), elem)。要在特定位置插入元素，可以使用 insert(position, elem)，其中 position 是一个指向列表中当前位置的迭代器。

list__306">25. list 容器如何进行删除操作？

解答：
在 list 容器中删除元素也有多种方式：

  1. 删除指定元素：erase(const_iterator position)
  2. 删除指定元素（通过值）：erase(const T& elem)
  3. 删除范围：erase(const_iterator first, const_iterator last)
    例如，要删除一个特定位置的元素，可以使用 erase(position)，其中 position 是一个指向要删除元素的迭代器。要删除所有值为特定值的元素，可以使用 remove(elem) 或 remove_if(pred)，其中 pred 是一个符合 std::remove_if_t 或 std::predicate 类型的函数对象或函数指针。

list__313">26. list 容器如何进行排序操作？

解答：
list 容器不保证元素的自然顺序，但你可以使用 sort() 函数对其进行排序。要排序 list，可以使用 sort(comp)，其中 comp 是一个符合 std::less 或 std::greater 类型的比较函数。

#include <algorithm>
#include <list>
int main() {std::list<int> myList{3, 1, 4, 1, 5, 9};myList.sort(); // 使用默认比较器// 现在 myList 的顺序是 1, 1, 3, 4, 5, 9return 0;
}

list__326">27. list 容器如何进行合并操作？

解答：
要合并两个 list 容器，可以使用 merge() 函数。这个函数将一个列表中的元素合并到另一个已排序的列表中。

#include <algorithm>
#include <list>
int main() {std::list<int> list1{1, 3, 5};std::list<int> list2{2, 4, 6};list1.sort();list2.sort();list1.merge(list2);// 现在 list1 的顺序是 1, 2, 3, 4, 5, 6return 0;
}

list__342">28. list 容器如何进行旋转操作？

解答：
在 list 容器中，旋转操作可以将列表中的元素围绕一个指定的元素进行旋转。这可以通过交换元素来实现，但需要注意的是，旋转操作不一定会保持列表的排序。

#include <list>
void rotateList(std::list<int>& myList, int pos) {if (pos <= 0) return;auto it = myList.begin();std::advance(it, pos);myList.splice(myList.begin(), myList, it);
}
int main() {std::list<int> myList{1, 2, 3, 4, 5};rotateList(myList, 2); // 将列表旋转2个位置// 现在 myList 的顺序是 4, 5, 1, 2, 3return 0;
}

list__360">29. list 容器如何进行拆分操作？

解答：
在 list 容器中，拆分操作通常指的是将一个列表分割成两个或多个列表。这可以通过使用 split() 函数来实现，该函数接受一个迭代器作为分隔点，并将列表拆分为两部分。

#include <algorithm>
#include <list>
void splitList(std::list<int>& myList, const std::list<int>::const_iterator& pos) {auto second_half = std::make_unique<std::list<int>>(myList.begin(), pos);myList.erase(myList.begin(), pos);myList.splice(myList.end(), *second_half);
}
int main() {std::list<int> myList{1, 2, 3, 4, 5};auto it = myList.begin();std::advance(it, 2); // 选择第三个元素作为分隔点splitList(myList, it);// 现在 myList 包含前两个元素：1, 2// second_half 包含后三个元素：3, 4, 5return 0;
}

list__vector__381">30. list 容器与 vector 容器的主要区别是什么？

解答：
list 容器和 vector 容器都是顺序容器，但它们在实现和性能上有一些关键区别：

  1. 内存分配：vector 使用连续的内存块，这使得访问元素非常快，只需常数时间 O(1)。而 list 使用双向链表结构，每个元素都需要额外的空间来存储到下一个和前一个元素的链接，这影响了元素的访问速度，访问通常需要线性时间 O(n)。
  2. 插入和删除：在 vector 中插入或删除元素可能会导致内存重新分配，这需要移动大量元素，因此时间复杂度为 O(n)。在 list 中，插入和删除元素只需要改变链接，这可以在常数时间内完成。
  3. 大小和容量：vector 的大小和容量是动态变化的，它会根据需要自动增长。而 list 的大小是固定的，但它可以无限增长，因为链表的元素可以在内存中的任意位置。
  4. 迭代器：vector 的迭代器是随机访问迭代器，可以快速访问容器中的任意元素。list 的迭代器是双向迭代器，可以向前和向后遍历，但不能随机访问。

list__388">31. 在使用 list 容器时，如何避免无限循环的问题？

解答：
在使用 list 容器时，避免无限循环的关键是确保不要创建循环引用。在 list 中，每个元素都包含两个指针，分别指向前一个元素和后一个元素。如果删除操作没有正确更新这些指针，就可能导致元素之间的链接没有被正确断开，从而形成循环。
为了避免无限循环，应该总是在删除元素之前删除指向它的所有引用，并且在删除元素时总是从链表的头部开始。此外，使用 erase() 函数时，确保不要删除最后一个元素后立即访问下一个元素，因为这时下一个元素的指针可能仍然指向已被删除的元素。
例如，下面的代码可能会导致无限循环，因为它尝试访问已被删除元素的下一个元素：

#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};auto it = myList.begin();while (it != myList.end()) {it = myList.erase(it); // 删除当前元素并返回下一个元素}// 在这里尝试访问 it 可能会导致无限循环，因为 myList 已经为空return 0;
}

正确的做法是在循环中直接使用 erase() 函数的返回值来更新迭代器：

#include <list>
int main() {std::list<int> myList{1, 2, 3, 4, 5};while (!myList.empty()) {myList.erase(myList.begin()); // 删除并返回第一个元素}// myList 现在为空，没有无限循环的风险return 0;
}

http://www.ppmy.cn/devtools/4579.html

相关文章

2024-4-19 群讨论：GraalVM 与 JVM 使用

2024-4-19 群讨论：GraalVM 与 JVM 使用

以下来自本人拉的一个关于 Java 技术的讨论群。关注公众号&#xff1a;hashcon&#xff0c;私信进群拉你 GraalVM Native Image 的进程能否被 jps 看到&#xff1f; 感谢 dreamlike_ocean ( https://space.bilibili.com/8227104 )指正 如果编译参数里面开启了 jstat&#xff…
阅读更多...
傅里叶变换例题

傅里叶变换例题

目录 傅里叶转化例题： 时移 频移 尺度 时域卷积性质：卷积==乘机
阅读更多...
C++：运算符重载和“const”成员

C++：运算符重载和“const”成员

hello&#xff0c;各位小伙伴&#xff0c;本篇文章跟大家一起学习《C&#xff1a;运算符重载》&#xff0c;感谢大家对我上一篇的支持&#xff0c;如有什么问题&#xff0c;还请多多指教 &#xff01; 文章目录 赋值运算符重载1. 运算符重载2.赋值运算符重载第一个点第二个点&…
阅读更多...
css常见动画

css常见动画

1、音乐播放效果 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>制作竖条加载动画</title><style>.animbox {margin: 50px auto;width: 200px;text-align: center;}/*设置各竖条的共有样…
阅读更多...
js，ts中简写符号大全

js，ts中简写符号大全

falsy 值&#xff08;虚值&#xff09;&#xff1a;是在布尔值Boolean上下文中认定为 false 的值。在 JavaScript 中只有 8 个 falsy 值&#xff0c;包括undefined、null、false、空字符串 (双引号 ""、单引号’’、反引号 )、NaN、0。 nullish 值&#xff1a;要么是…
阅读更多...
c++通过运算符重载实现的日期类(源码)

c++通过运算符重载实现的日期类(源码)

通过我们对运算符重载的学习&#xff0c;我们可以由此实现一个日期类。 头文件&#xff1a; #pragma once #include<iostream> #include<assert.h> using std::endl; using std::cout; using std::cin; using std::ostream; using std::istream;class Date{//声明…
阅读更多...
口型动画论文2：《基于语音驱动的表情动画设计与实现》

口型动画论文2：《基于语音驱动的表情动画设计与实现》

说明 本文是北京邮电大学的硕士毕业论文&#xff0c;作者是郭梦婷。由于是艺术硕士&#xff0c;所以本文没有罗列很多公式&#xff0c;而是从动画创作的角度来写如何根据语音设计动画人物的嘴型及表情。本文作者行文缜密、轻松&#xff0c;举得例子都是一些热播的动画和电影&a…
阅读更多...
ChatGPT深度科研应用、数据分析及机器学习、AI绘图与高效论文撰写

ChatGPT深度科研应用、数据分析及机器学习、AI绘图与高效论文撰写

2022年11月30日&#xff0c;可能将成为一个改变人类历史的日子——美国人工智能开发机构OpenAI推出了聊天机器人ChatGPT3.5&#xff0c;将人工智能的发展推向了一个新的高度。2023年4月&#xff0c;更强版本的ChatGPT4.0上线&#xff0c;文本、语音、图像等多模态交互方式使其在…
阅读更多...
最新文章

Copyright @ 2022~2023