4

有没有办法在 O(1) 中将 ArrayList 的全部内容移动到另一个 ArrayList 实例？

即：只有对支持数组的引用从一个实例传递到另一个实例（元素不会一个一个地复制）。

例如：

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = new ArrayList<>();
a.moveContentsTo(b);
// 'a' is now empty, while 'b' contains everything that 'a' did before and 'a != b'
// It is desired that the 'moveContentsTo' method is O(1)

更好的是，有ArrayList#swapContents(ArrayList)什么方法吗？

进一步的解释和用例：

进一步解释1：'a'和'b'的引用不能互换。我不是在寻找tmp = a; a = b; b = tmp;解决方案的类型。

进一步解释2：运算必须及时~O(1)。

用例：当对象想要封装外部构造的列表时，这很有用：

public class A {
    private ArrayList<String> items = new ArrayList<>();

    /**
     * This method takes the sole ownership of the contents. Whoever
     * passed the list from the outside will not be able to modify
     * contents of 'this.items' from outside the class.
     */ 
    public AnImmutableObject(ArrayList<String> items) {
        if (items != null) {
            items.moveContentsTo(this.items);
        }
    }

    /**
     * Other collections that do not provide the 'move' functionality
     * must be copied. If we just stored the reference to 'items' we
     * would break encapsulation as whoever called the constructor
     * still have write capabilities to the collection.
     */ 
    public A(Collection<String> items) {
        if (items != null) {
            this.items.addAll(items);
        }
    }

    public List<String> getItems() {
        return Collections.unmodifiableList(items);
    }
}

请注意，我们希望避免进行复制（以提高速度并减少内存使用）。关键是被调用者必须失去修改（现在封装的）的能力ArrayList。

4

3 回答 3

2

AFAIK，跟踪引用的“所有权”（至少在程序员方面）非常不像 Java，这就是为什么我怀疑你会找到std::move()你想要的类似功能的原因。它在 Java 中并不是很常用。我猜 C++ 需要明确地跟踪对象所有权，因为没有垃圾收集。

我认为你最好的选择是在你的构造函数中创建一个防御性副本并通过依赖不可变对象的复制构造函数来节省空间：

public class AnImmutableObject {

    private final List<String> items;

    /**
     * Creates a new immutable object with the given list of items.
     * Always deep copy from an outside source, because we can't know if the
     * calling code will modify that collection later.
     */ 
    public AnImmutableObject(Collection<String> items) {
        // It's a constructor. We know items needs to be set.
        // We are creating a new array list, using its constructor which deep
        // copies the collection, and immediately wrapping it to make it truly
        // immutable. We are guaranteed that no one will hold a reference to the
        // mutable view of the new ArrayList.
        this.items = Collections.unmodifiableList(new ArrayList<String>(items));
    }

    /**
     * Creates a new immutable object with the same items as another.
     * Copying the reference here is completely safe because we
     * enforce the immutability of the items array.
     */ 
    public AnImmutableObject(AnImmutableObject source) {
        items = source.items;
    }

    public List<String> getItems() {
        return items;
    }
}

此时，您可以在自己的不可变对象之间在 O(1) 中“传递数组”（真正共享它们）：

ImmutableObject a = new ImmutableObject(Arrays.asList("A", "B", "C")); // O(n)
ImmutableObject b = new ImmutableObject(a); // O(1)

希望这样的事情可以满足您的目的。

您可以采用的另一条路线是使用Guava的ImmutableList。由于这些是不可变的，您可以安全地将引用复制到ImmutableList构造函数中。

主要方法是让您可以安全地复制对列表的引用，而不是获得对它们的所有权。

于 2012-04-05T04:55:18.283 回答
2

@Lirik 的答案是 +1。但是，如果您正在寻找一个真正的ArrayList#swapContents(ArrayList)，您可以这样做：

public static void swapContents(ArrayList<String> listA, ArrayList<String> listB)
{
    List<String> temp = new ArrayList<String>(listA);
    listA.clear();
    listA.addAll(listB);
    listB.clear();
    listB.addAll(temp);
}
于 2012-04-05T04:08:23.797 回答
2

这应该这样做：

ArrayList<String> a = new ArrayList<>(Arrays.asList("A", "B", "C"));
ArrayList<String> b = a;
a = new ArrayList<>();

从概念上讲，a现在是空的，b包含a之前包含的内容。有一个单一的任务，没有数据复制，这大约是你能做到的最快的。这是否满足您的要求，或者您是否真的想a引用同一个数组，除了给定的数组现在应该是空的？

更新

我不相信在 C++ 中移动操作的时间复杂度也是 O(1)。还要谨慎指出“因为 Java 中的类使用引用语义，所以这些语言中从来没有任何对象的隐式副本。移动语义解决的问题在 Java 中不存在也不存在。 ”（参见 FredOverflow 的回答：C++ 右值引用和移动语义）

有没有办法将 ArrayList 的全部内容移动到另一个 ArrayList 以便只有对支持数组的引用从一个传递到另一个（即，这样元素就不会一个一个地复制）。

鉴于上面的语句，那么如果你在 Java 中从一个数组复制a到另一个数组，两个数组将引用相同的数据。b您在 C++ 中使用移动语义所做的所有事情就是保存需要创建的临时对象以制作这样的副本：

X foo();
X x;
// perhaps use x in various ways
x = foo();

最后一个是：

destructs the resource held by x,
clones the resource from the temporary returned by foo,
destructs the temporary and thereby releases its resource.

移动语义可以：

swap resource pointers (handles) between x and the temporary,
temporary's destructor destruct x's original resource.

你保存了一个destruct，但只在C++中......上面的问题在Java中不存在！有关移动语义的更多详细信息，请参阅本文：http: //thbecker.net/articles/rvalue_references/section_02.html

于 2012-04-05T03:56:30.357 回答