关于邻接表的一点小疑问
邻接表不是一般都是用链表来实现的吗，感觉很少看见有人用C++ STL里的list容器来实现邻接表呢？list不是会很方便吗
list就是链表
不知道你这个问题是否已经解决, 如果还没有解决的话:
- list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。
- list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率 更好
- 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销
| 构造函数 | 接口说明 |
|---|---|
| list() | 构造空的list |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list(const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
**此处一定要注意，是左闭右开的区间！！！ **
list iterator的使用
| 函数声明 | 接口说明 |
|---|---|
| begin（） end（） | 正向迭代器，对迭代器执行++操作，迭代器向后移动 |
| rbegin（） rend（） | 反向迭代器，对迭代器执行++操作，迭代器向前移动 |
其他重要接口
| 函数声明 | 接口说明 |
|---|---|
| empty | 判空 |
| size | 返回list中有效节点个数 |
| front | 返回list中第一个节点的值 |
| back | 返回list中最后一个节点的值 |
| push_front | 头插 |
| pop_front | 头删 |
| pop_front | 尾删 |
| push_back | 尾插 |
| insert | 在pos位置插入元素 |
| erase | 删除pos位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list的元素 |
list的迭代器失效
迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响
邻接表是一种图的表示方法，常用于有向图和无向图。邻接表使用链表来存储每个节点的邻居节点，因此链表的使用是一种很自然的选择。这就是为什么很少使用STL中的list容器来实现，而通常使用链表来实现的原因。使用list容器实现邻接表也是可行的。使用list的优点是，可以通过STL提供的算法，如sort进行排序，unique去重等。同时可以通过迭代器方便地遍历链表。下面是一个使用STL中的list容器实现邻接表的示例代码：
#include <iostream>
#include <list>
using namespace std;
// Graph class represents a directed graph using adjacency list representation
class Graph
{
int V; // No. of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // function to add an edge to graph
void printGraph(); // prints adjacency list representation of graph
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::printGraph()
{
for (int v = 0; v < V; ++v)
{
cout << "Adjacency list of vertex " << v << "\n head ";
for (auto x : adj[v])
cout << "-> " << x;
printf("\n");
}
}
// Driver code
int main()
{
// create the graph given in above figure
int V = 5;
Graph g(V);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.printGraph();
return 0;
}
这里使用了STL中的list容器，list *adj存储了每个结点的邻居结点，其中*adj是一个指向list的指针，adj[v]表示结点v的邻居节点，adj[v].push_back(w)表示把结点w加入到结点v的邻居列表中。
参考资料：https://www.geeksforgeeks.org/graph-and-its-representations/