Is that a Java-specific thing? My experience with C++ is that ever since libclang became widely used, autocompletion works really well—but that's because libclang is so good. Is there an analog of libclang for Java?
What package are you using for your Emacs back end for completion? I've tried several and never really found them stable or even working in some cases. I write a couple thousand lines of C++ every week in emacs and I've actually become very productive without auto completion, so perhaps I'm not missing it anymore at all.
I use irony-mode (with its flycheck and company support) on OSX, and I think it works really well. It uses libclang as the backend, so for completion it's about as precise as a compiler can be.
I code in C so can't speak for C++, but I imagine it works well for that too: irony-mode as a backend and company-mode as frontend. It pretty much gives the Xcode auto-complete experience, and I think it works great!
Seconded this, this is my setup on both Windows and Linux and works for me across multi-million-line C and C++ codebases. It's quite finicky to get set up on Windows at first (or at least, it was for me last time I tried), but once you have irony-mode working with libclang, you don't need to think about it ever again, except for changing a couple compiler flags here and there.
My one complaint is that clang's MSVC mode is imperfect, and sometimes suggests some strange things (or produces some false negative/positive in syntax checking). But they've been getting much better lately and it's never caused me much pain.
e: also, second what a sibling said - combo this with flycheck-mode and you have yourself a full-blown C++ IDE in emacs ;)
I tried irony mode, but my autocomplete pop-ups would contain all kinds of nonsense, and I noticed at least two other issues on the irony mode github page that showed other people with the same experience as mine, on Mac. So I eventually gave up after not tracking down a resolution.