JAVA基础篇五（Java,C++中的容器类）

快来打我* 2022-08-03 12:44 199阅读 0赞

说到容器， 学习C++的都会想到STL库，曾经把STL源码剖析看了两遍，每次头昏脑胀不想再看，现在回想起来，STL库的东西忘的差不多了，就剩几个容器的使用方法了。

关于JAVA的容器，大二的时候就开始学习过，但是却懵懵懂懂，这次把两种语言的容器做个对比，记录下来，希望能够做到帮助自己记忆，同时帮助别人。

**1、C++容器**

标准STL序列容器：vector、string、deque和list。

标准STL关联容器：set、multiset、map和multimap。

非标准序列容器slist和rope。slist是一个单向链表，rope本质上是一“重型”string。

非标准的关联容器hash\_set、hase\_multiset、hash\_map和hash\_multimap。

vector<char> 作为string的替代。(见第13条)

vector作为标准关联容器的替代。(见第23条)

几种标准的非STL容器，包括数组、bitset、valarray、stack、queue和priority\_queue。

上面这种分类方法我也是第一次见到过，所以贴出来看一看，下面这种说法我会更喜欢一点：

<table style="color:rgb(0,0,0); font-family:Arial; font-size:14px; line-height:26px"> 
 <tbody> 
 <tr> 
 <td style="background-color:rgb(191,191,191)"> 标准容器类 </td> 
 <td style="background-color:rgb(191,191,191)"> 特点 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="background-color:rgb(242,242,242)"> 顺序性容器 </td> 
 </tr> 
 <tr> 
 <td> vector </td> 
 <td> 从后面快速的插入与删除，直接访问任何元素 </td> 
 </tr> 
 <tr> 
 <td> deque </td> 
 <td> 从前面或后面快速的插入与删除，直接访问任何元素 </td> 
 </tr> 
 <tr> 
 <td> list </td> 
 <td> 双链表，从任何地方快速插入与删除 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="background-color:rgb(242,242,242)"> 关联容器 </td> 
 </tr> 
 <tr> 
 <td> set </td> 
 <td> 快速查找，不允许重复值 </td> 
 </tr> 
 <tr> 
 <td> multiset </td> 
 <td> 快速查找，允许重复值 </td> 
 </tr> 
 <tr> 
 <td> map </td> 
 <td> 一对多映射，基于关键字快速查找，不允许重复值 </td> 
 </tr> 
 <tr> 
 <td> multimap </td> 
 <td> 一对多映射，基于关键字快速查找，允许重复值 </td> 
 </tr> 
 <tr> 
 <td colspan="2" style="background-color:rgb(242,242,242)"> 容器适配器 </td> 
 </tr> 
 <tr> 
 <td> stack </td> 
 <td> 后进先出 </td> 
 </tr> 
 <tr> 
 <td> queue </td> 
 <td> 先进先出 </td> 
 </tr> 
 <tr> 
 <td> priority_queue </td> 
 <td> 最高优先级元素总是第一个出列 </td> 
 </tr> 
 </tbody> 
</table>

粘贴一个List用法的代码：

#include <iostream>
 #include <list>
 #include <numeric>
 #include <algorithm>
 using namespace std;
 //创建一个list容器的实例LISTINT
 typedef list<int> LISTINT;
 
 //创建一个list容器的实例LISTCHAR
 typedef list<int> LISTCHAR;
 
 int main(){
 //--------------------------
 //用list容器处理整型数据
 //--------------------------
 //用LISTINT创建一个名为listOne的list对象
 LISTINT listOne;
 //声明i为迭代器
 LISTINT::iterator i;
 
 //从前面向listOne容器中添加数据
 listOne.push_front (2);
 listOne.push_front (1);
 
 //从后面向listOne容器中添加数据
 listOne.push_back (3);
 listOne.push_back (4);
 
 //从前向后显示listOne中的数据
 cout<<"listOne.begin()--- listOne.end():"<<endl;
 for (i = listOne.begin(); i != listOne.end(); ++i)
 cout << *i << " ";
 cout << endl;
 
 //从后向前显示listOne中的数据
 LISTINT::reverse_iterator ir;
 cout<<"listOne.rbegin()---listOne.rend():"<<endl;
 for (ir =listOne.rbegin(); ir!=listOne.rend();ir++) {
 cout << *ir << " ";
 }
 cout << endl;
 
 //使用STL的accumulate(累加)算法
 int result = accumulate(listOne.begin(), listOne.end(),0);
 cout<<"Sum="<<result<<endl;
 cout<<"------------------"<<endl;
 
 //--------------------------
 //用list容器处理字符型数据
 //--------------------------
 
 //用LISTCHAR创建一个名为listOne的list对象
 LISTCHAR listTwo;
 //声明i为迭代器
 LISTCHAR::iterator j;
 
 //从前面向listTwo容器中添加数据
 listTwo.push_front ('A');
 listTwo.push_front ('B');
 
 //从后面向listTwo容器中添加数据
 listTwo.push_back ('x');
 listTwo.push_back ('y');
 
 //从前向后显示listTwo中的数据
 cout<<"listTwo.begin()---listTwo.end():"<<endl;
 for (j = listTwo.begin(); j != listTwo.end(); ++j)
 cout << char(*j) << " ";
 cout << endl;
 
 //使用STL的max_element算法求listTwo中的最大元素并显示
 j=max_element(listTwo.begin(),listTwo.end());
 cout << "The maximum element in listTwo is: "<<char(*j)<<endl;
 }

**2、JAVA容器**

JAVA的容器---List,Map,Set   
Collection   
├List   
│├LinkedList   
│├ArrayList   
│└Vector   
│　└Stack   
└Set   
Map   
├Hashtable   
├HashMap   
└WeakHashMap

**Collection接口 **  
　　Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

表(List)和集合(Set)是java.util中定义的两个接口(interface)。这两个接口都继承自Collection接口。通过实施接口，我们可以获得相应的容器。

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。 注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List： List list = Collections.synchronizedList(new LinkedList(...));

ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。   
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。 和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和ArrayList创建的 Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出ConcurrentModificationException，因此必须捕获该异常。

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。   
很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。   
请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

**Map接口 **  
　　Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。 添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。 Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

JAVA list 的使用方法：

import java.util.*;
 public class ArrayListTest{
 public static void main(String dd[]){
 //new了一个存储list
 List l=new ArrayList();
 //因为Collection framework只能存储对象所以new封装类
 l.add(new Integer(1));
 l.add(new Integer(2));
 l.add(new Integer(3));
 l.add(new Integer(4));
 
 Iterator it=l.iterator();
 //hasNext是取值取的是当前值.他的运算过程是判断下个是否有值如果有继续.
 while(it.hasNext()){
 	//设it.next封装类,调用Integer的intValue方法返回值为int赋给i;
 	int i=((Integer)it.next()).intValue();
 	System.out.println("Element in list is : "+i);
 }
 }
 }

使用java有些集合是线程安全的，而c++本身没有这样的要求。

另外，java传递的都是引用，而c++容器存放的是对象的复制品。