How to move contents of one ArrayList to another?

Question

Is there a way to move the entire contents of an ArrayList to another instance of ArrayList in O(1)?

I.e.: only the reference to the backing array is passed from one instance to the other (elements are not copied one by one).

For example:

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)

Even better, is there an ArrayList#swapContents(ArrayList) method?

---

Further explanation and use-case:

Further explanation 1: the references of 'a' and 'b' must not be exchanged. I am not looking for tmp = a; a = b; b = tmp; type of solutions.

Further explanation 2: The operation must be ~O(1) in time.

The use-case: This is useful when an object wants to encapsulate a list constructed outside:

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);
    }
}

Notice that we want to avoid making a copy (to increase speed and decrease memory usage). The crucial bit is that the callee must lose the ability to modify the (now encapsulated) ArrayList.

Solution 1

@Lirik answer is greate +1. However, if you are looking for a real ArrayList#swapContents(ArrayList), here is how you can do it:

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);
}

Solution 2

This should do it:

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

Conceptually speaking, a is now empty and b contains what a contained before. There was a single assignment and no copying of data, which is about the fastest you can do it. Does that satisfy your requirement, or do you actually want a to still reference the same array except that the given array should now be empty?

Update

I don't believe that in C++ the time complexity for the move operation is O(1) either. It's also prudent to point out that "because classes in Java use reference semantics, there are never any implicit copies of objects in those languages. The problem move semantics solve does not and has never existed in Java." (see the answer by FredOverflow: C++ Rvalue references and move semantics)

Is there a way to move the entire contents of an ArrayList to another ArrayList so that only the reference to the backing array is passed from one to the other (i.e., so that elements are not copied one by one).

Given the above statement, then if you copy something from array a to array b in Java, both arrays will reference the same data. All that you do with move semantics in C++ is that you save the temporary object which needs to be created in order to make such a copy:

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

The last one does:

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

Move semantics does:

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

You save one destruct, but only in C++... the above problem does not exist in Java! See this article for more details on move semantics: http://thbecker.net/articles/rvalue_references/section_02.html

Solution 3

AFAIK, it's very not Java-like to keep track of "ownership" of references (at least on the programmer's side) which is why I doubt that you'll find the std::move()-like functionality that you want. It just isn't very commonly needed in Java. I guess C++ needs to keep track of object ownership explicitly because there is no garbage collection.

I think that your best bet is to create a defensive copy in your constructor and save space by relying on copy constructors of immutable objects:

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;
    }
}

At this point, you can "pass the arrays around" (really share them) in O(1) between your own immutable objects:

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

Hopefully, something like this can suit your purposes.

Another route you could go is use Guava's ImmutableList. Since these are immutable, you can safely copy the reference to the ImmutableList in a constructor.

The main approach is about making it safe for you to copy references to the lists rather than taking ownership over them.

Comments

[sinharaj]

This does not satisfy the requirements. Please see further explanation (added post factum).

[Kiril]

@sinharaj I don't believe you can do this in O(1) time... you can do it in O(n) time...

[sinharaj]

This is also not up to requirements. The operation should be O(1). Unless the addAll operations are O(1), which, I believe, they aren't.

[sinharaj]

Yeah, it seems like it. I've spent ages trying to find this functionality. I guess we'll eventually have to concede and say: no, there is no way of doing this in Java.

[Eng.Fouad]

@sinharaj I believe there is no way to move elements from ArrayList to another as O(1), unless you use multi-threading (By assigning a thread for each element in the list, whose job is to transfer the element to the other list).

[Kiril]

@sinharaj I don't know if it's O(1) in c++ either, I have not been able to find out what's the time complexity of std::move either. Furthermore, std::move relies on rvalues for the move semantics and that's not available in Java, see this answer: stackoverflow.com/questions/9498381/…

[Kiril]

@Eng.Fouad even that wouldn't be O(1), you would still perform n number of operations.

[Eng.Fouad]

@Lirik n number of operations, but concurrently! which I believe it is similar to O(1).

[Kiril]

@Eng.Fouad I get what you're trying to say, but time complexity is not calculated based on how many number of cores you have. Furthermore, unless you have n-number of cores, you will not be able to achieve O(1) time.

[sinharaj]

std::move(a) makes sure that a is an r-value reference. Based on this, instead of the copy constructor the move constructor can be called. The latter then simply moves the backing array pointer from one container to the other (clearly O(1)). Well, since there is no r-value concept in Java, we would have to resort to methods that have access to encapsulated data (like the suggested moveContentsTo). This method would do something similar to the move constructor in C++.

[sinharaj]

Btw, I'm not saying Java should get r-values or something. I would just like to have this bit of functionality (which just happens to be similar to what C++ move stuff does).

[Kiril]

@sinharaj I get it now, but nearly the same functionality can be achieved in Java in the same way that I showed initially. It works almost the same way in C++ with move semantics: the swap is performed on the references, but C++ makes a temporary which has to be destroyed and that temporary does not exist in Java (as far as I understand). It will be O(1) if you do make a temporary... I don't see why a temporary wouldn't be acceptable.

[sinharaj]

Look at the use case. An ArrayList is passed as an argument to a constructor (method). We want the callee to lose the ability to modify the (now encapsulated) ArrayList from outside the class.

[sinharaj]

let us continue this discussion in chat